I have been flirting with getting into Haskell and fp for years now and your excellent teaching style is the sign that now is the time. Thank you very much :))
8:08 IIRC haskell compiler (ghc) will often turn recursive functions into their imperative equivalent, if it's possible. so you can write recursive functions and the compiler will turn them into optimized loops. so saying that they are "always slow" is misleading
i never said it would be slow, only that an handwritten and optimized iterative appeoach will perform better if one exists. That is why the compiler does what you described in the first place. And for simple situations it will perform equally to an imperative equivalent, but you miss out on a lot of case-by-case optimizations. I should've clarified that better, I might cover that in the higher-order functions video.
There really isn't anything about hand-written, iterative, recursive or imperative that means optimal. The reason GHC creates imperative code is simply because the target CPU is sequential. It's a subtly different story with e.g. the Reduceron. A key understanding about tail calls is that everything is already in place; there need not be, and often isn't, any call overhead (they're jumps, branches or fall throughs, not calls, at a typical machine language level). Your favourite imperative language compiler probably takes your imperative loop and rebuilds it to SSA blocks exactly equivalent to the tail recursive version, as a step between AST and code generation. See e.g. LLVM's phi nodes.
Just started learning haskell today, and I was doing the practice examples at the end. Finally getting and understanding the 'sorted' function was so exciting! It feels like the kick I got from first learning to code all over again
You make some incredible content, thanks ! I heard that haskell do some optimisation when compiling the recursion to make it's perforances similar to a classic loop. Rust has this functionality: using a for loop or a chain of higher order functions give the same assembly code.
thats why i encourage people to learn this. Haskell might not be great at it, but it does force you to get used to it, and some other languages definitely are great at it.
@@peppidesuwhat are you talking about lol. Tail call recursion in haskell is converted into loops by the compiler. Bruh how do you even make videos on something you don't even have basic knowledge of
There is *lots* of overhead in the for loop you showed to begin with, specifically on the programmer's side! Compare: int factorial(int n) { int product=1; for (int factor=1; factor Int factorial n = product [1..n] Why should the programmer repeatedly explain to the compiler how to iterate through numbers every time they want to handle any sort of sequence? It's even done with the full expectation the compiler will recognize the pattern and discard those details, in order to perform optimization like using CPU flags, unrolling, vectorization etc; which means there's another load of overhead on the compiler's side. And then you still have to elaborate for some of those, like #pragma omp reduction (* : product).
This video is so starkly different from the conclusions I've come to in my work experience that it was a little jarring. Great video and I can understand how one would arrive at using recursion more, but based on my work experience I try to avoid recursion at all costs. I have found that recursion tends to tie knots in my code that only get worse over time. I find iterators and their associated for loops to be much more intuitive, and even figured out how to handle trees without recursion by instead building tree-based iterators.
Lol what are you talking about. First of all, tail call recursion is converted into for loops. Second of all, this is low level iteration you should never be writing, neither for loops nor recursion, unless you've got some performance need. OOP has iterators and FP has HOFs and comprehensions which are 2-3 levels of abstraction above loops and recursion. It also decouples how to iterate from what you want to do as well as isn't specific to a data structure... On top of that it's also much cleaner code
6:55 I think for the take 0s, doing just `take 0 n = []` here should suffice? Not sure why it needs to be two cases Edited nvm I paused too fast and jumped the shark lol
What do you mean by linked lists resulting in less memory fragmentation? I can't come up with any mechanism or workload by which a linked list would result in less memory fragmentation than an array-based list
nodes in a linked list don't need to be stored sequentially, so the individual nodes can fill up gaps of free memory and remedy fragmentation. also if an array-like list grows too large to the point where it collides with other allocated memory it needs to be moved which is very time consuming, whereas a linked list doesn't care its not a common reason to use linked lists tho, they are mostly used because of O(1) insertion and deletion time
@@peppidesu thats a weird way to look at memory fragmentation. The fact that the nodes are so small and not stored sequentially causes memory fragmentation if they are long lived. I suppose if they are short lived it technically reduces the memory fragmentation as the hole in memory is plugged, but that's not a practical way to reduce memory fragmentation since you're just using up more memory I get where you're coming from though, but I think a better label in that case would be "less affected by memory fragmentation"
@@crazychicken0378 You have !! backwards (and didn't import Data.List to define it). fibSeq also avoided the branching recursion, though it can instead form an in-memory list of results. Alternate definition: fibSeq = map fst (iterate (\(a, b) -> (b, a+b)) (0, 1)) iterate is one of many higher order functions that factor out recursion. Iteration is not what a C++ iterator does.
Wait, isn't there a massive crashing bug in the factorial code? If i call "factorial (-1)" it will infinitely recurse and never stop. How is this an acceptable coding feature? Surely, the function domain should be limited to unsigned integers (Z+) rather than all Integers?
YESSS NEW PEPSI VIDEO
Recursion: If you don’t understand, see Recursion
Recursion: If you don't understand, see Recursion
Recursion: If you don't understand, see Recursion
Malformed recursive call, it should have a way to terminate (a change), unless you want the function to call itself without change for all infinity..
I prefer the Jargon File version:
Recursion, noun: See recursion.
Tail recursion, noun: If you're not sick of it already, see tail recursion.
Please keep this series going, your teaching style is very good, concise and easy to follow along.
Can't wait for the monads video.
im so ready to understand monads
Never knew I needed Haskell in my life, now I want more.
I have been flirting with getting into Haskell and fp for years now and your excellent teaching style is the sign that now is the time. Thank you very much :))
8:08 IIRC haskell compiler (ghc) will often turn recursive functions into their imperative equivalent, if it's possible. so you can write recursive functions and the compiler will turn them into optimized loops. so saying that they are "always slow" is misleading
i never said it would be slow, only that an handwritten and optimized iterative appeoach will perform better if one exists. That is why the compiler does what you described in the first place. And for simple situations it will perform equally to an imperative equivalent, but you miss out on a lot of case-by-case optimizations. I should've clarified that better, I might cover that in the higher-order functions video.
@@peppidesuno it's literally the same. And there's no compiler in the world with as many optimizations as the GHC
There really isn't anything about hand-written, iterative, recursive or imperative that means optimal. The reason GHC creates imperative code is simply because the target CPU is sequential. It's a subtly different story with e.g. the Reduceron. A key understanding about tail calls is that everything is already in place; there need not be, and often isn't, any call overhead (they're jumps, branches or fall throughs, not calls, at a typical machine language level). Your favourite imperative language compiler probably takes your imperative loop and rebuilds it to SSA blocks exactly equivalent to the tail recursive version, as a step between AST and code generation. See e.g. LLVM's phi nodes.
Just started learning haskell today, and I was doing the practice examples at the end. Finally getting and understanding the 'sorted' function was so exciting! It feels like the kick I got from first learning to code all over again
I wish these videos existed when I had to learn Haskell for my advanced programming languages course! Great stuff!
You make some incredible content, thanks ! I heard that haskell do some optimisation when compiling the recursion to make it's perforances similar to a classic loop. Rust has this functionality: using a for loop or a chain of higher order functions give the same assembly code.
thats why i encourage people to learn this. Haskell might not be great at it, but it does force you to get used to it, and some other languages definitely are great at it.
@@peppidesuwhat are you talking about lol. Tail call recursion in haskell is converted into loops by the compiler. Bruh how do you even make videos on something you don't even have basic knowledge of
based haskell user (youre very cool peppi)
thank you bepsi
base case: having a good one
These videos are great! Subbed and looking forward to more
Keep up the good work! Waiting for more
Rare haskell W, easy for peppi
@@noomade example?
There is *lots* of overhead in the for loop you showed to begin with, specifically on the programmer's side! Compare:
int factorial(int n) {
int product=1;
for (int factor=1; factor Int
factorial n = product [1..n]
Why should the programmer repeatedly explain to the compiler how to iterate through numbers every time they want to handle any sort of sequence? It's even done with the full expectation the compiler will recognize the pattern and discard those details, in order to perform optimization like using CPU flags, unrolling, vectorization etc; which means there's another load of overhead on the compiler's side. And then you still have to elaborate for some of those, like #pragma omp reduction (* : product).
4:09 > _"UTH, Haskell lists look like this"_
wait, this looks (syntax) & sound (name) like lisp lists.
This video is so starkly different from the conclusions I've come to in my work experience that it was a little jarring. Great video and I can understand how one would arrive at using recursion more, but based on my work experience I try to avoid recursion at all costs. I have found that recursion tends to tie knots in my code that only get worse over time. I find iterators and their associated for loops to be much more intuitive, and even figured out how to handle trees without recursion by instead building tree-based iterators.
Lol what are you talking about. First of all, tail call recursion is converted into for loops. Second of all, this is low level iteration you should never be writing, neither for loops nor recursion, unless you've got some performance need. OOP has iterators and FP has HOFs and comprehensions which are 2-3 levels of abstraction above loops and recursion. It also decouples how to iterate from what you want to do as well as isn't specific to a data structure... On top of that it's also much cleaner code
Yay another video 🎉
first, also haskell man ily
6:55 I think for the take 0s, doing just `take 0 n = []` here should suffice? Not sure why it needs to be two cases
Edited nvm I paused too fast and jumped the shark lol
What do you mean by linked lists resulting in less memory fragmentation? I can't come up with any mechanism or workload by which a linked list would result in less memory fragmentation than an array-based list
nodes in a linked list don't need to be stored sequentially, so the individual nodes can fill up gaps of free memory and remedy fragmentation. also if an array-like list grows too large to the point where it collides with other allocated memory it needs to be moved which is very time consuming, whereas a linked list doesn't care
its not a common reason to use linked lists tho, they are mostly used because of O(1) insertion and deletion time
@@peppidesu thats a weird way to look at memory fragmentation. The fact that the nodes are so small and not stored sequentially causes memory fragmentation if they are long lived. I suppose if they are short lived it technically reduces the memory fragmentation as the hole in memory is plugged, but that's not a practical way to reduce memory fragmentation since you're just using up more memory
I get where you're coming from though, but I think a better label in that case would be "less affected by memory fragmentation"
Great video :D
can someone tell me who graham mutton is i found graham sutton, graham hutton but not a graham mutton.
My solutions to the last exercises:
fibb 0 = 0;
fibb 1 = 1;
fibb n = fibb (n - 1) + fibb (n - 2)
elem2 n [] = False
elem2 n (x:xs) = (x == n) || elem2 n xs
isSorted [] = True
isSorted [x] = True
isSorted (x:y:xs) = x < y && isSorted (y:xs)
fib n = n !! fibSeq
where fibSeq = 0 : 1 : zipWith (+) fibSeq $ tail fibSeq
@@crazychicken0378 You have !! backwards (and didn't import Data.List to define it).
fibSeq also avoided the branching recursion, though it can instead form an in-memory list of results. Alternate definition:
fibSeq = map fst (iterate (\(a, b) -> (b, a+b)) (0, 1))
iterate is one of many higher order functions that factor out recursion. Iteration is not what a C++ iterator does.
Wait, isn't there a massive crashing bug in the factorial code? If i call "factorial (-1)" it will infinitely recurse and never stop. How is this an acceptable coding feature? Surely, the function domain should be limited to unsigned integers (Z+) rather than all Integers?
Feel free to add «factorial n | n
Burrito tutorials please
Its funny how Haskel uses church numerals to even go as far as evaluate numbers in a list of N lazily
Tail call recursion is not slower
so python is just dumb haskell?