Comment by layer8
8 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.
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.
A list in Haskell is a singly-linked list with the possibility of tail sharing.