あと味

たくさん情報を食べて、たくさん発信すると、あとになって味わい深い。

プログラミングHaskellのfoldr, foldlの説明が秀逸だった件

Haskell プログラミング全般

今年はHaskellを勉強しています。

土日などを利用して、すごいH本を3〜4週間かけて読み終えました。時間かかった分、記憶の密度が低くて、まだ理解度は低いです。

新しい概念を学ぶ時は、同じテーマの本を何冊か読んで、本当に読みたかった本を再度読み直すというのが自分の学習の方法として定着しているので、今は、プログラミングHaskellを読み進めています。

すでに「ふつうのHaskellプログラミング」は読み終えていましたが、改めて読むと、本当に普通のプログラミング本に感じたので、すごいH本がかなり刺激的で、よくできた本なんだと思います。読み直す時が楽しみであります。

本題

さて、「プログラミングHaskell」の話に戻りますが、foldrとfoldlの説明の箇所が秀逸だと思ったので内容を紹介してみます。*1

fold関数は、他の言語でreduceとかinjectとか呼ばれている関数ですね。個人的には、かなり表現力が強い関数なので、一番好きな関数かもしれません。*2

プログラミングHaskellでは、冒頭にこんな紹介があります。

引数にリストを取る関数は、リストに対する再帰を使って、以下のような簡単な様式で定義できることが多い。

f [] = v
f (x:xs) = x ⊕ f xs

標準ライブラリで提供される高階関数foldr（fold rightの略称）は、この再帰的な様式を抽出する。演算子⊕と値vは引数となる。

なんのこっちゃという感じですが、確かに、fold関数には引数にリストを除いて、⊕に相当する関数と初期値に相当する値vを渡します。

例にある、sum関数とproduct関数のfoldを使わない定義はこんな感じです。

sum []         = 0
sum (x:xs)     = x + sum xs

product []     = 1
product (x:xs) = x * product xs

sum関数とproduct関数のfoldを使った定義はこんな感じです。

sum     = foldr (+) 0
product = foldr (*) 1

確かに、⊕に相当する部分と、値vに相当する部分がそれぞれ引数になっています。しかも、いつの間にか再帰がなくなりましたね。再帰的な様式を抽出するというのは本当みたいです。

Haskellはすべての関数がカリー化されるので、sumもproductもリストに適用すれば、結果が返ってきます。

わかりやすかった説明

で、前提は以上で、次に以下のような説明が続きます。

すなわち関数foldr f vは、空リストを値vに変換する。空でないリストに対しては、「先頭の要素」と「残りのリストに対し自分自身を呼び出した結果」に関数fを適用する。ただ実際には、foldr f vは再帰的に理解するのではなく、単にcons演算子を関数fに置き換え、末尾の空リストを値vに置き換えると理解する方がいいだろう。

という説明の後に具体例がこのようにきます。

1:(2:(3:[]))

これは、以下のように変換される。

1+(2+(3+0))

こういう説明、今まで見たことなくて、すごくわかりやすい説明だと思いました。
すべての関数を中置記法で使えるHaskellだからこそわかりやすいのかもしれませんが、他の言語でその機能の採用率が低めってだけと考えれば良いだけですし。

まとめるとfoldrのフォーマットは以下のような感じですね。

foldr f v [...]

で、次からは例です。

例: リストの値を合計する
foldr (+) 0 [1,2,3]

関数f = (+)
値v = 0

before:

1:(2:(3:[]))

cons演算子を関数fに置き換え、末尾の空リストを値vに置き換えてみる。

after:

1+(2+(3+0))
例: リストで最も大きい数値を求める
foldr max 0 [1,2,3]

関数f = max
値v = 0

before:

1:(2:(3:[]))

cons演算子を関数fに置き換え、末尾の空リストを値vに置き換えてみる。

after:

1`max`(2`max`(3`max`0))
例: リストの最初の要素を求める
getLeft :: a -> b -> a
getLeft a _ = a
foldr getLeft 0 [1,2,3]

関数f = getLeft
値v = 0

この例の場合、値vは即捨てるので、なんでもいいですが。

before:

1:(2:(3:[]))

cons演算子を関数fに置き換え、末尾の空リストを値vに置き換えてみる。

after:

1`getLeft`(2`getLeft`(3`getLeft`0))
例: リストの要素数を求める
succRight :: Enum a => a -> a -> a
succRight _ n = succ n
foldr succRight 0 [1,2,3]

関数f = succRight
値v = 0

before:

1:(2:(3:[]))

cons演算子を関数fに置き換え、末尾の空リストを値vに置き換えてみる。

after:

1`succRight`(2`succRight`(3`succRight`0))
例: リストを逆順にする
snoc :: a -> [a] -> [a]
snoc x xs = xs ++ [x]
foldr snoc [] [1,2,3]

関数f = snoc
値v = []

before:

1:(2:(3:[]))

cons演算子を関数fに置き換え、末尾の空リストを値vに置き換えてみる。

after:

1`snoc`(2`snoc`(3`snoc`[]))
例: リストの偶数の要素の合計値を求める
addEven :: Int -> Int -> Int
addEven n m  = if even n then m + n else m
foldr addEven 0 [1,2,3,4]

関数f = addEven
値v = 0

before:

1:(2:(3:(4:[])))

cons演算子を関数fに置き換え、末尾の空リストを値vに置き換えてみる。

after:

1`addEven`(2`addEven`(3`addEven`(4`addEven`0)))

foldr, foldlの要約

foldrの要約として以下の定義が掲載されていました。

foldr (⊕) v [x0, x1, ..., xn] = x0 ⊕ (x1 ⊕ (...(xn ⊕ v)...))

で、foldrは⊕が左結合であることが前提の関数で、foldlは⊕が右結合であることが前提の関数だと。
foldlの定義も以下のように書かれています。

foldl (⊕) v [x0, x1, ..., xn] = (...((v ⊕ x0) ⊕ x1)...) ⊕ xn

foldrかfoldlかでは、個人的には圧倒的にfoldlの方がわかりやすいので、foldl相当（reduceかreduceRightだったらreduce）ばかり使っていましたが、どちらでも実装できる場合は、より効率の良い方を選びましょうという話でした。
例えば、すごいH本には、(++)は(:)に比べると遅いので、リストを使って、リストを構築するようなケースでは、foldrを使う方が良いと書いてありました。後、無限リスト扱う時とか。consは右結合ですもんね。

まとめ

今までに比べてfold(r|l)関数の処理が頭の中で可視化されるようになった気がします。
あと、foldrに渡す関数は、定義がどれだけ複雑だったとしても、とどのつまり左被演算子が要素で右被演算子が累積値になる二項演算子的な関数で、foldlに渡す関数も、定義がどれだけ複雑だったとしても、とどのつまり、左被演算子が累積値で右被演算子が要素になる二項演算子的な関数なんだねって理解もできました。
今後は、リストを使った再帰を書くような時は、foldr, foldlに書き換えることもまず検討しようと思います。

*1:すごいH本の説明もわかりやすかったですよ

*2:PerlのList::Utilにあるreduceは好きになれませんが...