foldr

『Real World Haskell』 4章の内容から。

左畳み込みと右畳み込みの違い

foldl (+) 0 (1:2:3:[]) == foldl (+) (0 + 1)             (2:3:[])
                       == foldl (+) ((0 + 1) + 2)       (3:[])
                       == foldl (+) (((0 + 1) + 2) + 3) []
                       ==           (((0 + 1) + 2) + 3)
 
foldr (+) 0 (1:2:3:[]) == 1 + foldr (+) 0 (2:3:[])
                       == 1 + (2 + foldr (+) 0 (3:[]))
                       == 1 + (2 + (3 + foldr (+) 0 []))
                       == 1 + (2 + (3 + 0))

• foldl では初期値は左側に現れ括弧も左側に寄っている
• foldr では初期値は右側に現れ括弧も右側に寄っている

右畳み込みというとリストの右から処理しているような感じがするのだが foldl と同様左から処理している。
初期値の違いより括弧の違いが重要でこれが以前教えてもらった foldr と merge の相性の良さにつながるようだ。

無限リストを扱ってみると foldr は値を返すことができるが foldl はできない。

Prelude> take 10 $ foldr (:) [] [1..]
[1,2,3,4,5,6,7,8,9,10]

Prelude> take 10 $ foldl (flip (:)) [] [1..]
Interrupted.

原始帰納的 (primitive recursive)

foldr を使って表現できるような関数のクラスを原始帰納的と言います。驚くべき数のリスト処理関数は原始帰納的です。

検索してみると難しそうなページしかないが『数学ガール ゲーテルの不完全性定理』も Hit するのでその中の原始再帰的関数のところを引用しておく。

原始再帰的関数と呼ばれる関数の仲間を定義する。これは、ひとことで言ういうなら、関数の値を得るまでに必要な《繰り返し回数》に上限がある関数だ。

現時点ではピンとこない。

foldl

Scala exercises for beginners の関数もおそらく原始帰納的*1で foldl も foldr で実装できるそうだ。

myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

これは混乱したが最初の例を解いてみたら理解できた。

myFoldl (+) 0 (1:2:3:[]) == foldr step id (1:2:3:[]) 0
                         == step 1 (step 2 (step 3 id)) 0
                         == step 2 (step 3 id) (0 + 1)
                         == step 3 id ((0 + 1) + 2)
                         == id (((0 + 1) + 2) + 3)
                         == (((0 + 1) + 2) + 3)

foldr を一気に展開してから step を適用したらどうなるかの順で考えた。
id が foldr を展開したリストの末尾に存在するのでそこで処理が完了する。

やっと読めるレベルだがいつか定義できるレベルになれるのだろうか?

*1:TODO foldr で実装する