CODEWITHSUNDEEP
haskellfunctional-programming
placeholder223
placeholder223

Reputation: 1

I'm getting confused about foldl and foldr in haskell

(\x acc -> acc + x*2) 0 I have this lambda for a fold function. If I use foldr, it returns the sum of the double of each element, as expected.

If I use foldl, it returns the sum of x*(2^pos_x) starting from the right and I have no idea why. Shouldn't they do the same thing in this case, but starting from different ends in the list?

Upvotes: 0

Views: 122

Answers (2)

chepner
chepner

Reputation: 532428

foldl and foldr take functions of different types:

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
                       ^^^^^^^^^^^^^

The function given to foldr expects the accumulator as its second argument, while the function given to foldl expects the accumulator as its first argument.

If you have a function suitable for foldr, you can adapt it using the flip :: (a -> b -> c) -> (b -> a -> c) function:

> f x acc = acc + x*2
> foldr f 0 [1,2,3]
12
> foldl (flip f) 0 [1,2,3]
12

Upvotes: 1

141592653
141592653

Reputation: 723

In foldl, the accumulator is the first argument of the folding function while in foldr it's the second argument. Consequently if you want to obtain the same result with foldl you should use the following function instead :

\acc x -> acc + x*2

Please note that here, you should get the same result, because the operator you use is commutative and associative, but it's not always the case.

Upvotes: 4

Related Questions