To start, you have to understand that foldl and foldr are not folds “from the left” and “from the right.” Both foldl and foldr traverse the structure in the same order, which in the case of lists means left to right. The difference is the fold’s associativity.
but then goes on to explain that the list is processed exactly as if the right two items are processed first, then continuing to proceed right-to-left. The whole thing seems to me like an explanation of how the internal workings of lazy vs eager implementations affect performance, but I can't distinguish the final result from
foldl and foldr fold “from the left” and “from the right exactly as you expect. That may be bad performancewise.
Keep in mind that the [a, b, c, d] syntax is sugar for the value a : (b : (c : (d : []))), hence anything processing such a value must go left-to-right. For example, if we use pattern-matching, like:
case myList of
[] -> myNilCase
x:xs -> myConsCase
Then the above value would hit the x:xs pattern, where x gets bound to a and xs gets bound to b : (c : (d : [])) (AKA [b, c, d]).
For something to go right-to-left, i.e. processing d before it processes a, it would first have to traverse through the list (e.g. using pattern-matching like above) in order to find those values that are buried under the : ("cons") constructors; and that traversal would be left-to-right! (Indeed, it would look like foldr with the function's arguments flipped).
I think the point is whether the actual work is done before the recursion on the "head" or after on the "tail". If the main work is done after the recursion, on its return value, you have to accumulate thunks and then unroll them after you reached the end of the list, and they will be effectively processed in reverse order. So it is still true that foldr goes from right to left somehow. At least this is how I get it.
If you use a non-commutative operator like subtraction, then you can imagine a "right to left fold" operation that applied to [1, 2, 3, 4] gives the result of 4-3-2-1. Not what either foldl or foldr does, but you can imagine that function existing, at least for lists.
I believe that's the hypothetical right-to-left alternative that the line "In both expressions, the elements of the list appear in the expression in the same order" alludes to.
If we swap the arguments, say like x £ y = y - x, then 4-3-2-1 is the same as 1£2£3£4, and we can use foldl (£) and foldr (£), depending whether we want ((1£2)£3)£4 or 1£(2£(3£4)). Note that we get another layer of thunks though, since x £ y has to wait for both arguments to arrive.
The function flip f x y = f y x will swap arguments for us, so my £ operator is the same as flip (-). Hence we can swap the order of any fold via foldl . flip or foldr . flip (again, at the cost of building up thunks).
I believe one of the great strengths of lazily-evaluated languages is that they allow elegant implementations of certain algorithms. I also believe one of their great weaknesses is that they require one to think about evaluation strategies in places they otherwise wouldn't need to, such as with foldl and foldl'. In a functional language with immutability like Haskell, this can often offset the reduction in incidental complexity that comes with eliminating/encapsulating mutable state. However, it is unfortunately necessary in order to permit a style of programming that complements said immutability.
A little-known fact about the mysterious foldr is that it's equivalent to something straightforward: for_. That is, iterating over each element of a container performing an effectful action based on that element.
That sounds a bit like foldl/foldl' too though, doesn't it? That's because foldl/foldl' is a special case of for_: iterating over each element of a container updating an accumulating state (it's equivalent to using for_ in the State monad).
So, by the "principle of least power" you should use foldl' when you can (not foldl, because it's lazy) and foldr when you must (but perhaps it's clearer to just use for_ instead). This is explained in my article foldl traverses with State, foldr traverses with anything
ryan-duve | a day ago
TIL what a
thunkis.The article starts with:
but then goes on to explain that the list is processed exactly as if the right two items are processed first, then continuing to proceed right-to-left. The whole thing seems to me like an explanation of how the internal workings of lazy vs eager implementations affect performance, but I can't distinguish the final result from
chriswarbo | a day ago
Keep in mind that the
[a, b, c, d]syntax is sugar for the valuea : (b : (c : (d : []))), hence anything processing such a value must go left-to-right. For example, if we use pattern-matching, like:Then the above value would hit the
x:xspattern, wherexgets bound toaandxsgets bound tob : (c : (d : []))(AKA[b, c, d]).For something to go right-to-left, i.e. processing
dbefore it processesa, it would first have to traverse through the list (e.g. using pattern-matching like above) in order to find those values that are buried under the:("cons") constructors; and that traversal would be left-to-right! (Indeed, it would look likefoldrwith the function's arguments flipped).gignico | a day ago
I think the point is whether the actual work is done before the recursion on the "head" or after on the "tail". If the main work is done after the recursion, on its return value, you have to accumulate thunks and then unroll them after you reached the end of the list, and they will be effectively processed in reverse order. So it is still true that foldr goes from right to left somehow. At least this is how I get it.
frogulis | 19 hours ago
If you use a non-commutative operator like subtraction, then you can imagine a "right to left fold" operation that applied to [1, 2, 3, 4] gives the result of 4-3-2-1. Not what either foldl or foldr does, but you can imagine that function existing, at least for lists.
I believe that's the hypothetical right-to-left alternative that the line "In both expressions, the elements of the list appear in the expression in the same order" alludes to.
chriswarbo | 12 hours ago
If we swap the arguments, say like
x £ y = y - x, then4-3-2-1is the same as1£2£3£4, and we can usefoldl (£)andfoldr (£), depending whether we want((1£2)£3)£4or1£(2£(3£4)). Note that we get another layer of thunks though, sincex £ yhas to wait for both arguments to arrive.The function
flip f x y = f y xwill swap arguments for us, so my£operator is the same asflip (-). Hence we can swap the order of any fold viafoldl . fliporfoldr . flip(again, at the cost of building up thunks).nil | a day ago
I believe one of the great strengths of lazily-evaluated languages is that they allow elegant implementations of certain algorithms. I also believe one of their great weaknesses is that they require one to think about evaluation strategies in places they otherwise wouldn't need to, such as with
foldlandfoldl'. In a functional language with immutability like Haskell, this can often offset the reduction in incidental complexity that comes with eliminating/encapsulating mutable state. However, it is unfortunately necessary in order to permit a style of programming that complements said immutability.nathan | a day ago
I've seen a few of Alexis' talks over the years and she's a great science communicator; hope she keeps writing on the Haskell blog!
tome | 14 hours ago
A little-known fact about the mysterious
foldris that it's equivalent to something straightforward:for_. That is, iterating over each element of a container performing an effectful action based on that element.That sounds a bit like
foldl/foldl'too though, doesn't it? That's becausefoldl/foldl'is a special case offor_: iterating over each element of a container updating an accumulating state (it's equivalent to usingfor_in theStatemonad).So, by the "principle of least power" you should use
foldl'when you can (notfoldl, because it's lazy) andfoldrwhen you must (but perhaps it's clearer to just usefor_instead). This is explained in my articlefoldltraverses withState,foldrtraverses with anything