読者です 読者をやめる 読者になる 読者になる

haskellでなぜfoldrだと無限リストが扱えてfoldlだと扱えないのか

畳込関数fold:foldrとfoldlの違い (あるいはfold_right, fold_left) - 一歩前進
無限リストをfoldrで扱う(foldlでは扱えない)


haskellは遅延評価が特徴。
式の評価は外側から行う。
つまり外側の評価をするその時に内側の結果が必要なら計算する。

算数で例えると

(1 + (2 * 3))

という計算の場合は、外側の1 + の部分を計算するためには(2 * 3)の結果が必要なので、しゃーなしにその時に(2 * 3)を計算するみたいな感覚っぽい。

なので

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


のような場合だと
foldlの場合は一番外側の式がxnの計算、つまり無限の終端を対象とする計算になってしまうので計算不可能。
foldrの場合は、一番外側がx0でリストの最初の数を対象にしているので計算(を開始することは)可能。

ということみたい。

試しにGHCIで

Prelude> foldl (+) 0 [1..]

は返ってこない

Prelude> foldr (+) 0 [1..]
[2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,98,100,102,104,106,108,110,112,114,116,118,120,122,124,126,128,130,132,134,136,138,140,142,144,146,148,150,152,154,156,158,160,162,164,166,168,170,172,174,176,178,180,182,184,186,188,190,192,194,196,198,200,202,204,206,208,210,212,214,216,218,220,222,224,226,228,230,232,234,236,238,240,242,244,246,248,250,252,254,256,258,260,262,264,266,268,270,272,274,276,278,280,282,284,286,288,290,292,294,296,298,300,302,304,306,308,310,312,314,316,318,320,322,324,326,328,330,332,334,336,338,340,342,344,346,348,350,352,354,356,358,360,362,364,366,368,370,372,374,376,378,380,382,384,386,388,390,392,394,396,398,400,402,404,406,408,410,412,414,416,418,420,422,424,426,428,430,432,434,436,438,440,442,444,446,448,450,452,454,456,458,460,462,464,466,468,470,472,474,476,478,480,482,484,486,488,490,492,494,496,498,500,502,504,506,508,510,512,514,516,518,520,522,524,526,528,530,532,534,536,538,540,542,544,546,548,550,552,554,556,558,560,562,564,566,...

で一応実行できる。