Haskell勉強記（8）

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

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

view plainprint?

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

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

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

view plainprint?

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

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

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

view plainprint?

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

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

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

view plainprint?

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

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

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

view plainprint?

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

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を末尾に付ける関数を作る。さらにそれを受け取って、・・・・・という具合。

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