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

foldl とレジスター

手続き型プログラム言語で1から10までの総和を計算するときは次の様にループを使う。

>>> if True:
... total = 0
... for i in range(1,6):
...  total += i
... print(total)
...
15

上のプログラムで変数 total はループの途中の計算結果を保持するレジスターだ。total の内容はループが一つ進むごとに次の様に値を変えていく。

total = total + 1 = 0 + 1 = 1
total = total + 2 = 1 + 2 = 3
total = total + 3 = 3 + 3 = 6
total = total + 4 = 6 + 4 = 10
total = total + 5 = 10 + 5 = 15

このように計算の途中経過を変数 total に残していくので、これができない Haskell ではプログラムできないように見える。しかしこの計算の過程は次のような計算に置き換えることができる。

((((0 + 1) + 2) + 3) + 4) + 5

python のループではこの計算の途中経過を一旦 total に破壊的代入しているのがわかる。しかし、見方を変えて、まずこの計算式を最初に展開していって最後に一気に計算するという方法をとれば途中の計算結果をレジスター total に入れる必要がなくなる。Haskell ではこのような畳み込み計算を利用してレジスターを使わずに累積の加算を行うことができる。

このような目的のために Haskell の foldl という畳み込みの計算を利用することができる。

Prelude> foldl (+) 0 [1..5]
15

foldl がどのような計算をしているかは foldl 自身に聞くことができる。

Prelude> foldl (\x y -> "(" ++ x ++ "+" ++ y ++ ")") (show 0) $ map show [1..5]
"(((((0+1)+2)+3)+4)+5)"

手続き型プログラム言語で累積の計算をするときは、途中経過を毎回レジスターに保存するというやり方を行うが、Haskell はまず一気に計算式を展開してしまってそのあとその式を計算するという手順になる。したがって途中経過がないのでレジスターは要らないのだ。

畳み込みの関数には foldl 以外に foldr があるが、次の様に畳み込みの方向が反対になっている。

Prelude> foldr (\x y -> "(" ++ x ++ "+" ++ y ++ ")") (show 0) $ map show [1..5]
"(1+(2+(3+(4+(5+0)))))"
by tnomura9 | 2023-01-31 17:38 | Haskell | Comments(0)
<< flip map 関数で多重ループを記述する >>