s-zeng5 hours ago
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...
tomean hour ago
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_!
(This is explained in my article "foldl traverses with State, foldr traverses with anything": https://h2.jaguarpaw.co.uk/posts/foldl-traverses-state-foldr...)
someonebaggy3 hours ago
At some point doesn't it become easier to write the function explicitly? As in
go [] = ...
go head:remainder = ...
bos2 hours ago
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.
s-zeng2 hours ago
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
vatsachak12 minutes ago
Every time I spend a lot of thought on a problem I always go back to F-Algebras and F-CoAlgebras.
Most recursion is through fold and unfold
someonebaggy18 minutes ago
Folding 'fold' into contortions to use it as a generic List iterator does not "provide clarity".
chippiewill2 hours ago
I think once you become comfortable with a fold, and of thinking in that manner, it actually becomes easier with a fold.
tomean hour ago
Or just use `for_` instead of explicit recursion ...
layer83 hours ago
> 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.
kccqzy3 hours ago
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.
someonebaggy3 hours ago
A list in Haskell is a singly-linked list with the possibility of tail sharing.
[deleted]an hour agocollapsed
kccqzy4 hours ago
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.
Drupon3 hours ago
Doesn't using AI render the main advantage of Haskell (telling everyone you can write software in Haskell) somewhat pointless?
kccqzy3 hours ago
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.
nosman2 hours ago
In my experience, AI does really well with a good type system. It tries something, if it doesn't compile, looks at the message, fixes, etc etc.
The compiler itself acts as a steering function for the AI. I've also had this experience with Rust.
whateveracct6 minutes ago
my haskell is still natty
mbauman4 hours ago
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.
woadwarrior0121 minutes ago
Main takeaway: foldl can be tail recursive.
lukebitts2 hours ago
This was a very interesting read. Makes me want to try learning Haskell again after failing miserably a few years ago
sgt39 minutes ago
How about Hodl?
[deleted]2 hours agocollapsed