Re:Differences Between `Foldl` and `Foldr`
by s-zeng on Monday October 05, 2026 @08:56AM
(#49964252)
A neat fact about foldr on lists, unlike foldl, is that it actually passes control flow entirely to the accumulating function on each fold step. That means you can use foldr to implement arbitrary traversals of lists, including foldl' or list traversals that exit early. See https://github.com/quchen/articles/blob/master/useful_techni...
Re:Differences Between `Foldl` and `Foldr`
by s-zeng on Monday October 05, 2026 @12:01PM
(#49966638)
There's a relatively popular point of view amongst Haskell programmers that explicit recursion is the goto of functional programming; a dedicated folding or traversing function provides more clarity on what exactly the function intends to do. The extreme end of this is recursion schemes and memes like zygohistomorphic prepomorphisms, which are almost certainly overkill on lists proper but might be useful when traversing bigger recursive structures. Personally, I almost always prefer to find a monoid to map the list elements into, and use `fold :: (Monoid m, Foldable t) => t m -> m`. It's essentially the equivalent of using `sum()` instead of `reduce()` in python
Re:Differences Between `Foldl` and `Foldr`
by strbean on Monday October 05, 2026 @05:35PM
(#49971147)
In functional programming, there is no "generic list iterator", though. It matters what the output is, whether you need to look at the value of previous iterations, etc.
Re:Differences Between `Foldl` and `Foldr`
by bos on Monday October 05, 2026 @11:45AM
(#49966390)
If you don’t already know about folds, arguably yes.
If you do, then a quick glance at whether you’re using foldl’ or foldr tells you about what the function is allowed to do, which cuts down a little on comprehension.
List traversals are typically compact enough that there’s not a huge difference either way.
One advantage of using a fold, even in these cases, is that newcomers to Haskell often get so carried away with (and confused by) the power of pattern matching that they’ll write bizarre overly-complicated list traversals by hand, when a simpler mechanism exists that they just haven’t yet internalized.
Re:Differences Between `Foldl` and `Foldr`
by WorldMaker on Monday October 05, 2026 @02:33PM
(#49968653)
One of the links (on Fusion) points out that GHC in particular has a lot of optimizations and rewrite rules for folds and many Prelude functions written as simple recursion also include optimized fold representations to suggest to various stages of GHC's optimizer.
As with so many such topics it seems an interesting spectrum between clarity and/or aesthetics and potential performance optimizations. Especially because it often seems like one of those "learning curve flips the clarity/aesthetics preferences" because at some point of familiarity folds can be faster to read than trying to reason through an explicitly written recursion.
Re:Differences Between `Foldl` and `Foldr`
by tome on Monday October 05, 2026 @01:11PM
(#49967568)
Yes, because foldr is equivalent to for_, that is, iterating over a container and performing an effectful action (what in other languages would be called "doing something") for each element. Uses of foldr can always be rewritten to uses of for_, and I find things much clearer in terms of for_!
Re:Differences Between `Foldl` and `Foldr`
by Twey on Monday October 05, 2026 @06:26PM
(#49971683)
Well, `foldr` is (up to interdefinability) just the implementation of `for_` (or `traverse`) in the case of lists, in the same way that `map` is the implementation of `fmap`. The point of `traverse` is that it's provided by the functor.
The question of whether to use the most generic (for consistency) or the least generic (for directness) name for a function is the old bugbear of the Prelude :)
Re:Differences Between `Foldl` and `Foldr`
by tome on Tuesday October 06, 2026 @09:49AM
(#49978467)
I don't quite follow. `fmap = map` is a valid implementation for lists indeed, but `for_ = foldr` is not. They don't have compatible types, for one thing. What do you mean?
Re:Differences Between `Foldl` and `Foldr`
by Twey on Monday October 05, 2026 @06:30PM
(#49971718)
In other words, `foldr` (flipped about) takes a list to its Church encoding: since it just ‘replaces the constructors’ (`:` becomes `f`, `[]` becomes `z`), it doesn't lose any information from the list: if you can write a function by recursing on a list then you can write it using `foldr`.
Re:Differences Between `Foldl` and `Foldr`
by kccqzy on Monday October 05, 2026 @09:59AM
(#49965009)
I noticed that AI likes to overuse foldl' and foldr (especially foldr) including analogous versions on Maps, even when there are simpler and more straightforward ways to achieve the same thing.
When AI writes foldr with a complicated accumulation function, I’d prompt AI to define a custom monoidal structure and then use foldMap. Then the reader doesn’t have to think about the asymmetric accumulation function and instead think about the mapping operation and the associative combine function separately. Factoring out the two jobs of the accumulation function is a great trick to improve readability: excellent tradeoff if the human is mostly reading the code.
Re:Differences Between `Foldl` and `Foldr`
by kccqzy on Monday October 05, 2026 @11:11AM
(#49965887)
The advantage of Haskell is higher quality code with fewer bugs even when you write fewer unit tests. The advantage is the same whether humans write the code or AI writes it.
This might not be noticeable if you only write short programs: if the human can put the entire program in the head or if the AI can keep the whole thing in the context window. It matters much more when the program gets bigger.
Re:Differences Between `Foldl` and `Foldr`
by brabel on Monday October 05, 2026 @02:31PM
(#49968630)
Fewer bugs is such a wild claim. Especially since study after study has shown that to be wishful thinking. Haskell apps have just as many bugs in general as anything else.
Re:Differences Between `Foldl` and `Foldr`
by anyfoo on Monday October 05, 2026 @05:42PM
(#49971254)
Can you produce those studies? Genuinely interested. Intuitively, I would have thought properly used Haskell prevents a lot of bugs by virtue if its type system, which allows for encoding internal constraints to a certain degree.
The extreme end of this is dependent types, which is so strong that it can be used as a foundation for mathematics itself, and is the principle that the Lean, the proof assistance, is used on. A Lean "program" is effectively proven to be bug-free.
Re:Differences Between `Foldl` and `Foldr`
by brabel on Wednesday October 07, 2026 @04:02PM
(#49998078)
Someone else posted a danluu study that is very good. I've read many more studies over the years and NEVER seen one showing a significant advantage for Haskell and similar languages. Try Google Scholar and you'll find some for sure.
Also, just think about this: what bugs have you had in your software historically? How many of those do you believe would've been prevented by a type system like Haskell's?? At least for my software, nearly every bug is a logical bug that no type system could've prevented (though I do use typed languages like Java and Kotlin).
The only thing that ever made a difference in the number of bugs in any study I've seen was not the language, but good testing and the experience of the developer.
> A Lean "program" is effectively proven to be bug-free.
You misunderstand this. Lean proves the program matches a specification. It doesn't and can't prove the specification is for the "right thing" - in other words, if your specification itself has wrong or bad assumptions, you'll still have bugs. Now, who is going to prove the specification is specifying the "right things"? It's turtles all the way.
Re:Differences Between `Foldl` and `Foldr`
by tome on Thursday October 08, 2026 @03:40AM
(#50002901)
This comment by nh2 (on Reddit) is my favourite response to that line of thinking. I recommend reading the whole thing. Excepts:
> You're not going to get any "credible empirical evidence" already because the sample size is so small. That would require getting, say, 100 companies that are similar in size and tasks, have a working business model and are still around, and also want to spend time on methotically collecting concrete evidence, and care to blog about that.
> people don't really want to spend time stating the obvious
> We don't spend time blogging that on our Haskell server, we get pretty much none of [run time type error or segfault] because well, those don't exist in Haskell
> We're convinced it's the best tool for the server job, compared to other tech we used at past jobs and projects. So we're using Haskell for it, and we started it in Haskell. We cannot compare before/after, because we directly started it in the "best tool available". We can compare our current project to our past individual work experience, but one cannot simply turn such individual cross-project experience into quantitative evidence
Re:Differences Between `Foldl` and `Foldr`
by brabel on Thursday October 08, 2026 @03:13PM
(#50010585)
As long as you recognize that this is a perfect example of an anecdote and as such cannot be generalized to anything, and others could provide just the same “experience” for pretty much any language being the best. It’s telling that the poster can’t even compare with other languages as they started with the “best”! Yeah yeah I am sure you chose perfectly first time… we all know that doing some research on paper always proves to end up with the perfect choices.
Re:Differences Between `Foldl` and `Foldr`
by tome on Friday October 09, 2026 @02:24AM
(#50016721)
I think you've got it exactly backwards. The comment is supposed to explain that there can't be a scientific determination of such a matter, not that it itself is such a determination.
Re:Differences Between `Foldl` and `Foldr`
by anyfoo on Thursday October 08, 2026 @06:36PM
(#50013404)
No, I'm not misunderstanding, and you are pushing goalposts. The majority of programs above a certain size would benefit tremendously if they were "matching a specification". Sure, the specification itself may not be fully correct, but a lot, if not most bugs, are code that would go against such a specification.
> Also, just think about this: what bugs have you had in your software historically? How many of those do you believe would've been prevented by a type system like Haskell's??
I program Haskell all the time, and I encounter "non-bugs" where the compiler prevented me from doing something, which other languages would not have, on the regular.
> (though I do use typed languages like Java and Kotlin)
Those are not even close to a Hindley-Milner based type system like the one in Haskell.
Re:Differences Between `Foldl` and `Foldr`
by mbauman on Monday October 05, 2026 @10:08AM
(#49965108)
To a CS person, "ordering" is about the arrangement of a list. But pretty much everyone else will think about a *temporal* order of operations. And in that case it is indeed "starting" from the right or left.
It just gets confusing when you're dealing with lots of deferred/lazy operations.
Re:Differences Between `Foldl` and `Foldr`
by layer8 on Monday October 05, 2026 @10:42AM
(#49965526)
> Both foldl and foldr traverse the structure in the same order, which in the case of lists means left to right.
This characterization is debatable, unless one is assuming single-linked lists, which by definition can only be traversed from left to right (even moreso in a lazy language where the list may have indefinite length). When implemented in a strict language on an array or a double-linked list, the traversal order will be right-to-left for foldr.
A more accurate statement would be that in Haskell, lists can only be traversed from left to right, and therefore the implementations of both foldl and foldr in Haskell are necessarily based on that.
Re:Differences Between `Foldl` and `Foldr`
by kccqzy on Monday October 05, 2026 @10:50AM
(#49965638)
Right. The article is only talking about the foldr and foldl functions on Haskell lists. In the addendum it talks about the functions on other data structures (presumably the implementation of instances of the Foldable class). It would be more instructive to examine the definitions of foldr and foldl on other types such as Map instead of yet another custom list type.
I actually think examining the definitions of folds in Map (a binary tree) is perhaps pedagogically a better starting point. The singly linked list is inherently left biased. A binary tree is symmetrical. So the implementation of foldr and foldl on a binary tree is more similar: literally flipping the order of the arguments to the accumulation function and swapping the left and right children. Furthermore you can induce the “early termination” by laziness behavior by adjusting whether your accumulation function forces the first or second argument. And all four versions foldr, foldl, foldr' and foldl' are meaningful.
Re:Differences Between `Foldl` and `Foldr`
by nimih on Tuesday October 06, 2026 @11:11AM
(#49979699)
I'm not sure what the point you're trying to illustrate is, but I think you forgot a `flip` (unless the point is that you always mix up the argument order of the foldr reducing function, in which case fair enough).
Most recursion is through fold and unfold
If you do, then a quick glance at whether you’re using foldl’ or foldr tells you about what the function is allowed to do, which cuts down a little on comprehension.
List traversals are typically compact enough that there’s not a huge difference either way.
One advantage of using a fold, even in these cases, is that newcomers to Haskell often get so carried away with (and confused by) the power of pattern matching that they’ll write bizarre overly-complicated list traversals by hand, when a simpler mechanism exists that they just haven’t yet internalized.
As with so many such topics it seems an interesting spectrum between clarity and/or aesthetics and potential performance optimizations. Especially because it often seems like one of those "learning curve flips the clarity/aesthetics preferences" because at some point of familiarity folds can be faster to read than trying to reason through an explicitly written recursion.
(This is explained in my article "foldl traverses with State, foldr traverses with anything": https://h2.jaguarpaw.co.uk/posts/foldl-traverses-state-foldr...)
The question of whether to use the most generic (for consistency) or the least generic (for directness) name for a function is the old bugbear of the Prelude :)
When AI writes foldr with a complicated accumulation function, I’d prompt AI to define a custom monoidal structure and then use foldMap. Then the reader doesn’t have to think about the asymmetric accumulation function and instead think about the mapping operation and the associative combine function separately. Factoring out the two jobs of the accumulation function is a great trick to improve readability: excellent tradeoff if the human is mostly reading the code.
This might not be noticeable if you only write short programs: if the human can put the entire program in the head or if the AI can keep the whole thing in the context window. It matters much more when the program gets bigger.
The extreme end of this is dependent types, which is so strong that it can be used as a foundation for mathematics itself, and is the principle that the Lean, the proof assistance, is used on. A Lean "program" is effectively proven to be bug-free.
Also, just think about this: what bugs have you had in your software historically? How many of those do you believe would've been prevented by a type system like Haskell's?? At least for my software, nearly every bug is a logical bug that no type system could've prevented (though I do use typed languages like Java and Kotlin).
The only thing that ever made a difference in the number of bugs in any study I've seen was not the language, but good testing and the experience of the developer.
> A Lean "program" is effectively proven to be bug-free.
You misunderstand this. Lean proves the program matches a specification. It doesn't and can't prove the specification is for the "right thing" - in other words, if your specification itself has wrong or bad assumptions, you'll still have bugs. Now, who is going to prove the specification is specifying the "right things"? It's turtles all the way.
> You're not going to get any "credible empirical evidence" already because the sample size is so small. That would require getting, say, 100 companies that are similar in size and tasks, have a working business model and are still around, and also want to spend time on methotically collecting concrete evidence, and care to blog about that.
> people don't really want to spend time stating the obvious
> We don't spend time blogging that on our Haskell server, we get pretty much none of [run time type error or segfault] because well, those don't exist in Haskell
> We're convinced it's the best tool for the server job, compared to other tech we used at past jobs and projects. So we're using Haskell for it, and we started it in Haskell. We cannot compare before/after, because we directly started it in the "best tool available". We can compare our current project to our past individual work experience, but one cannot simply turn such individual cross-project experience into quantitative evidence
https://www.reddit.com/r/haskell/comments/1plsmqh/comment/nt...
> Also, just think about this: what bugs have you had in your software historically? How many of those do you believe would've been prevented by a type system like Haskell's??
I program Haskell all the time, and I encounter "non-bugs" where the compiler prevented me from doing something, which other languages would not have, on the regular.
> (though I do use typed languages like Java and Kotlin)
Those are not even close to a Hindley-Milner based type system like the one in Haskell.
The compiler itself acts as a steering function for the AI. I've also had this experience with Rust.
It just gets confusing when you're dealing with lots of deferred/lazy operations.
This characterization is debatable, unless one is assuming single-linked lists, which by definition can only be traversed from left to right (even moreso in a lazy language where the list may have indefinite length). When implemented in a strict language on an array or a double-linked list, the traversal order will be right-to-left for foldr.
A more accurate statement would be that in Haskell, lists can only be traversed from left to right, and therefore the implementations of both foldl and foldr in Haskell are necessarily based on that.
I actually think examining the definitions of folds in Map (a binary tree) is perhaps pedagogically a better starting point. The singly linked list is inherently left biased. A binary tree is symmetrical. So the implementation of foldr and foldl on a binary tree is more similar: literally flipping the order of the arguments to the accumulation function and swapping the left and right children. Furthermore you can induce the “early termination” by laziness behavior by adjusting whether your accumulation function forces the first or second argument. And all four versions foldr, foldl, foldr' and foldl' are meaningful.