『入門Haskell』練習問題例解(6) - 坂梨の人生坂あり日記

foldl

p.73の(1)です。

foldl (+) 0 [1, 2, 3, 4, 5] について、動作ステップを確認しなさい。

foldlの定義は

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs

となっています。では確認してみます。

foldl (+) 0 [1, 2, 3, 4, 5]
= foldl (+) ((+) 0 1) [2, 3, 4, 5]
= foldl (+) ((+) ((+) 0 1) 2) [3,4,5]
= foldl (+) ((+) ((+) ((+) 0 1) 2) 3) [4, 5]
= foldl (+) ((+) ((+) ((+) ((+) 0 1) 2) 3) 4) [5]
= foldl ((+) ((+) ((+) ((+) ((+) 0 1) 2) 3) 4) 5) []
= (+) ((+) ((+) ((+) ((+) 0 1) 2) 3) 4) 5
= (+) ((+) ((+) ((+) 1 2) 3) 4) 5
= (+) ((+) ((+) 3 3) 4) 5
= (+) ((+) 6 4) 5
= (+) 10 5
= 15

こうなります。二行目の ((+) 0 1) はすぐに評価されず、先にfoldlの展開が行われるようです。なので、foldlに無限リストを渡すとヒープが一杯になってエラーになります。ここがfoldrと違うところです。foldrに無限リストを渡したらどうなるかということはfoldl とfoldr - foldrに無限リストを与えるとどうなるか？ - 坂梨の人生坂あり日記で確認しました。

foldr

p.73の(2)です。

foldrの定義を書きなさい。

myFoldr f a [] = a
myFoldr f a (x:xs) = f x (myFoldr  f a xs)

これでよし。

reverse

p.73の(3)です。

reverseは、リストを逆転させる関数です。たとえば reverse [1, 2, 3] は [3, 2, 1] になります。このreverseを定義しなさい。

ここで出題されているということは、foldlかfoldrを使って定義しろということなのでしょう。方針としては、初期値として空リストを用意し、順番に頭に繋げていくということになります。

まずfoldl版。

myReverse = foldl (\x y -> y : x) []

となります。Prelude.flipを使って変数を消去すると

myReverse = foldl (flip (:)) []

となります。これは仕様書に書いてあるのと同じ定義です。

次にfoldr版。

myReverse = foldr (\x y -> y ++ [x]) []

これも変数を消去してみましょう。

  foldr (\x y -> y ++ [x]) []
= foldr (\x y -> y ++ ((:) x [])) []
= foldr (\x y -> y ++ (flip (:) [] x)) []
= foldr (\x y -> flip (++) (flip (:) [] x) y) []  -- ここでyを消去できる
= foldr (\x -> flip (++) (flip (:) [] x)) []
= foldr (\x -> (flip (++) . (flip (:) []) x) []   -- 関数を合成しxを消去できる形にする
= foldr ((flip (++)) . (flip (:) [])) []

一応こんな形になりましたがこれを一見して意味のわかる人はそういないでしょう。自分でもよくわかりません。まあお遊びということで。