This article is a reproduction of a seminal explanation by Alexis King 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.
Thanks for publishing this in a more easily accessible form than a GitHub comment!
I’m not sure if we have a policy about posting exactly the same reply across multiple channels. I made a response on Reddit but won’t copy and paste it here unless a mod says that’s OK.
From the very first sentence, I don’t like how the post wants to be an explanation of folds in general with constant caveating that the explanation only applies to lists. It inevitably culminates in
None of the post is wrong to be pedantic, just… can we use some different data structure next time?
What different data structure were you thinking of? Exactly the same analysis of foldl' versus foldr applies to Seq or Vector. (The foldl versus foldr' part doesn’t necessarily, but it’s ambiguous what those should mean on data structures that can be walked from both ends).
Yes, because the thing that you want to tease out in the article is the evaluation order of lazy and strict folds (which can be demonstrated over any foldable data structure), not directionality (which is egregiously skewed specifically in the case of lists).
A good example type would be one would be one that is trivial to manipulate directly, even if it would never be constructed manually. A spine-lazy PATRICIA tree, perhaps. An immutable array would also work (though base should provide proper arrays; I don’t like Vector).
Also I don’t think there needs to be any ambiguity as to what “walking a data structure from either end” means. Folding a data structure should take constant time per element instead of leaving it up to library writers to introduce the notion of order into the definition on a whim.
Agreed with that (though maybe log time rather than constant). Foldable has become a kitchen sink and is essentially impossible to use generically.
If some of this is more pithy or clear than the Overview section Data.Foldable, and appropriate for the haddocks, please open an MR that improves that text.