DEV Community

Discussion on: Forever Functional: The mighty reduce

Collapse
 
totally_chase profile image
Phantz • Edited

Neat article. The supremacy of folds become stark in languages like Haskell. Their general usefulness, alongside their deep relation with monoids pose an incredibly interesting rabbit hole to dive into. It's not as useful in Javascript, unfortunately, but it's cool regardless.

I think you could extend the intuition on the relation between left fold and right fold. This is indeed a valid mathematical property of folds-

arr.reduceRight(f, z) === [...arr].reverse().reduce(f, z)
Enter fullscreen mode Exit fullscreen mode

But perhaps it'd be more useful to note that a no mutating reverse function can also be a fold.

function reverse<T>(arr: T[]): T[] {
    return arr.reduceRight((acc: T[], x) => [x, ...acc], []);
}
Enter fullscreen mode Exit fullscreen mode

The [x, ...acc] operation is, of course, cons. Reverse is just a right fold! It can also be a left fold using the append operation. So the property-

arr.reduceRight(f, z) === reverse(arr).reduce(f, z)
Enter fullscreen mode Exit fullscreen mode

could eta reduce to-

arr.reduceRight(f, z) === arr.reduceRight((acc: T[], x) => [x, ...acc], []).reduce(f, z)
Enter fullscreen mode Exit fullscreen mode

Which would be fold fusioned and optimized to oblivion. In Haskell, that is. Cool!

Anyway, this is the naive intuition we've all made when trying to find a relation between a left fold and a right fold. But you can go further. Right folds can lean so far right that they become left folds again.

Sounds like jargon right? Well this is how it works-

foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
foldl accF initialVal target = foldr
    (\value abstractAccFn userAcc -> abstractAccFn (accF userAcc value))
    id
    target
    initialVal
Enter fullscreen mode Exit fullscreen mode

A right fold builds up functions, starting with id. Then the final build up function is applied to the user supplied initialVal and the order of operations ends up being left to right.

I know, dear reader, that it takes a bit to wrap your head around it but if you sit down one evening with a pen and paper and try to work through this, it'll feel like magic. In a good way. Once that's conquered, the next intuition to make is that the functions being built up represent endomorphisms. What the hell is an endomorphism then? Another rabbit hole to dive into :)

Here's the equivalent in typescript/javascript (the types may be an important resource in understanding abstract concepts).