Haskellのfoldrの挙動がわかりません

Question

main = print (reverse' [1,2,3,4])

reverse' :: [a]->[a]
reverse' = foldr (:) []

の出力結果が
[1,2,3,4]
となりました。

foldrはアキュムレーターが第２引数で、リストの各要素が第1引数となるので
上の例なら、まず
(:) 1 []
で[1]となり、次に
(:) 2 [1]
で[2,1]となり、最終的に
[4,3,2,1]が出力されるのではないかと思ったのですが、この考えのどこに誤りがあるのでしょうか。

Answer 1

上の例なら、まず(:) 1 []

最初は1じゃなくて4です

Comments

[igrep]

よくある誤解ですが、最初は1で合っています。

[ozwk]

再起を展開すると
(1:(2:(3:(4:[]))))になって
最初に[]と結合されるのが4だという意味です

[igrep]

なるほど。失礼いたしました。

Answer 2

「(:)」は結合則を満たしていて、結合則を満たす演算に対しての「foldl」と[foldr」は同じ挙動です。
(厳密には、第二引数であるアキュムレータが単位元であるならという但し書きが必要ですが)

どこに解釈の間違いがあるかというと、
(:) 1 [] ... = [1]
(:) 2 [1] ... = [2,1]
(:) 3 [2,1] ... = [3,2,1]
(:) 4 [3,2,1] ... = [4,3,2,1]
となるのではなく、
(:) 4 [] ... = [4]
(:) 3 [4] ... = [3,4]
(:) 2 [3,4] ... = [2,3,4]
(:) 1 [2,3,4] ... = [1,2,3,4]
となります。

Comments

[fuu]

ありがとうございました！

Answer 3

Listに対する foldr は、次のように定義されています。
（参考にしたのはこちらですが、実際にはもうちょっと効率のいい実装になっているみたいです）

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

これをご覧いただくとわかるかと思いますが、
第2引数に当たるz、つまりfuuさんが書いたコードで言うところの []は、
第3引数であるリストが空の場合、すなわちリストの要素をすべて処理しきった後に f の第2引数として渡されます。

そして、それ以外の場合、第1引数に渡した関数fに対して、
「リストの各要素」と「リストの残りの要素をfoldrした結果」を渡しています。

例えばfuuさんのコードの場合、(:)にリストの先頭の要素1と、foldr (:) [] [2, 3, 4]を渡すことになります。

リストの残りの要素については、自分の手で計算してみてください。よくわかると思います。

ちなみに、fuuさんが期待したように動作するのはfoldlの方です（第1引数に渡す関数の引数の順番が異なるので注意）。

> foldl (\accum x -> x : accum) [] [1, 2, 3, 4]
[4,3,2,1]