10:39 the order in which data is processed and the order of operations are two different things, and, due to non-commutative functions, the order *can* matter. For example, consider `foldDiv = foldr (/) 1.0`; the order of the elements does matter in this case (`foldDiv [1, 2, 3]` returns 1.5, while `foldDiv [1, 3, 2]` returns approximately ⅔)
OMG never ever imagined that I could build anything from scratch so elegantly using functional programming! this is unreal, is just mind blowing how everything just makes sense!
Once you escape the Matrix of Object-Oriented Programming and understand the elegant Platonic Ideal Realm of Functional Programming Paradigms it changes how you think about coding. None of the projects I write use Haskell, but learning it changed how I write Java code.
@@sentzeu I totally agree. OOP has many real world applications and teaches you to think in terms of objects, but without the elegance of functional programming, you just cant get the most out of OOP. Functional programming makes you think and program in terms of math, the language of the universe. It just takes programming to a different new awesome level.
Very good explanation. The explanation from chapter 7 in "Programming Haskell" did not really click for me, but your video made finally clear to me. Thanks!
5:00 There is another way to define "isAll" using a point-free function within foldl': isAll1 e = foldl' ( (&&) .^ (==e) ) True where (f .^ g) x y = f x (g y) -- or imported from pointless-fun Data.Function.Pointless. For foldr there is no matching predefined function, but we could adjust ".^" with flip: isAll2 e = foldr ( flip $ (&&) .^ (==e) ) True
Here is something mind-blowing for you. Foldr is not tail recursive, and we therefore want to use foldl instead to prevent stack overflow, which is tail recursive. Here is what people tend to think: "as long as the fold function is commutative, i can use foldl and foldr interchangeably, and if not i can just swap the arguments". The reality is that you also need the fold function to be *associative*, and if it isn't, there is generally no way to make a foldr into a foldl, and no way to make it tail-recursive, even if you implement it yourself.
if the operator (op) is not comutative, is foldr (op) z [a,b,c,d] then equivalent to a op (b op (c op (d op z))) ? (so that the most right operation binds the strongest)
AT 1:38 in your example xn is of type a and a is of type b - correct? It makes a bit hard at first the reconcile it with (a -> b -> b) -> b -> [a] -> b on top of th screen. I understand that the first a is tha name of type and the other is name of parameter but first time you read it you get turned around
Vielen Dank für die Haskell-Tutorials! ich studiere grad Informatik in den USA und es gibt kaum genug YT Content über Haskell im Vergleich zu Python, Java usw
Yes very much so. You can think of fold (at a high level) as "reduce (\x acc -> ...) . map (\y -> ...)", but the functions can be rolled into one (e.g. transforming while reducing in the same function.
More generally, a reduce may operate in arbitrary order, suitable for a semigroup (i.e. associative functions, as was assumed at the end of this video). Left/right folds specify the ordering. In practice reduce is often implemented as a left fold, but using it with a monoid allows starting in more than one place for parallel evaluation. This may make more sense for chunked or tree structures than lists. The 1 variants of fold start at some element within the foldable, which is also often how reduce operates. That way the zero value of the monoid isn't needed.
$ is never necessary; it only manipulates precedence. It could be replaced with the appropriate parenthesis, so (&&) (e==x). Function application has very high precedence, so just removing $ produces ((&&) e)==x, which requires e to be Bool and x to be equality comparable to a partially applied &&, but functions are not comparable so that won't work. Another way to write (\x -> (&&) $ e==x) is ((&&) . (e==)). And despite what was said in this session, you should not fear "iterating twice" because Haskell can fuse loops like "and . map ((==) e)" (better spelled "all (e==)").
That was just a bad way of visualizing on my part. The "2" node will always be visited only a single time. The arrows are meant to signify the "flow" of the folding, if that makes sense. ;)
I couldn't find documentation anywhere that says what order the arguments to the lamda function from the fold functions. Do you have any idea how I would look this sort of thing up? I was completely lost here, and had to come back to your tutorials to look it up. While your videos are informative and have helped me a lot, they're not great for looking up documentation when you need clarification.
the names are confusing. foldr starts at the right, but goes to the left. I think it's more intuitive to name it after the direction rather than the starting point, but either way it's confusing.
Yes it's very mathy and has to do with how the "spine" is evaluated. A better way to think of this is that the accumulator / fixed-point (0 for +, 1 for *, etc) is placed at the right of the list for foldr, and the left for foldl.
Right and left have nothing to do with the side folding starts or ends. Right stands for right-associative application (of the binary operator/function passed to foldr), and left for left-associative application. foldr (-) 0 [1,2,3] will expand to 1 - (2 - (3 - 0)) foldl (-) 0 [1,2,3] will expand to ((0 - 1) - 2) - 3 Notice that expansion of the foldl above is identical to 0 - 1 - 2 - 3, because subtraction operator itself is left-associative.
I am struggling with the syntax of Haskell. Besides being phenomenally cryptic and condensed, it appears you are throwing up fragments of code separate from how they would be used in an actual working program (or even complete function block), *and* not explaining what the strange and shifting aggregations of special characters mean. I see "->" and "=>" and "
I'd highly recommend rewatching the earlier videos going over syntax, as well as checking out books like "Haskell From First Principles", or the wikibook guide!! Haskell seems a bit opaque at first but it's highly rewarding once you engage with it!! Something I've found is that even being given only math education up to calculus, everything we need for functional stuff that lambda calc captures has already been given, it's just implicit and needs to be drawn out!!
Maybe you should learn computer science instead of crying. Also he talked about most of this before. You're not gonna to make it far in life if you can't figure out how to watch videos in order. They start with the #1
foldr = (x1 op (x2 op (x3 op .... (xn op a)))) foldl = ((((a op x1) op x2) op x3) ... op xn) foldr = x1 op x2 op x3 op x4 ... xn op a works only if it's asociative operation
the map implementation with foldr was mindblowing ;)
I guess it is kinda randomly asking but does anybody know a good website to stream new movies online?
10:39 the order in which data is processed and the order of operations are two different things, and, due to non-commutative functions, the order *can* matter. For example, consider `foldDiv = foldr (/) 1.0`; the order of the elements does matter in this case (`foldDiv [1, 2, 3]` returns 1.5, while `foldDiv [1, 3, 2]` returns approximately ⅔)
OMG never ever imagined that I could build anything from scratch so elegantly using functional programming! this is unreal, is just mind blowing how everything just makes sense!
Once you escape the Matrix of Object-Oriented Programming and understand the elegant Platonic Ideal Realm of Functional Programming Paradigms it changes how you think about coding. None of the projects I write use Haskell, but learning it changed how I write Java code.
@@sentzeu I totally agree. OOP has many real world applications and teaches you to think in terms of objects, but without the elegance of functional programming, you just cant get the most out of OOP. Functional programming makes you think and program in terms of math, the language of the universe. It just takes programming to a different new awesome level.
Very good explanation. The explanation from chapter 7 in "Programming Haskell" did not really click for me, but your video made finally clear to me. Thanks!
If the function used in folding isn't commutative then the order in which you traverse a tree matters.
associative but yeah the order matters
@@tobiasboschung3210 no... commutative, right?
This is awesome!!!
Folding L is the same as Reduce in JavaScript
5:00 There is another way to define "isAll" using a point-free function within foldl':
isAll1 e = foldl' ( (&&) .^ (==e) ) True
where (f .^ g) x y = f x (g y) -- or imported from pointless-fun Data.Function.Pointless.
For foldr there is no matching predefined function, but we could adjust ".^" with flip:
isAll2 e = foldr ( flip $ (&&) .^ (==e) ) True
Here is something mind-blowing for you. Foldr is not tail recursive, and we therefore want to use foldl instead to prevent stack overflow, which is tail recursive. Here is what people tend to think: "as long as the fold function is commutative, i can use foldl and foldr interchangeably, and if not i can just swap the arguments". The reality is that you also need the fold function to be *associative*, and if it isn't, there is generally no way to make a foldr into a foldl, and no way to make it tail-recursive, even if you implement it yourself.
if the operator (op) is not comutative,
is foldr (op) z [a,b,c,d] then equivalent to
a op (b op (c op (d op z)))
? (so that the most right operation binds the strongest)
Yes it does, didn't whatch to the end
it has to be associative too
AT 1:38 in your example xn is of type a and a is of type b - correct? It makes a bit hard at first the reconcile it with (a -> b -> b) -> b -> [a] -> b on top of th screen. I understand that the first a is tha name of type and the other is name of parameter but first time you read it you get turned around
Vielen Dank für die Haskell-Tutorials! ich studiere grad Informatik in den USA und es gibt kaum genug YT Content über Haskell im Vergleich zu Python, Java usw
Is folding the same as “reduce” used in some programming languages/frameworks?
Yes very much so. You can think of fold (at a high level) as "reduce (\x acc -> ...) . map (\y -> ...)", but the functions can be rolled into one (e.g. transforming while reducing in the same function.
More generally, a reduce may operate in arbitrary order, suitable for a semigroup (i.e. associative functions, as was assumed at the end of this video). Left/right folds specify the ordering. In practice reduce is often implemented as a left fold, but using it with a monoid allows starting in more than one place for parallel evaluation. This may make more sense for chunked or tree structures than lists.
The 1 variants of fold start at some element within the foldable, which is also often how reduce operates. That way the zero value of the monoid isn't needed.
4:52 why is the $ sign necessary? Couldn’t we just write in the end
Foldr( ….. -> (&&) e==x)
??
I was wondering this as well, I really don't get it. Still no answers
$ is never necessary; it only manipulates precedence. It could be replaced with the appropriate parenthesis, so (&&) (e==x).
Function application has very high precedence, so just removing $ produces ((&&) e)==x, which requires e to be Bool and x to be equality comparable to a partially applied &&, but functions are not comparable so that won't work.
Another way to write (\x -> (&&) $ e==x) is ((&&) . (e==)). And despite what was said in this session, you should not fear "iterating twice" because Haskell can fuse loops like "and . map ((==) e)" (better spelled "all (e==)").
Thank you, this was very helpful.
muy bien explicado, sos crack philipp ee
Is it correct that the 2 is visited twice in the pre- and post- tree fold orders? Wouldn't that make count, map, etc. impossible?
That was just a bad way of visualizing on my part. The "2" node will always be visited only a single time. The arrows are meant to signify the "flow" of the folding, if that makes sense. ;)
I had the same question
I couldn't find documentation anywhere that says what order the arguments to the lamda function from the fold functions. Do you have any idea how I would look this sort of thing up? I was completely lost here, and had to come back to your tutorials to look it up. While your videos are informative and have helped me a lot, they're not great for looking up documentation when you need clarification.
How can I execute isAll on the right way? Don't get it
Loved the video, thank you!
the names are confusing. foldr starts at the right, but goes to the left. I think it's more intuitive to name it after the direction rather than the starting point, but either way it's confusing.
Yes it's very mathy and has to do with how the "spine" is evaluated. A better way to think of this is that the accumulator / fixed-point (0 for +, 1 for *, etc) is placed at the right of the list for foldr, and the left for foldl.
Right and left have nothing to do with the side folding starts or ends. Right stands for right-associative application (of the binary operator/function passed to foldr), and left for left-associative application.
foldr (-) 0 [1,2,3] will expand to 1 - (2 - (3 - 0))
foldl (-) 0 [1,2,3] will expand to ((0 - 1) - 2) - 3
Notice that expansion of the foldl above is identical to 0 - 1 - 2 - 3, because subtraction operator itself is left-associative.
@@michaell8624 Yeah alright, I suppose that makes sense. In that case I just wish it was more obvious from their names.
This is really great! Thank you so much
Awsome vid!
Very helpful. Thanks!
love this video! FOLD IS OP
folding without an accumulator would prevent you from doing the first operation, not the last
Depends on the direction of the fold and how you define operation order.
I am struggling with the syntax of Haskell. Besides being phenomenally cryptic and condensed, it appears you are throwing up fragments of code separate from how they would be used in an actual working program (or even complete function block), *and* not explaining what the strange and shifting aggregations of special characters mean. I see "->" and "=>" and "
I'd highly recommend rewatching the earlier videos going over syntax, as well as checking out books like "Haskell From First Principles", or the wikibook guide!! Haskell seems a bit opaque at first but it's highly rewarding once you engage with it!!
Something I've found is that even being given only math education up to calculus, everything we need for functional stuff that lambda calc captures has already been given, it's just implicit and needs to be drawn out!!
Maybe you should learn computer science instead of crying. Also he talked about most of this before. You're not gonna to make it far in life if you can't figure out how to watch videos in order. They start with the #1
Go Frogs Under Cold Kumquats yourself.@@AndreiGeorgescu-j9p
This is #9 so that seems somewhat expected
Skill issue
fold arrr matey
ty a lot !
Good Explanation if you want to understand WHAT it does.
Not so good to understand how you do it.
foldr = (x1 op (x2 op (x3 op .... (xn op a))))
foldl = ((((a op x1) op x2) op x3) ... op xn)
foldr = x1 op x2 op x3 op x4 ... xn op a works only if it's asociative operation
Good take!