Menu
I've noticed there's a difference between Haskell and Erlang when it comes to foldl.
For foldr, both languages return the same results:
foldr (\x y -> 2*x+y) 4 [1, 2, 3] -- returns 49
lists:foldr(fun(X, Y) −> X+2∗Y end, 4, [1,2,3]). % returns 49
But the return values for foldl are different:
foldl (\x y -> x+2*y) 4 [1, 2, 3] -- returns 16
lists:foldl(fun(X, Y) −> X+2∗Y end, 4, [1,2,3]). -- returns 43
How can this difference be explained?
377
Haskell : foldl. Description: it takes the second argument and the first item of the list and applies the function to them, then feeds the function with this result and the second argument and so on. See scanl for intermediate results.
Only foldr is lazy and can be used for codata/infinite streams. While foldl is tail-recursive (enhanced with strict application foldl' can avoid stack overflow). This is why foldr should be used by default in Haskellin order preserve laziness across function composition.
For foldl you need to switch the argument order between acc and _ , because foldr logically puts the initial argument on the end of the sequence, while foldl puts it logically at the start. That means that the accumulator is the first (!) argument to the folding function for foldl (and the second argument for foldr ).
To recap, with foldr , the purpose of the function argument is to take the first element of the list and the results of having folded the rest of the list, and return the new value. With foldl , the function argument takes a default value, the first element of the list, and returns a new default value.
You are confusing yourself by not simplifying your fold function.
fold left, Haskell:
Prelude Debug.Trace> foldl (\x y -> trace("x:"++show x++" y:"++show y) $ x+y) 4 [1,2,3]
x:4 y:1
x:5 y:2
x:7 y:3
10
fold left, Erlang:
1> lists:foldl(fun (X,Y) -> io:format("x:~p y:~p~n", [X,Y]), X+Y end, 4, [1,2,3]).
x:1 y:4
x:2 y:5
x:3 y:7
10
fold right, Haskell:
Prelude Debug.Trace> foldr (\x y -> trace("x:"++show x++" y:"++show y) $ x+y) 4 [1,2,3]
x:3 y:4
x:2 y:7
x:1 y:9
10
fold right, Erlang:
2> lists:foldr(fun (X,Y) -> io:format("x:~p y:~p~n", [X,Y]), X+Y end, 4, [1,2,3]).
x:3 y:4
x:2 y:7
x:1 y:9
10
From this, it's clear that in Haskell, the foldl function will be passed (Accumulator, Element) while the foldr function will be passed (Element, Accumulator). On the other hand, both functions in Erlang will be passed (Element, Accumulator).
110
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
