foldr と無限リスト

昨日の IO () さんのコメントから。

 cf. id:takatoh:20060514:myInits

えーと,つまり foldl は無限リストを扱えないけど, foldr は扱えるってことだな。foldl を使った版の myInits がダメだったのは last じゃなくて foldl のせいだってことだ。

それより,foldr は無限リストを扱えるって?

Prelude> foldr (:) [] [1..]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,3
0,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,
57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83
,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107

うわ,ホントだ。なんでだ。リストの右(後ろ)から評価するんじゃないのか。
うーん,”Yet Another Haskell Tutorial”を読んでみようか。英語は苦手なんだがなぁ……と思ったら id:moi2 さんのところに翻訳がある。ありがたい。該当個所はこのあたりか。

この中に foldr の評価過程の例がある。

foldr (-) 1 [4,8,5]
==> 4 – (foldr (-) 1 [8,5])
==> 4 – (8 – foldr (-) 1 [5])
==> 4 – (8 – (5 – foldr (-) 1 []))
==> 4 – (8 – (5 – 1))
==> 4 – (8 – 4)
==> 4 – 4
==> 0

上の例をこれと同じようにしてみると

foldr (:) [] [1..]
==> 1:(foldr (:) [] [2..])
==> 1:2:(foldr (:) [] [3..])
==> 1:2:3:(foldr (:) [] [4..])
==> 1:2:3:4:(foldr (:) [] [5..])
(以下無限に続く)

こんな感じになるはずで,無限リストを扱えるようには思えない。
いや,そうか,リストだから遅延評価されるんだ。だからうまくいくってことか。
ということは結果がリストにならないような場合にはうまくいかないはず。

Prelude> foldr (+) 0 [1..]
*** Exception: stack overflow

やっぱり。

カテゴリー: Haskell パーマリンク

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください