昨日の 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
やっぱり。
