Search on the blog

2011年7月19日火曜日

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

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


0 件のコメント:

コメントを投稿