haskell中 foldr 與foldl的差別？

01-14

我先來帖一下自己想像中的現實
foldl acc zero [] = zero
foldl acc zero (x:xs) = foldl acc (acc zero x) xs

foldr acc zero [] = zero
foldr acc zero (x:xs) = acc x (foldr acc zero xs)

從上面來看，foldl為迭代實現，而foldr為遞歸實現
在實踐中我用foldl比較多
我問題是：
1. haskell內部的foldl與foldr是否採用上面類似的實現？
2.foldr能實現的功能foldl也可以實現嗎？（憑直覺來說是這樣的）

a.舉個例子： sum = foldl (+) 0 sum" = foldr(+) 0
3.foldr 與foldl都有什麼優缺點，分別適用於什麼情況？

https://wiki.haskell.org/Foldr_Foldl_Foldl"

官網例子如下

&> foldr f z [] = z &> foldr f z (x:xs) = x `f` foldr f z xs


&> sum1 = foldr (+) 0

&> try1 = sum1 veryBigList

If we evaluate try1 we get:

*** Exception: stack overflow

Too bad... So what happened:

try1 --&> sum1 veryBigList --&> foldr (+) 0 veryBigList --&>


foldr (+) 0 [1..1000000] --&>

1 + (foldr (+) 0 [2..1000000]) --&>

1 + (2 + (foldr (+) 0 [3..1000000])) --&>

1 + (2 + (3 + (foldr (+) 0 [4..1000000]))) --&>

1 + (2 + (3 + (4 + (foldr (+) 0 [5..1000000])))) --&>

-- ...

-- ...  My stack overflows when there"s a chain of around 500000 (+)"s !!!

-- ...  But the following would happen if you got a large enough stack:

-- ...

1 + (2 + (3 + (4 + (... + (999999 + (foldr (+) 0 [1000000]))...)))) --&>

1 + (2 + (3 + (4 + (... + (999999 + (1000000 + ((foldr (+) 0 []))))...)))) --&>
1 + (2 + (3 + (4 + (... + (999999 + (1000000 + 0))...)))) --&>

1 + (2 + (3 + (4 + (... + (999999 + 1000000)...)))) --&>

1 + (2 + (3 + (4 + (... + 1999999 ...)))) --&>
1 + (2 + (3 + (4 + 500000499990))) --&>

1 + (2 + (3 + 500000499994)) --&>

1 + (2 + 500000499997) --&>

1 + 500000499999 --&>

500000500000
Good Lord! Again a stack overflow! Lets see what happens:
try2 --&>

sum2 veryBigList --&>

foldl (+) 0 veryBigList --&>
foldl (+) 0 [1..1000000] --&>
let z1 =  0 + 1

in foldl (+) z1 [2..1000000] --&>
let z1 =  0 + 1

    z2 = z1 + 2

in foldl (+) z2 [3..1000000] --&>
let z1 =  0 + 1

    z2 = z1 + 2

    z3 = z2 + 3

in foldl (+) z3 [4..1000000] --&>

let z1 = 0 + 1 z2 = z1 + 2 z3 = z2 + 3 z4 = z3 + 4 in foldl (+) z4 [5..1000000] --&>

foldr能處理某些具有短路運算的無限數據結構

foldl和foldr，一個是從左邊干到右邊，一個是從右邊干到左邊。對於+這種滿足結合律的函數來說，當然選哪個都可以。