5

I've been learning Haskell recently and came across something I don't quite understand: the parameters of a lambda function.

In the Learn You a Haskell for Great Good book, chap. 5, there are the following two functions:

elem' :: (Eq a) => a -> [a] -> Bool
elem' y ys = foldr (\x acc -> if x == y then True else acc) False ys

reverse' :: [a] -> [a]
reverse' = foldl (\acc x -> x : acc) []

In the first function, the accumulator is listed as the lambda's second parameter, but then is the first to follow the lambda for foldl, which I took to mean it would be the first, not the second, thus, defying expectations.

Whereas, in the second function, it follows expectations, showing up as the lambda's first parameter, making the list that reverse' takes as a parameter the second for the lambda.

I tested both functions and they work as expected. I also noticed that one function involves a right fold and the other a left fold, but I'm not sure why that would alter the meaning of the parameters.

QUESTION: Can someone explain what I'm missing? Why are the parameters seeming to swap places?

Improve this question

2 Answers 2

Reset to default
10

foldl and foldr expect the accumulating function to have different formats. The two functions have the following types:

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

You're correct that in foldr, the accumulator is the second argument, and in foldl it's the left.

While this may seem unintuitive, it may help to think of foldl and foldr in terms of how they associate values in a list, the following images come from the "fold" page on the Haskell wiki:

Treating the natural order of the list as left to right: In foldr, the accumulator starts at the right hand side of the list, so it's natural that it's the second argument, while in foldl, the opposite is true.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Makes sense. I also learned I need to scrutinize the function signature in the future. Thanks.
hoogle (hoogle.haskell.org) is a great resource for quickly investigating type signatures, (as is :t in ghci)
3

It is just a convention that the accumulator in foldr is the second argument, and in foldl it is the first argument.

Why was this convention chosen?

  1. The first reason was answered by @Joe. acc is the folded part of the list. In foldl it's left part but in foldr it's right part. So it's natural to provide acc as left operand (the first argument) to folding operator in foldl and as right operand (the second argument) to folding operator in foldr.

  2. foldl should iterate over all the elements in the provided list, while foldr should not. You can provide folding operator to the foldr which can skip rest of elements in the list. The first example does that. The second argument acc in the foldr is thing which is not computed yet, it hold folding the rest of elements. And if you skip it in your folding operator it never be computed. In your example, if x == y you just "return" True (and skip rest elements), else you "return" acc which force to evaluate the next element in the list. So, foldr works lazyly, but foldl works strictly.

  3. In Haskell is another convention. When operator can works lazyly then it usually have the first argument with strict semantic and the second with non strict. For example: &&, || are this sort of operators.

    False && undefined => False
True || undefined => True

    Folding operator in your the first example is lazy too.

    (\x acc -> if x == y then True else acc) y undefined => True

    And it can be rewrite in terms of || like this:

    (\x acc -> x == y || acc)

Combining above reasons together we have what we have :-)

Improve this answer

7 Comments

I wouldn't really say it's a convention. It is an unarguable part of the definitions of foldl and foldr. Unlike, say, the convention of naming a list variable xs, you can't go against it if you disagree: you will get a type error, because that is how the functions are defined to work. You may argue that it was a convention to define foldl and foldr in this way, But if this is the case you are making, you should say so.
The lazy evaluation justification makes a lot of sense. Thanks!
@amalloy I wouldn't really say it's an unarguable part of the definitions. You can rewrtite foldr which will be have the type like foldl (or wise versa). I agree that it was convention to define foldl and foldr in this way. But I think on which kind of level was convention is not matter for answer on this question.
foldl is not strict, contrary to what you might expect. For a strict left fold, you need foldl' (note the trailing prime/apostrophe). This is a common pitfall.
@freestyle You could rewrite them as you describe, but then they would not be foldr and foldl. They would be very similar functions, but different, defined differently, and incompatible.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.