foldrでmap関数???

このエントリーをはてなブックマークに追加

最近大川徳之さんの「関数プログラミング実践入門」を購入して再びHaskellをちらほら触っています。
foldr関数に差し掛かったところなのですが、割と混乱してしまったので掘り下げてみました。
最初に引っかかったのがこの文章です。

「foldrは実は、リストの(:)と[]をそれぞれ関数と初期値で置換する関数です。」

なんとなくわかるような、でもわかってないような、そしてやっぱりわかってなかった自分がそこにはいました。私は凡人以下のプログラミング脳、数学脳なのでここでストップ。。。Google先生登場です。

Functional Programming

上のサイトで割とイメージがつかめました。
まず、n個の要素から構成されるリストxs([x1,x2, … ,xn])は木構造で見ると以下のように描けます。

スクリーンショット 2015-01-10 22.23.17

 

つまり、大川さんが仰っていた「foldrはリストの(:)と[]をそれぞれ関数と初期値で置換する関数」というのは木構造で表現すると以下のことです。
スクリーンショット 2015-01-10 22.46.47

リストの(:)と[]が関数fと初期値zに置き換わっていることがわかります。これをさらに具体例を挙げてみましょう。例えば[1,2,3]というリストがあったとします。このリストに対して初期値を4として右側から乗算(*)で畳み込む(foldr)を適用した場合以下のようになります。

1 * (2 * (3 * 4)) = 24

さらにリストと木構造で描くと以下の通り。

スクリーンショット 2015-01-10 22.53.51

 

なるほど!確かに(:)と[]が関数と初期値に変わっている!結構スッキリです。

しかし

一難去ってまた一難。
その直後くらいにしれっと書いてある文章でまたつまづきます。

「foldrからはmapが作れるなど、汎用的で強力な関数になっています」

map' :: (a -> b) -> [a] -> [b]
map' f = foldr ((:).f) []

わからん。いや、作れそうな雰囲気はなんとなくわかるんですけど、これを自分でちゃんと理解できていないこともよくわかる。まずmap関数はと言いますと、指定された関数をリストのそれぞれの要素に適用してリストを生成する関数です。

*Main> map (*2) [1,2,3]
[2,4,6]

となります。イメージ的には多分↓

スクリーンショット 2015-01-10 23.16.48

 

お?ということは左から右の結果を出す為に(:)と[]を置換すればfoldr関数で同様の処理ができるわけだ!ということで以下のように描けることがわかります。(ラムダ式=図の中のfと思ってください)

スクリーンショット 2015-01-10 23.18.06

 

ラムダ式の内容は「関数(*2)を適用してリストysの先頭に要素を挿入する」ということなので上の例での((:).f)と同等の意味となります。ということでmap関数をfoldr関数で表すと以下のようになるのです。

map' :: (a -> b) -> [a] -> [b]
map' f = foldr ((:).f) []
−− map' f as = foldr ((:).f) [] asと一緒だし
-- map' f x:xs = foldr (\y ys -> f y:ys) [] xsとも一緒

いやー、脳みその体操が足りてない足りてない!

Written on January 10, 2015
このエントリーをはてなブックマークに追加