# Thinking about folds

**URL:** <https://discourse.elm-lang.org/t/thinking-about-folds/4361>\
**Category:** Request Feedback\
**Created:** [September 23, 2019, 6:11pm UTC](https://discourse.elm-lang.org/t/thinking-about-folds/4361 "2019-09-23T18:11:39Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![mzero](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/mzero/32/674_2.png) [@mzero](https://discourse.elm-lang.org/u/mzero)\
**Post date:** [September 23, 2019, 6:11pm UTC](https://discourse.elm-lang.org/t/thinking-about-folds/4361/1 "2019-09-23T18:11:39Z")

</div>

**Yesterday, I found myself helping to explain folds** on the Slack. Someone was trying to understand the difference between `foldr` and `foldl`, again. This is not unexpected: Those new to functional programming need to learn how to stop thinking in imperative loops and start using higher level functions like folds.

As always, I want to illustrate how to think about the folds like so (this is math notation, not code):

> _foldr_⊕,z ([a, b, c, d]) = (a ⊕ (b ⊕ (c ⊕ (d ⊕ z))))  
> _foldl_⊕,z ([a, b, c, d]) = ((((z ⊕ a) ⊕ b) ⊕ c) ⊕ d)

These definitions make it clear how one groups to the right, the other to the left. You can see that for many operations (like append, +, \*) with the appropriate _z_ value, these two produce the same result.¹

It’s also pretty easy for people to grasp why, when folding over a list, walking the list from the head (as system must), _foldl_ is efficient, becoming a simple loop, and _foldr_ is recursive, to the depth of the list.²

**This is not how it is in Elm.** In Elm we have:

```auto
foldr ⊕ z [a, b, c, d] = (a ⊕ (b ⊕ (c ⊕ (d ⊕ z))))
foldl ⊕ z [a, b, c, d] = (d ⊕ (c ⊕ (b ⊕ (a ⊕ z))))

```

Which I argue is a little harder to see what’s going on, breaks the _foldr_ / _foldl_ equivalence, and requires a few more steps to see why one is a plain loop and not the other.

I presume the choice was made to avoid the _other_ difficulty in learning and using folds: The order of the arguments to the combining function.

Based on the mathematical definitions, Haskell’s functions have these type signatures:

```auto
foldr :: (a -> b -> b) -> b -> [a] -> b
foldl :: (b -> a -> b) -> b -> [a] -> b

```

Even I, after over a decade of Haskell coding, still have to stop and think for a second when coding if I need to flip my combining function’s args or not.³

You might think that Elm’s definitions would eliminate that mental bump because there’s only one signature to remember:

```auto
foldr : (a -> b -> b) -> b -> List a -> b
foldl : (a -> b -> b) -> b -> List a -> b

```

But I find it doesn’t: I still have to stop and think for a second about which way things are going, is that the direction I want, can/should I use the other fold, and is my combining function defined with the arguments in the needed order. I bet you do, too.

**Which leads us to consider:** Which form of `foldl` is better?

Many useful combining functions match `a -> b -> b`:

```auto
Set.insert : a -> Set a -> Set a
List.(::) : a -> List a -> List a

```

And common things one writes are often in this form:

```auto
\item model -> { model | filter = Dict.insert item True filter }
\(k, v) -> Dict.update k (Just << Maybe.Extra.unwrap [v] ((::) v))

```

These are reduction operations. In general one usually doesn’t care what order the list is traversed, and it is conventional for the reduction operations to have the form `(a -> b -> b)`. Hence, `foldl` and `foldr` taking the same combining function is useful.

**On the other hand,** there are common combining operations that generally have the form `a -> a -> a`⁴

```auto
Dict.union : Dict k v -> Dict k v -> Dict k v
(++) : a -> a -> a

```

When using these, there is an important order to the first two arguments. And so, in Elm, choosing `foldr` vs. `foldl` not only chooses the order or traversal, _but also the order of arguments to the combining function._

```auto
concat listOfLists = foldr (++) [] listOfLists
oddConcat listOfLists = foldl (++) [] listOfLists

> concat[[1, 2, 3], [4], [], [5, 6] ]
[1,2,3,4,5,6]
> oddConcat [[1, 2, 3], [4], [], [5, 6] ]
[5,6,4,1,2,3]

```

For many (most?) uses, the ordering that `foldr` uses is natural (it is _left-biased_). However, it is often both conceptually, and efficiently, desirable to use `foldl` - It makes sense to “proceed down the list” merging the elements. Hence, `foldl`’s swapped combining function arguments makes sense.

**Given both are useful, just pick one, right?** Perhaps. In Haskell, it is common to use the function `flip`, and it is part of the standard library, always available unqualified. It isn’t uncommon to see things like:

```auto
foldl' (flip Set.insert) Set.empty flagList

```

Since it is very easy to use a combining function of either form, with either fold, Haskell chooses the order it has, and it works just fine for all uses.

But Elm doesn’t have `flip`, and it seems small utility higher order functions are eschewed, so if `foldl` were defined as in Haskell, you’d have to write:

```auto
List.foldl (\s f -> Set.insert f s) Set.empty flagList

```

Reading that use of `Set.insert` requires a higher mental burden than the modest `flip`. You have to stop for a moment when you read that lambda. Which, I’m guessing, is what Elm’s definition of `foldl` is trying to avoid.

**So, both?**

Which leads me to this proposal. In the next major upheaval of the core libraries, define:

```auto
foldr : (a -> b -> b) -> b -> List a -> b
foldl : (b -> a -> b) -> b -> List a -> b
reduce : (a -> b -> b) -> b -> List a -> b

```

Where `reduce` is a left fold, but with the combining function in the order shown.

I know that we like having a minimal core, and that two ways to do something is not “the Elm way”… but, hear me out:

Now the library addresses two situations that programmer’s encounter:

1. Reduction operations - for these `reduce` is the natural choice both because of the common combining function definitions, and from efficiency point of view.
2. Merging operations - for which there are two natural choices, `foldr` and `foldl`, that match the associative meaning of these operations, and work well for merging functions.

**If nothing else,** even if this proposal goes nowhere, I hope you find this exploration of the order of arguments to folds enlightening.

— Mark

* * *

¹ Technically, for monoids, which are by definition associative and have a zero element that is commutative, _foldr_ and _foldl_ always produce the same result. I hesitate to say “monoid”, as it seems to worry people I’m getting too Haskelly… but “monoid” is what the concept is, and programmers of all types use monoids day in and day out without seeing the common pattern because we don’t name it. So - let’s not be scared of odd words: “monoid” is what it is!

² The Elm implementation of `foldr` will, after a depth of about 4k, decide to instead reverse the list, and then use `foldl` for the rest. It also has unrolled the recursion 4× so that the maximum depth it 1000. Of course, these details don’t belong in a discussion of folds for those new to functional programming.

³ The mnemonic I use, and teach, is “In fold **r** the _z_ slides in from the **right**. With fold **l** it slides in from the **left**.”

⁴ Operations that are part of a monoid. But I’m trying hard not to say that word in the main part of the post!

---

<div class="post-metadata">

**Author:** ![avh4](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/avh4/32/97_2.png) [@avh4](https://discourse.elm-lang.org/u/avh4)\
**Post date:** [September 23, 2019, 8:25pm UTC](https://discourse.elm-lang.org/t/thinking-about-folds/4361/2 "2019-09-23T20:25:39Z")

</div>

Nice analysis!

To contribute to the questions raised, I figured I’d briefly add how I’ve come to think about the folds in Elm:

Having come to Elm before having any background in haskell or in mathematical folds, I personally find it simpler to have both `foldl` and `foldr` have the same signature; in both cases, it’s one-by-one incorporating an element into the accumulator. I find a bigger mental bump when looking at haskell-style foldl since I find it easier to think about incorporating items into an accumulator in some order (where having the same signature makes sense) than to think about unrolling the fold into an equivalent mathematical expression (where I agree the different signature does make more sense).

The mnemonic I use is “foldl: fold _from_ the left”, “foldr: fold _from_ the right” (note that in Elm \<=0.15, there was also “foldp: fold _from_ the past” for use with Signals) – meaning with foldl the leftmost item is incorporated first; and with foldr, the rightmost is first (from which can be deduced that it must require space overhead to dig in to the bottom of the list to start iterating).

---

<div class="post-metadata">

**Author:** ![lydell](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/lydell/32/178_2.png) [@lydell](https://discourse.elm-lang.org/u/lydell)\
**Post date:** [September 24, 2019, 4:12pm UTC](https://discourse.elm-lang.org/t/thinking-about-folds/4361/3 "2019-09-24T16:12:02Z")

</div>

Coming from JavaScript, I’m used to `Array.prototype.reduce` and `Array.prototype.reduceRight` having the same signature. I had no idea that Haskell had different signatures for `foldl` and `foldr` before reading this thread! At first I was shocked – it sounds so easy to mess up, or to be confused about. Now I see that there’s some mathsy stuff that can motivate it, but I don’t quite understand it yet.

To me, `.reduce` and `foldl` has always meant “go through the list from left to right and build something up along the way”. I almost always use `.reduce` and `foldl`. A couple of times, the thing I’ve built up along the way required starting from the right, so then I used `.reduceRight` or `foldr`. So personally I’ve never had a problem with Elm’s `foldl` and `foldr`, but now I’m intrigued to learn more about folds in a new light.

---

<div class="post-metadata">

**Author:** ![mzero](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/mzero/32/674_2.png) [@mzero](https://discourse.elm-lang.org/u/mzero)\
**Post date:** [September 24, 2019, 4:34pm UTC](https://discourse.elm-lang.org/t/thinking-about-folds/4361/4 "2019-09-24T16:34:37Z")

</div>

Thank you both, @avh4 and @lydell for your replies.

They both illustrate that one common way of think of these operations is _reduction_, or as @lydell put it:

> [@lydell](#):
>
> “go through the list from left to right and build something up along the way”

From this view, there is almost never a reason to go other than left to right (or really, from the head to tail). And as we all see, the argument order for the combining function is naturally `a -> b -> b`. Hence why I suggest we call this operation `reduce`.

It is the other user, _merging_ that other way of defining `foldl` comes into play. To extend @lydell’s style of description, Merging is

> lining up all the items in the list side by side and merging them together in pairs, either from the left or from the right

---

<div class="post-metadata">

**Author:** ![rupert](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/rupert/32/1775_2.png) [@rupert](https://discourse.elm-lang.org/u/rupert)\
**Post date:** [September 24, 2019, 9:54pm UTC](https://discourse.elm-lang.org/t/thinking-about-folds/4361/5 "2019-09-24T21:54:18Z")

</div>

I can definitely see how this is annoying coming from Haskell.

I do like that the signatures of `foldl` and `foldr` are identical, in that it makes it easy to change from one to the other by changing the `l` or `r` about. Say in some complex algorithm you lose track of which way round you are doing something and get the answer backwards, usually fixed by switching over the fold direction.

---

<div class="post-metadata">

**Author:** ![opvasger](https://avatars.discourse-cdn.com/v4/letter/o/8e8cbc/32.png) [@opvasger](https://discourse.elm-lang.org/u/opvasger)\
**Post date:** [September 25, 2019, 12:32pm UTC](https://discourse.elm-lang.org/t/thinking-about-folds/4361/6 "2019-09-25T12:32:58Z")

</div>

The confusion for me used to be in choosing between foldl and foldr. If they were named differently, for example `fold` and `foldRight`, I think intuition would build up more naturally.

List-operations are naturally head to tail. That would be the case for `fold`.

I like “reduce” from javascript, but “folding” feels really intuitive to me.

---

<div class="post-metadata">

**Author:** ![lydell](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/lydell/32/178_2.png) [@lydell](https://discourse.elm-lang.org/u/lydell)\
**Post date:** [September 25, 2019, 7:31pm UTC](https://discourse.elm-lang.org/t/thinking-about-folds/4361/7 "2019-09-25T19:31:27Z")

</div>

I actually regularly forget that it’s called `foldl` and not just `fold`. The first time I saw `foldr` I thought it was a misspelling of `folder` 😆

---

<div class="post-metadata">

**Author:** ![system](https://canada1.discourse-cdn.com/flex035/uploads/elm_lang/original/1X/50a05e53677a2c3b47776d7abd0f113eb50193a1.png) [@system](https://discourse.elm-lang.org/u/system)\
**Post date:** [October 5, 2019, 7:31pm UTC](https://discourse.elm-lang.org/t/thinking-about-folds/4361/8 "2019-10-05T19:31:30Z")

</div>

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.