foldl について

「畳み込み」を行う関数の一つである foldl 。

*main> foldl (+) 0 [1,2,3]
6

のようにリストの中身である1、2、3を左から足して、結果が6になる、という挙動を示す。いったいどういう仕組みなのだろうか。

foldl の定義は、

foldl :: (a -> b -> a) -> a -> [b] -> a                ･･･ 1)

foldl step zero (x:xs) = foldl step (step zero x) xs   ･･･ 2)
foldl _    zero []     = zero                          ･･･ 3)

foldlは引数を3つとる関数である。
1. step：リストの各値に適用する関数（この場合、+なので足すわけである）
2. zero：初期値。そして、計算途中の値を蓄積する場所である。ここに途中経過を蓄えながら再帰的に計算を行っていく
3. (x:xs)：対象となるリスト

具体的に fold (+) 0 [1,2,3] がどのように計算されるか順を追って調べてみよう。

foldl (+) 0 [1,2,3]
==> 2)式左辺を当てはめる
    step = +
    zero = 0 
    (x:xs) = [1,2,3] 、つまり x = 1、xs = [2,3]
    
    として 2)式右辺に適用
    foldl (+) ((+) 0 1) [2,3]
    ※ここで、((+) 0 1 ) というのは(0 + 1) と同じだから以降は後者の書き方にするよ、その方がシンプルなので。
    よって、
    foldl (+) (0 + 1) [2,3]

==> 上記結果を 2)左辺と照らし合わせる
    step = +
    zero = (0 + 1)    ← リストの最初項目（つまり 1）に関数(+) を適用した途中結果が格納されている
    (x:xs) = [2,3] 、つまり x = 2、xs = [3]
    
    2)式右辺を適用
    foldl (+) ((0 + 1) + 2) [3]

==> 上記結果を 2)左辺と照らし合わせる
    step = +
    zero = ((0 + 1) + 2)  ← リストの内容のうち、1と2を適用した結果が格納されている
    (x:xs) = [3]、つまり x = 3、xs = []  xsは空要素となる
    
    2)式右辺を適用
    foldl (+) (((0 + 1) + 2) + 3) []

==> 上記結果を 2)左辺と照らし合わせる
    step = +
    zero = (((0 + 1) + 2) + 3)
    3つ目の引数は [] である。
    
    3つ目の引数が[] なので 3)式が適用される。つまり返ってくる値はzero。よって、
    (((0 + 1) + 2) + 3)

==> 再帰処理は終点まで到達。(((0 + 1) + 2 ) + 3) の値が計算されて答えは 6
    

もう一度まとめる

foldl (+) 0 [1,2,3]
==> foldl (+) (0 + 1) [2,3]
==> foldl (+) ((0 + 1) + 2) [3]
==> foldl (+) (((0 + 1) + 2) + 3) []
==> (((0 + 1) + 2) + 3)
==> 6

というわけである。ふむふむ。
ここに至るまで、自分の場合紙と鉛筆が必須でした。流れをガリガリ書かないとなかなか見えてこない。

それにしても、このような計算の経緯を視覚化するツールとか無いのかな。言い出したものが作れの法則なのだろうけど。