Comment by kccqzy | Hacker News Reader

Comment by kccqzy | Hacker News Reader

Parent Full thread

Haskell got this right. You have foldr (right fold) and foldl' (left fold), and the order of the callback is opposite. If you do a left fold, then the initial accumulator is applied on the left; if you do a right fold, then the initial accumulator is applied on the right.

    foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
    foldl' f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn

The mnemonic here is that the folding function (aka the callback) replaces the comma.

I find this slightly easier to remember than other languages. In contrast most other languages do not simultaneously provide a left fold and a right fold, so they do not consider this aspect, making things more difficult to remember.

That said I totally agree this requires more brainpower to read and write than map or filter. For this reason I have sometimes refactored code to use foldMap instead of foldr or foldl', so one no longer needs to think of the direction of the fold or the order of arguments.

Since you mention mnemonics, here are the mnemonics I use to remember the (symmetrical) differences between foldr and foldl

https://arialdomartini.github.io/fold-mnemonics

Ruby's `[1, 2, 3].inject(:+)` alias for `reduce` (name borrowed from Smalltalk) nicely reinforces that very mnemonic: you inject the operator _between_ the elements: 1 + 2 + 3. :+ here is symbol meaning "send + message", more general form takes a block:

    [1, 2, 3].inject { |a,b| a + b }

The downside of the "between" mnemonic is encouraging not handling an empty collection! Ruby's separate syntax to pass (args) {block} at least offers natural place to add initial value, but with symbol shorthand the API is harder to guess:

    numbers.inject(0) { |a,b| a + b }
    numbers.inject(0, :+)

(Also, it's always a left fold ((a) OP b) OP c, even if you give a symbol like :* which parses right-assiciative without parens — making the "inject operator between values" mental model less accurate.)

I admit that I have always looked at an explanation like yours with x1,...,xn when using fold because I could never keep it straight in my mind.

It's still a complex and more abstract function than map or filter. Those do a single thing that's easy to grasp. reduce/fold can be easily abused to duplicate the effect of most other collection functions, at the cost of making the code less readable. Although for slightly-too-clever people, that could mean you only need to know one function instead of all of them.

But it hurts readability. If you're going to do it, at least don't use it anonymously, but give it a name that clearly describes what's going on.

But even then, there can be hidden performance traps. I've often seen javascript that used reduce and created the new accumulator by using a spread on the old accumulator and adding the new one: `[...acc, newValue]`. But that spread is another iteration inside a loop, turning it from O(n) to O(n^2). A for loop where you append it is much faster.

In other words, look at the types. The type of the folding function (the first argument) indicates how each fold works.

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

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

That's what I tend to do, but since foldr/foldl' is so ubiquitous in Haskell it would be nice if I could just remember the argument order of the callback. kccqzy's explanation (in particular "it replaces the comma") might just help me do that :)

When the accumulator isn't the second argument in a fold, left or right, it feels wrong and I waste some time cursing whomever made a silly mistake like getting the order wrong.

You want the accumulator second to match up with `cons` and similar functions that expect an initial/existing value second.

Luckily the functional languages I use the most are sane in that respect.

Reply on news.ycombinator.com