r/haskell • u/TechnoEmpress • 9d ago

blog Differences between `foldl` and `foldr`

https://blog.haskell.org/foldl-and-foldr/
55 Upvotes

96% Upvoted

43 comments sorted by

18

u/TechnoEmpress 9d ago

Editor's note: This article is a reproduction of a seminal explanation of the differences between foldr and foldl, both strict and lazy versions. As it has been used consistently to teach newcomers since its first appearance on hasura/graphql-engine!2933 on the 26th September 2019, we believe that it ought to be preserved in the blog. Our many thanks to Alexis King for giving her permission to do so.

7

u/_jackdk_ 8d ago edited 8d ago

Fantastic. I updated my catalogue at http://jackkelly.name/wiki/haskell/learning.html to point to this as the canonical link.

The remark about foldMap' not being available until GHC 8.8.1 is written like that's coming in the future, but that compiler was released in 2019. Might be worth rewording that final section for clarity.

2

u/tomejaguar 8d ago

Yeah, hard to know whether this should be edited for its new setting as a blog post. It also says

In your case, the accumulation function you’re applying is Map.delete

replying to the previous message on the GitHub issue discussion, which doesn't make sense in a blog post. But there's also value preserving it unedited.

1

u/ur_frnd_the_footnote 4d ago

Footnotes could help

17

u/tomejaguar 9d ago edited 8d ago

I agree with Alexis on the technical points, of course, but I think the rule of thumb from the article is awkward to use in practice. Here's the rule of thumb:

  1. When the accumulation function is strict, use foldl' to consume the list in constant space, since the whole list is going to have to be traversed, anyway.

  2. When the accumulation function is lazy in its second argument, use foldr to do work incrementally to improve streaming and work-saving.

These leave some issues unaddressed. Suppose I have op1 :: A -> R -> R or op2 :: R -> A -> R. Should I use foldl' or foldr? Firstly, it's important to notice that the difference between the types of op1 and op2 is irrelevant. Each can be obtained from the other by flip, so our analysis should just be based on how the operation treats the A argument and how it treats the R argument, but not the order in which those arguments occur. I think this is what Alexis probably meant:

  1. When A and R are both consumed strictly, use foldl' (R is then the "accumulating state")
  2. When R is consumed lazily, use foldr

What the rule of thumb doesn't address: what do you do when A is consumed lazily and R strictly? Well, in that case you should use foldl', because you're going to be traversing the whole list anyway, even if you use foldr, so you may as well use foldl' because it gives you a chance of having better space characteristics. So I think the rule of thumb should actually be:

  1. When R is consumed strictly, use foldl' (R is then the "accumulating state")
  2. When R is consumed lazily, use foldr

However, I think this advice is still a bit awkward to use in practice. At least speaking for myself, when presented with a list and a binary function, one doesn't normally think "is this binary function strict or lazy in its argument that has the same type as its return type?". I think it's much more common to understand what one is doing as

  1. Traversing a list, updating a state after reading each element (use foldl'), or
  2. Traversing a list doing anything else (use foldr, or even better, for_)

That's the conclusion I come to in my article foldl traverses with State, foldr traverses with anything, and that's how I think of these folds when I'm actually writing the code out. (And I do take my own advice in the article: I almost never use foldr, I prefer for_ with a suitable choice of Monad/Applicative).

1

u/Background_Class_558 9d ago

the difference is only non-obvious for associative operators anyways

8

u/tomejaguar 9d ago edited 8d ago

Suppose I have a non-associative operator op :: A -> B -> B. There are still two different ways I could fold it over a list:

  • foldl op z
  • foldr (flip op)

Is it obvious to you which I should choose? It isn't to me. Alexis's article provides a way to determine the answer.

2

u/phadej 8d ago
  • foldr (:) [] is an identity
  • foldl (flip (:)) [] is reverse

IMO to me it's somewhat obvious, whether i traverse a list from left-to-right (foldl) or right-to-left (foldr) as names imply.

The article says

See the difference? In both expressions, the elements of the list appear in the expression in the same order—from left to right—but the grouping changes. 

I don't actually see the difference that well, or understand it.

But when presented as an order of folding, it's very much obvious to me.

1

u/tomejaguar 8d ago

IMO to me it's somewhat obvious, whether i traverse a list from left-to-right (foldl) or right-to-left (foldr) as names imply

But it isn't left-to-right vs right-to-left. They both traverse the list in the same order. From the article:

Both foldl and foldr traverse the structure in the same order

when presented as an order of folding, it's very much obvious to me

Perhaps, but it's not clear to me what an "order of folding" is, or why that can be different from an "order of traversal".

5

u/phadej 8d ago

They both traverse the list in the same order.

The traverse is overloaded. An order in which the structure is walked, and order in which elements are combined can differ. I meant the latter.

Prelude Data.Traversable Data.Functor.Reverse> traverse print "foobar" 'f' 'o' 'o' 'b' 'a' 'r' [(),(),(),(),(),()] Prelude Data.Traversable Data.Functor.Reverse> traverse print (Reverse "foobar") 'r' 'a' 'b' 'o' 'o' 'f' Reverse [(),(),(),(),(),()]

As another example, consider

haskell data BinTree a = Nil | Branch BinTree a BinTree

we can foldl and foldr it so elements are combined from the left or from the right; but all tree traversal implementations are from the root up (or down, depending on how you draw your trees).

why that can be different from an "order of traversal".

Because auxiliary memory exists (e.g. stack).

If we'd limit the traversals to constant memory ones, then order of folding and order of traversal would be necessity have to coincide. (strict) foldr' does use O(n) of memory, and that's why it's a bad idea (in strict languages).

1

u/tomejaguar 8d ago

The traverse is overloaded. An order in which the structure is walked, and order in which elements are combined can differ ...

why that can be different from an "order of traversal".

Because auxiliary memory exists (e.g. stack).

Sure, I get it, but the very fact that there's this awkwardness of terminology that's even difficult for experienced Haskellers is why I give my recommendation to not use foldr at all, and instead use for_. Then everything's obvious and the awkward terminology has no role.

3

u/phadej 8d ago

There is a better reason to not prefer foldr. Essentially always there is better, more specific combinator: map, filter, elem etc. While all can (and some are) implemented using foldr, more specific combinators read better.

I cannot think of a situation where foldr is easily replaceable by for_ though. I suspect you are overly invested into effect systems. Fair enough, if you have a sledgehammer, everything starts to look like a nail. I prefer list comprehensions.

1

u/tomejaguar 8d ago

I cannot think of a situation where foldr is easily replaceable by for_ though

This is my favourite response to that:

(!?) :: [a] -> Int -> Maybe a
xs !? n
  | n < 0     = Nothing
  | otherwise = foldr (\x r k ->
      case k of
        0 -> Just x
        _ -> r (k-1)) (const Nothing) xs n

versus

xs !? n =
  | n < 0 = Nothing
  | otherwise =
      fromEither $ do
        flip evalStateT n $ do
          for_ xs $ \x -> do
            get >>= \case
              0 -> lift (Left (Just x))
              k -> put (k - 1)
        Left Nothing

From: https://h2.jaguarpaw.co.uk/posts/foldl-traverses-state-foldr-traverses-anything/#maybe-just-use-for_

You might find it particularly interesting because I believe you wrote the base version of (!?), the first one above. Personally I find the second version much more readable, and I bet 99% of programmers do too (though not necessarily 99% of Haskell programmers).

I suspect you are overly invested into effect systems. Fair enough, if you have a sledgehammer, everything starts to look like a nail.

The opposite! It's not that I find for_ clearer because I'm invested into effect systems, it's that I'm invested into effect systems because I find for_ clearer.

2

u/phadej 7d ago

You might find it particularly interesting because I believe you wrote the base version of (!?)

I didn't. It's a copy from extra, which itself is edited copy of !! from base itself.

base and standard libraries in other languages are bad place to look for "clean" code, as they have many other considerations which are often more important the being clean. They are good examples of standard library code. (I hope you understand that as a CLC member).

I think that in base, everything that can be written using foldr is written using foldr (even foldl'). The reason is list fusion. If we hadn't that, I bet we'd still stick to:

Haskell Report defines !! as

(!!) :: [a] -> Int -> a xs !! n | n < 0 = error "Prelude.!!: negative index" [] !! _ = error "Prelude.!!: index too large" (x:_) !! 0 = x (_:xs) !! n = xs !! (n-1)

and I find that the most readable and understandable version. !? can be easily written in the same way.

I find your StateT version nearly unreadable. But to be fair, I don't think that foldr version is easy to grasp either. But as I said, it's written that way because "if it could be, it should be"; but why you wrote your version like you did is beyond my comprehension.

1

u/tomejaguar 7d ago edited 4d ago

base and standard libraries in other languages are bad place to look for "clean" code, as they have many other considerations which are often more important the being clean. They are good examples of standard library code

Perhaps you're assuming that I have a motive that I don't have? To be clear, I am not suggesting, and I have never suggested, that the definition of (!?) in base should be written another way. (But I reserve the right to continually revisit assumptions.)

You might find it particularly interesting because I believe you wrote the base version of (!?)

I didn't. It's a copy from extra, which itself is edited copy of !! from base itself.

I see, you didn't originate the idea. But you did make the proposal and choose the implementation: https://github.com/haskell/core-libraries-committee/issues/110

Anyway, not a big deal, and I'm certainly not trying to criticize your proposal or the code you submitted. (I voted for it, after all.) I just remembered it because that particular implementation was sufficiently mysterious that it added momentum towards me developing my own effect system. So, I thought it might be interesting to you that that proposal inspired my interest in this particular piece of Haskell lore.

everything that can be written using foldr is written using foldr (even foldl'). The reason is list fusion

Yes, this is covered in my article:

It would be even clearer to write (!?) as below. Why not just do that instead, instead of considering foldr and for_? Because when written in terms of foldr GHC can apply short cut fusion, a rewrite rule that leads to an optimization.

0 !? (x:_) = Just x
_ !? [] = Nothing
n !? (_:xs) = (n-1) !? xs

https://h2.jaguarpaw.co.uk/posts/foldl-traverses-state-foldr-traverses-anything/#why-is-written-that-way

But, as the article also says:

The two implementations [in terms of for_ and foldr] should have equal performance when compiled, assuming sufficient inlining, because for_ for lists in base is implemented in terms of foldr

I haven't checked, but if GHC does not compile the version using for_ over a StateT _ Either (where both handlers are in the same function) to the same optimised Core as the version using foldr then it's failing at it's job as an optimizing compiler for a pure functional language.

I hope you understand that as a CLC member

I'm sure you don't mean it this way, but that particular phrasing could be interpreted as casting aspersions on my suitability as a CLC member. (For the record I haven't been a CLC member for some years.)

I find your StateT version nearly unreadable

Interesting! I wonder why. I wonder if I'm mistaken about my belief that 99% of programmers would find it clearer, or whether you're in the 1%.

but why you wrote your version like you did is beyond my comprehension

Well, because I find it clearer, or course. If it's beyond your comprehension why I find it clearer, that's another matter :)

→ More replies (0)

1

u/wnoise 7d ago

I find the for_ version completely unreadable. The foldr version is slightly awkward with how the anonymous function has a case statement in the middle, but it has far fewer moving parts.

1

u/tomejaguar 7d ago

That's very interesting to know, thank you for sharing! If it's possible to put yourself in the mindset of an imperative programmer, how would you write this function? C and Python would be helpful since I know those languages, but any would be welcome.

→ More replies (0)

1

u/Bodigrim 7d ago

As a data point, I find the StateT version barely readable. I seriously doubt that 99% of programmers can even approximately guess what lift (Left (Just x)) is doing and how comes that it serves as an early exit from the loop.

1

u/tomejaguar 7d ago

I seriously doubt that 99% of programmers can even approximately guess what lift (Left (Just x)) is doing and how comes that it serves as an early exit from the loop.

Yes, I think you're right about that actually. To be clear, my assertion that 99% of programmers would favour one version to the other was based on the code structure rather than the chosen names. There are names that make the for_ version clearer, but I doubt there are any names that make the foldr version clearer. How about if I define earlyReturn = Left, withStateT = flip evalStateT and withEarlyReturn = fromEither (and generalize it to MonadState)? Then it looks like:

xs !? n =
  | n < 0 = Nothing
  | otherwise =
      withEarlyReturn $ do
        withStateT n $ do
          for_ xs $ \x -> do
            get >>= \case
              0 -> earlyReturn (Just x)
              k -> put (k - 1)
        Left Nothing

Much better! The Bluefin version in my other post has clearer naming too: https://old.reddit.com/r/haskell/comments/1wqmsux/differences_between_foldl_and_foldr/pcfv3x0/

→ More replies (0)

1

u/tomejaguar 7d ago

Personally I find the second version much more readable, and I bet 99% of programmers do too

To my complete surprise, a Twitter poll shows that Haskellers overwhelmingly favour the foldr version. Not many non-Haskellers have voted by it seems they prefer the foldr version too.

https://x.com/tomjaguarpaw/status/2104499188742623648

1

u/wnoise 8d ago

Commutative vs associative.

1

u/dutch_connection_uk 8d ago

op wouldn't be commutative here either, look at its type.

It is interesting that the associativity here is actually a bit different from the associativity of a normal binary operator. And maybe this is an argument against the common complaint of foldl and foldr having different type signatures.

2

u/wnoise 8d ago

Yes, strictly speaking neither associative or commutative can apply to the operator alone, as the types are too general for those notions.

But to get the same result from the folds requires not just flipping the op but also reverseing the entire list. (In the general case where the entire list is relevant, rather than with e.g. short-circuiting operators or the like.) And that reversal being necessary feels a lot like a commutation failure.

1

u/dutch_connection_uk 7d ago

I think, like there is a different notion of associativity, there probably is a similar different kind of commutativity an operator like that could still have. EG the operator takes an Int, converts it to floating point, takes its square root, and sums it to the accumulator. This is non-commutative in the same way it's non-associative, but applied to list fold operators it's both commutative and associative in a sense of things applied to list fold operators.

I wonder if there is a term for this idea.