foldl and foldr only work the same if the function is associative, not commutative. For example, a + (b + c) = (a + b) + c, but a - (b - c) /= (a - b) - c. Commutative would be if a + b = b + a. gcd and lcm happen to be both, but both folds apply arguments in the same order, but the associativity is different.
I find using spreadsheets for analyzing recursive functions very convenient (I learn Haskell); you may want to try to use them in your videos to explain how recursion works in cases like the one described in this video.
@@valbogda5512 Sure, but that doesn't describe what the behaviour is on the foldable (a,a) type. It seems to be just taking the right-hand term and discarding the left-hand one. If so, what is the justification (in your words: "context") of that?
@@jamma246 Ok, this was surprising and confusing me too so I just did a little bit of digging. The problem is that pairs can contain 2 different types (a, b), but Foldable is a typeclass that takes just 1 type (Foldable a). The type system doesn't allow you to define Foldable on just pairs with the same type (a, a). So, the only implementation for pairs that works with Foldable is to pick 1 of the elements and go with that type. They chose the second element for whatever reason, and therefore folding with a pair always just uses the second element. (Its a bit more complex than this but thats the idea, it actually considers the whole tuple to contain the type of the second element even when they are different) Really, pairs shouldn't be Foldable at all in my opinion. None of the other tuples are. This leads to really counter intuitive things like minimum (1, 2) == 2. I would much prefer an error over that answer. So basically, don't use pairs as Foldable. It shouldn't be a thing but someone implemented it for whatever reason and now its sitting there as a trap for young players.
Thanks for not explaining it as "left vs right" - I try to teach an intuition: foldLeft is a 'for loop' and foldRight is replacing constructors. I talk about this a little bit over here: ua-cam.com/video/NzIZzvbplSM/v-deo.htmlh14m25s
Nice video. Now, because the video began about an issue of difference between right and left fold in general, I am also looking for efficiency implications of choosing one fold over other. It won't be just commutativity of the function that drives the choice of left or right folding. Do you have any other stuff about time and memory requirements of folds ?
Mostly, I’m only talking about lists here, other Foldable types may have different behavior. Some things to keep in mind: First, never use foldl, but actually use foldl' instead. Secondly, to choose between foldl' and foldr, take into account the strictness properties of the function you’re folding with. I’ll give three examples. (+) is strict in both arguments, which means, to get any result from addition, both arguments must be evaluated first. In such a case foldl' is better. (&&) [conjunction of Bools] is potentially non-strict in its second argumend (similar to short-circuiting in other languages). Thus foldr is better. The third example, (++) [list concatenation], is a bit more complex. To fully evaluate the result of appanding two lists, you of course need to evaluate both lists first. But Haskell is a bit more nuanced around this. For example when I have [1,2,3]++[4,5,6] and only look at (up to) the first three list entries of the result, then the second argument of (++) is not even touched. FWIW, it could’ve been [1,2,3]++undefined and still worked. This non-strictness in the second arguments indicates that foldr is better. In the case of (++) there is another concern: Time complexity, which gets us into implications territory. For evaluating [1,2,3] ++ ([4,5,6] ++ [7,8,9]), the first ++ has to traverse [1,2,3] and the second one has to go through [4,5,6]. On the other hand, in ([1,2,3] ++ [4,5,6]) ++ [7,8,9], the first ++ still encounters [1,2,3], while the second ++ now sees [1,2,3,4,5,6], which means [1,2,3] gets traversed twice! This has the very real implication that foldr (++) [] has linear time behavior, while foldl' (++) [] needs quadratic time. To conclude on further implications, the fact that foldr handles lazyness well means that it can work with infinite lists some times. For example, foldr (&&) True ([True,True,False,True]++[True,True ..]) terminates and returns False as soon as it hits the false, whereas the same thing with foldl' will never terminate (in case it isn’t clear, [True,True ..] is an infinite list). So we have seen foldl' having the effect of worse complexity with some operations and bad termination behavior. On the other hand, using foldr instead when foldl' would be better tends not to have so terrible effects. Of course with a different operation, the same kind of problem with computational complexity that we had with (++) could apply, but I can’t really think of any operation in the standard library of Haskell that does behave like this. The worst effect of a misused foldr that you usually encounter would be (drastically) increased space usage of your program. (In older versions of GHC, a stack overflow was another possibility). For example, evaluating foldl' (+) 0 [1..1000000] runs in with constant (small) memory in Haskell, the list never needs to be fully present in memory, instead it is lazily generated and consumed at the same time. On the other hand, using foldr would create, through recursion, an expression of the form (0 + (1 + (2 + (3 + ...)))), to be evaluated inside-out, so even though the list is still consumed while being generated, your call-stack grows to a size of 1000000 (or you get a stack overflow in older GHC versions). Finally a quick mention on foldl (without the ' ): You can google up on why exactly it’s bad, but the consequences you can get are, too, increased memory usage (and it doesn’t really have any benefit over foldl').
Not true, they will sometimes have different termination behaviour on infinite lists. For example: > foldr1 (&&) (repeat False) returns False but > foldl1 (&&) (reverse $ repeat False) gets stuck in an infinite loop (in case you don't know, given an element x, giving "repeat x" returns the infinite list [x,x,x,x,x...]) The first terminates because of the power of laziness. The right-fold looks something like: False && (False && (False && .... But Haskell already knows that False && anything is always False, so it can tell you that the above expression is False, no matter what is to the right of all of those &&'s. On the other hand, the foldl will only be able to start evaluating when it's got through the list.
Excellent job, I am still a student but when I earn my first salary I will support you in Patreon. I swear, continue like this!
foldl and foldr only work the same if the function is associative, not commutative. For example, a + (b + c) = (a + b) + c, but a - (b - c) /= (a - b) - c. Commutative would be if a + b = b + a. gcd and lcm happen to be both, but both folds apply arguments in the same order, but the associativity is different.
Oh yeah, I can never remember which one is called what. :) Thanks!
Just started getting into Haskell - your breakdown of foldr and foldl were great! Haven’t seen a clearer example of a recursive decent before.
You can also see that it's right fold because the recursion is in the second argument (the right argument)
That environment and speed you have on Emacs makes me wanna switch . from . you . know . what .
Vim ? WAAAAT ? :D
I find using spreadsheets for analyzing recursive functions very convenient (I learn Haskell); you may want to try to use them in your videos to explain how recursion works in cases like the one described in this video.
why foldl (+) 0 (2,3) is 3 and not equal 5?
Because _tuples_. Tuples are not considered a container of two elements, but a container of one element with some context.
@@valbogda5512 Sure, but that doesn't describe what the behaviour is on the foldable (a,a) type. It seems to be just taking the right-hand term and discarding the left-hand one. If so, what is the justification (in your words: "context") of that?
@@jamma246 Ok, this was surprising and confusing me too so I just did a little bit of digging. The problem is that pairs can contain 2 different types (a, b), but Foldable is a typeclass that takes just 1 type (Foldable a). The type system doesn't allow you to define Foldable on just pairs with the same type (a, a). So, the only implementation for pairs that works with Foldable is to pick 1 of the elements and go with that type. They chose the second element for whatever reason, and therefore folding with a pair always just uses the second element.
(Its a bit more complex than this but thats the idea, it actually considers the whole tuple to contain the type of the second element even when they are different)
Really, pairs shouldn't be Foldable at all in my opinion. None of the other tuples are. This leads to really counter intuitive things like minimum (1, 2) == 2. I would much prefer an error over that answer.
So basically, don't use pairs as Foldable. It shouldn't be a thing but someone implemented it for whatever reason and now its sitting there as a trap for young players.
Good video, but you accidently swapped the arguments in the first call of the foldl reduction
Unfortunately, ghc doesn't type check code in comments. :)
@@Tsoding
So instead of foldr folding *to* the right, it folds *from* the right, and vice versa for foldl.
Thanks for not explaining it as "left vs right" - I try to teach an intuition: foldLeft is a 'for loop' and foldRight is replacing constructors. I talk about this a little bit over here: ua-cam.com/video/NzIZzvbplSM/v-deo.htmlh14m25s
Also Tony Morris has a good explanation of loops vs. replacing constructors. ua-cam.com/video/t9pxo7L8mS0/v-deo.html
Gracias.
Nice video.
Now, because the video began about an issue of difference between right and left fold in general, I am also looking for efficiency implications of choosing one fold over other. It won't be just commutativity of the function that drives the choice of left or right folding. Do you have any other stuff about time and memory requirements of folds ?
Mostly, I’m only talking about lists here, other Foldable types may have different behavior.
Some things to keep in mind: First, never use foldl, but actually use foldl' instead.
Secondly, to choose between foldl' and foldr, take into account the strictness properties of the function you’re folding with. I’ll give three examples. (+) is strict in both arguments, which means, to get any result from addition, both arguments must be evaluated first. In such a case foldl' is better. (&&) [conjunction of Bools] is potentially non-strict in its second argumend (similar to short-circuiting in other languages). Thus foldr is better.
The third example, (++) [list concatenation], is a bit more complex. To fully evaluate the result of appanding two lists, you of course need to evaluate both lists first. But Haskell is a bit more nuanced around this. For example when I have [1,2,3]++[4,5,6] and only look at (up to) the first three list entries of the result, then the second argument of (++) is not even touched. FWIW, it could’ve been [1,2,3]++undefined and still worked. This non-strictness in the second arguments indicates that foldr is better. In the case of (++) there is another concern: Time complexity, which gets us into implications territory. For evaluating [1,2,3] ++ ([4,5,6] ++ [7,8,9]), the first ++ has to traverse [1,2,3] and the second one has to go through [4,5,6]. On the other hand, in ([1,2,3] ++ [4,5,6]) ++ [7,8,9], the first ++ still encounters [1,2,3], while the second ++ now sees [1,2,3,4,5,6], which means [1,2,3] gets traversed twice! This has the very real implication that foldr (++) [] has linear time behavior, while foldl' (++) [] needs quadratic time.
To conclude on further implications, the fact that foldr handles lazyness well means that it can work with infinite lists some times.
For example, foldr (&&) True ([True,True,False,True]++[True,True ..]) terminates and returns False as soon as it hits the false, whereas the same thing with foldl' will never terminate (in case it isn’t clear, [True,True ..] is an infinite list).
So we have seen foldl' having the effect of worse complexity with some operations and bad termination behavior.
On the other hand, using foldr instead when foldl' would be better tends not to have so terrible effects. Of course with a different operation, the same kind of problem with computational complexity that we had with (++) could apply, but I can’t really think of any operation in the standard library of Haskell that does behave like this. The worst effect of a misused foldr that you usually encounter would be (drastically) increased space usage of your program. (In older versions of GHC, a stack overflow was another possibility). For example, evaluating foldl' (+) 0 [1..1000000] runs in with constant (small) memory in Haskell, the list never needs to be fully present in memory, instead it is lazily generated and consumed at the same time. On the other hand, using foldr would create, through recursion, an expression of the form (0 + (1 + (2 + (3 + ...)))), to be evaluated inside-out, so even though the list is still consumed while being generated, your call-stack grows to a size of 1000000 (or you get a stack overflow in older GHC versions).
Finally a quick mention on foldl (without the ' ): You can google up on why exactly it’s bad, but the consequences you can get are, too, increased memory usage (and it doesn’t really have any benefit over foldl').
Frank Steffahn
So well explained. . Thanks !
when do you stream on twitch? I've tried to catch you streaming several times but I keep on failing, do you have some kind of schedule or something?
tsoding.github.io/schedule.html
Have you tried lisp before?
It was better to write f in infix form:
left fold: ((a1 `f` a2) `f` a3) `f` a4
right fold: a1 `f` (a2 `f` (a3 `f` a4))
I don't see a need for two different fold functions, since foldr f xs = foldl f (reverse xs).
Not true, they will sometimes have different termination behaviour on infinite lists.
For example:
> foldr1 (&&) (repeat False)
returns False
but
> foldl1 (&&) (reverse $ repeat False)
gets stuck in an infinite loop (in case you don't know, given an element x, giving "repeat x" returns the infinite list [x,x,x,x,x...])
The first terminates because of the power of laziness. The right-fold looks something like:
False && (False && (False && ....
But Haskell already knows that False && anything is always False, so it can tell you that the above expression is False, no matter what is to the right of all of those &&'s. On the other hand, the foldl will only be able to start evaluating when it's got through the list.
you seemed so nice and soft 6 years ago lmao
I wonder if some origami enthusiasts accidentally will click this video