Haskell勉強記（8）

前回分からなかったfoldlをfoldrで書きかえる方法について。

duality theorems concerning foldl and foldrの一つらしい。

main = print $ foldl (++) [] ["1", "2", "3", "4", "5"]

は、foldrを用いて以下のように書ける。

main = print $ foldr (\x g n -> g (n ++ x)) id ["1", "2", "3", "4", "5"] []

関数適用がもっとも結合度が高いことと、関数適用はleft-associativeであることを考えると、上式は以下と等価。

main = print $ foldr (\x g n -> g (n ++ x)) id ["1", "2", "3", "4", "5"] $ []

ちょっとだけ分かりやすく書くと、

func = foldr (\x g n -> g (n ++ x)) id ["1", "2", "3", "4", "5"]
main = print $ func []

なるほど、foldrは、値と関数を受け取って新しい関数を返す関数であることが分かる。やってるのは、こんなこと。

func = (\x g n -> g (n++x)) [1] $
   (\x g n -> g (n++x)) [2] $
   (\x g n -> g (n++x)) [3] $
   (\x g n -> g (n++x)) [4] $
   (\x g n -> g (n++x)) [5] $ id

main = print $ func []

それ自体を返す関数を受け取って、5を末尾に付ける関数を作る。それを受け取って、4を末尾に付けた後に、5を末尾に付ける関数を作る。さらにそれを受け取って、・・・・・という具合。

一般に以下の書き換えが可能。