13

There are lots of good questions and answers about foldl, foldr, and foldl' in Haskell.

So now I know that:
1) foldl is lazy
2) don't use foldl because it can blow up the stack
3) use foldl' instead because it is strict (ish)

How foldl is evaluated:
1) a whole bunch of thunks are created
2) after Haskell is done creating thunks, the thunks are reduced
3) overflow the stack if there are too many thunks

What I'm confused about:
1) why does reduction have to occur after all thunk-ing?
2) why isn't foldl evaluated just like foldl'? Is this just an implementation side-effect?
3) from the definition, foldl looks like it could be evaluated efficiently using tail-recursion -- how can I tell whether a function will actually be efficiently evaluated? It seems like I have to start worrying about order-of-evaluation in Haskell, if I don't want my program to crash.

Thanks in advance. I don't know if my understanding of the evaluation of foldl is right -- please suggest corrections if necessary.

UPDATE: it looks the answer to my question has something to do with Normal Form, Weak Normal Form, and Head Normal Form, and Haskell's implementation of them.
However, I'm still looking for an example where evaluating the combining function more eagerly would lead to a different result (either a crash or unnecessary evaluation).

Community
  • 1
  • 1
Matt Fenwick
  • 48,199
  • 22
  • 128
  • 192
  • 5
    `foldl` _is_ tail-recursive... but it turns out that in Haskell (unlike in eager languages) tail-recursion is a bad thing. – Daniel Wagner Sep 20 '11 at 17:32
  • 1
    @Daniel -- good point, I wrote that incorrectly and have edited the question to correct that. Also, thanks for clarifying that -- I had always thought of tail-recursion as unquestionably a good thing. – Matt Fenwick Sep 20 '11 at 17:43
  • @DanielWagner [Bang patterns](http://www.haskell.org/ghc/docs/latest/html/users_guide/bang-patterns.html) to the rescue! Tail-recursion can still be a good thing in Haskell. – Dan Burton Sep 20 '11 at 18:24
  • 1
    @DanBurton Yep, you bet. If you use the eager fragment of Haskell, then of course tail recursion is good there, too! – Daniel Wagner Sep 20 '11 at 18:49
  • @DanielWagner Tail-recursion is a bad thing in Haskell? Why? – MasterMastic Nov 06 '14 at 23:58
  • 1
    @MasterMastic Generally the way to get tail recursion is to have an accumulator. Combine this with laziness, and what you get by the time you make all the recursive calls is an accumulator with a very deeply-nested thunk. Boom! Stack overflow. – Daniel Wagner Nov 07 '14 at 04:50

4 Answers4

8

The short answer is that in foldl f, it's not necessarily the case that f is strict, so it might be too eager to reduce the thunks up front. However, in practice it usually is, so you nearly always want to be using foldl'.

I wrote a more in-depth explanation of how the evaluation order of foldl and foldl' works on another question. It's rather long but I think it should clarify things a bit for you.

Community
  • 1
  • 1
hammar
  • 138,522
  • 17
  • 304
  • 385
4

You know, that by definition:

foldl op start (x1:x2:...:xN:[]) = ((start `op` x1) `op` x2) ...

the line in foldl that does this is:

foldl op a (x:xs) = foldl op (a `op` x) xs

You are right that this is tail recursive, but observe that the expression 

(a `op` x)

is lazy and at the end of the list, a huge expression will have been build that is then reduced. The difference to foldl' is just that the expression above is forced to evaluate in every recursion, so at the end you have a value in weak head normal form.

Ingo
  • 36,037
  • 5
  • 53
  • 100
  • So `op` is more lazy than `foldl`? I guess it seems to me that there are multiple possible lazy evaluation orders for `foldl`, and that Haskell picks the worst one. I will read up on this 'weak head normal form' and hopefully it'll make more sense. – Matt Fenwick Sep 20 '11 at 15:50
  • 2
    To preserve semantics, foldl must indeed assume that op is lazy. See the link in hammar's answer, it is explained very well there. BTW, Haskell picks not the worst one but the correct-in-all-cases one. – Ingo Sep 20 '11 at 15:55
  • Okay, it's making more sense. But what do you mean by 'correct-in-all-cases'? That Haskell will not evaluate computations that are not used later? – Matt Fenwick Sep 20 '11 at 16:21
  • 3
    Exactly. For, when it did that, the semantics of the program would change. Consider, for example, that (42, undefined) is a perfect tuple. Haskell programs must not crash by evaluating the second component before it is absolutely needed. – Ingo Sep 20 '11 at 16:28
1

I'm still looking for an example where evaluating the combining function more eagerly would lead to a different result

The general rule of thumb is never, ever use foldl. Always use foldl', except when you should use foldr. I think you know enough about foldl to understand why it should be avoided.

See also: Real World Haskell > Functional Programming # Left folds, laziness, and space leaks

However, your question neglects foldr. The nifty thing about foldr is that it can produce incremental results, while foldl' needs to traverse the entire list before yielding an answer. This means that foldr's laziness allows it to work with infinite lists. There are also questions and answers that go into detail about this sort of thing.

Having brought that up, let me try to succinctly answer your questions.

1) why does reduction have to occur after all thunk-ing?

Reduction only occurs at strictness points. Performing IO, for example, is a strictness point. foldl' uses seq to add an additional strictness point that foldl does not have.

2) why isn't foldl evaluated just like foldl'? Is this just an implementation side-effect?

Because of the additional strictness point in foldl'

3) from the definition, foldl looks like a tail-recursive function to me -- how can I tell whether a function will actually be efficiently evaluated? It seems like I have to start worrying about order-of-evaluation in Haskell, if I don't want my program to crash.

You need to learn a little bit more about lazy evaluation. Lazy evaluation is not exclusive to Haskell, but Haskell is one of the very, very few languages in which laziness is the default. For a beginner, just remember to always use foldl' and you should be fine.

If laziness actually gets you into trouble someday, that is when you should probably make sure you understand laziness and Haskell's strictness points. You might say that said theoretical day is a strictness point for lazy-by-default learning.

See also: PLAI > Part III: Laziness

Dan Burton
  • 53,238
  • 27
  • 117
  • 198
  • I didn't mention `foldr` because, in general, it's not equivalent. But +1 for mentioning strictness points (is that an actual technical term? the series of pipes and tubes have failed me). – Matt Fenwick Sep 20 '11 at 18:37
  • I thought that I picked it up from PLAI, but glancing over it again, perhaps not. I guess I got the term from the college class where we studied PLAI. It seemed like a very natural and technical term to use; I'm surprised it is not more widespread. I'm going to take the liberty of creating a SO question about it and see if we can come up with some good explanations. – Dan Burton Sep 20 '11 at 19:09
  • Asked: [SO: What are Haskell's strictness points?](http://stackoverflow.com/questions/7490768/what-are-haskells-strictness-points) – Dan Burton Sep 20 '11 at 19:35
0

It seems like I have to start worrying about order-of-evaluation in Haskell, if I don't want my program to crash.

In my opinion, the best options if you want your program not to crash are (ranked from better to worse in terms of yield per effort spent): 1. Give it enough resources. 2. Improve your algorithm. 3. Do micro-optimisations (one of which is foldl').

So, rather that worrying about the order of evaluation I'd rather first worry about what is to be evaluated (is foldr enough? can I do without folding that at all?). And before that, I'd increase the available stack space.

You don't limit your whole program to 8MB of RAM, do you? Why would you limit the stack space then? Just increase the stack space to 4GB and start worrying when something really hogs a lot of it (like you do with heap memory).

And to somewhat answer the question of how foldl is lazy:

foldl (\x y -> y) undefined [undefined, 8] -- evaluates to 8
foldl' (\x y -> y) undefined [undefined, 8] -- fails to evaluate
Matt Fenwick
  • 48,199
  • 22
  • 128
  • 192
Rotsor
  • 13,655
  • 6
  • 43
  • 57
  • The example is there not to prove the laziness of `foldl`, but to demonstrate a situation when the laziness is needed. – Rotsor Sep 20 '11 at 17:58
  • 1
    -1 for proposing that you ignore obvious performance failures. Give it enough resources is a _user_ solution, not a _programmer_ solution. – alternative Sep 20 '11 at 19:12
  • @monadic, using lists at all is most of the time an obvious performance failure, yet that is often acceptable and even embraced. – Rotsor Sep 20 '11 at 20:03
  • @Rotsor not really. Lists have different performance characteristics than an array but not necessarily bad. For example, front-append O(1) is great. Don't spread FUD... – alternative Sep 20 '11 at 20:11
  • @monadic, one can do amortized O(1) front-append with arrays that is much faster than using linked lists. Persistent structures are a convenience coming at a cost! The same way laziness is. So, if you call "lists are bad" FUD, I call "laziness is bad" FUD. – Rotsor Sep 20 '11 at 20:21
  • @Rotsor When did I insult laziness? Its just that a medium is necessary. Amortized O(1) front-append with arrays doesn't exist in haskell without ST because you would have to copy the array every time. – alternative Sep 20 '11 at 20:23
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/3639/discussion-between-rotsor-and-monadic) – Rotsor Sep 20 '11 at 20:25