人気ブログランキング | 話題のタグを見る

アキュームレータと畳込み

手続き型のプログラムではループの中に途中経過を保持する変数(アキュームレータ)を使うことが多い。例えば数列の総和を求めるプログラムは次のようになる。

irb(main):001:0> begin
irb(main):002:1> total = 0
irb(main):003:1> for i in 1..10
irb(main):004:2> total += i
irb(main):005:2> end
irb(main):006:1> puts total
irb(main):007:1> end
55

上のプログラムの for ループのなかで、総和の途中経過を保持する変数 total がアキュームレータだ。しかし、Haskell ではこのような再代入の方法はないので、別の方法を考えないといけない。一般的には次のようにリストの総和を求める関数を再帰的に定義する。

Prelude> {total [] = 0; total (x:xs) = x + total xs}
Prelude> total [1..10]
55

また、foldr や foldl のような畳込み関数を利用すると、擬似的なアキュームレータを記述することができる。それを示す前にまず foldr などの畳込みがどのように実行されるかを見てみる。

Prelude> foldr (\x y -> "(" ++ show x ++ "+" ++ y ++ ")") "0" [1..10]
"(1+(2+(3+(4+(5+(6+(7+(8+(9+(10+0))))))))))"
Prelude> foldl (\x y -> "(" ++ x ++ "+" ++ show y ++ ")") "0" [1..10]
"((((((((((0+1)+2)+3)+4)+5)+6)+7)+8)+9)+10)"

アキュームレータはなく、リストのデータがスタックに保存されていって展開の最後に計算されることがわかる。これをよく見ると foldl の x が手続き型のプログラムのアキュームレータ total の役割に近いことがわかる。そこでやってみた。

Prelude> foldl (\total x -> total + x) 0 [1..10]
55

ラムダ記法の本体の total + x のところが for ループの total = total + i に対応しているのがわかる。手続き型のプログラムのループの部分はこのように foldl で置き換えることができるかどうかを考えてみるのもいいかもしれない。たとえば、リストの要素の2乗和をとる計算は次のようになる。

Prelude> foldl (\total x -> total + x*x) 0 [1..10]
385

しかし、これは次のようなプログラムのほうが可読性が高い。

Prelude> sum [x*x| x <- [1..10]]
385

アキュームレータにこだわらずに計算の意味を考えた翻訳のほうも考える必要があるだろう。



追記

数値リストの総和と2乗和を同時に計算するプログラムを考えてみた。アキュームレータを意識したプログラムは次のようになる。

Prelude> foldl (\total x -> (fst total + x, snd total + x*x)) (0,0) [1..10]
(55,385)

アキュームレータを使わない場合は次のようになる。

Prelude> foldl (\x y -> (fst x + fst y, snd x + snd y)) (0,0) [(x,x*x)| x <- [1..10]]
(55,385)

アキュームレータを想定したほうが簡潔?

by tnomura9 | 2019-05-19 08:45 | Haskell | Comments(0)
<< 手続き型言語風の Haskel... mapM_ で IO モナドに... >>