Professor Hutton is a fantastic teacher. The Lambda Calculus video is another prime example of his comprehension of the concepts and how to convey the knowledge effectively.
Unfortunately in the end they made a huge mistake. They claim to have implemented the Sieve while the algorithm implemented is just smart trial division (the Sieve does no modulo operation. It uses a prime to rule out known *composites*, while the algorithm here simply checks for each number if it is a multiple of a prime we found before which is asymptotically slower). This shows how subtle mistakes can be in math&computer science and make tons of other people fall for them even when explained slowly and clearly.
@@Giacr45 Is it slower because of the time complexity of modulo operation which is higher for arbitrarily large numbers? Or is it slower because it checks every number for being a multiple of every smaller prime? I believe the answer to the second question is negative, so it leaves the first one. I don't have time to analyse further but it does appear that it might be a problem for infinite sequences.
For anyone interested, this can be done in C# with IEnumerable and the keyword 'yield'. Essentially you can "describe" a list and a function will yield the next value on demand.
It’s a pleasure to listen to Prof. Hutton, he speaks clearly, well-structured and without ever saying “um” or anything. Also I love your videos on Haskell, it’s an elegant language that deserves a broader audience!
@@morgansearle3912 'Hutton' is a toponymic surname from Scotland, specifically from Berwickshire. That, of course, doesn't mean that he is from there, just his name is.
I’m from Glasgow, but have spent some time in Australia, Sweden, The Netherlands, and England, so my accent is a bit all over the place! But I hope it still sounds a bit Scottish :-)
@@aliedperez if you use the Integer type instead of Int, it uses arbitrarily wide integer values. Perfect for infinity, so long as you have enough RAM.
This video was extremely enjoyable and interesting. Prof. Hutton was extremely clear and concise in his explanation. Hope to see more content from him. Thank you for this video. It kind of made me want to try to approach functional programming once more.
@@Pat315 The wondrous thing is that it takes four lines of code to do what C would take 20 to do, with much uglier syntax, and no polymorphic re-usability for the code creating laziness.
You can do exactly this with Java. Check Stream API. Update: I was wrong. I couldn't implement this in Java. The Stream API has a lot of deficiency. You can do this in Scala though. Or in Java using the jOOL library.
@@kleavenae You should be able to. Streams include the filtering etc. and the starting infinite stream can be generated via Stream.iterate, e.g., Stream.iterate(1, i -> i + 1) for [1..]. I'd expect most stream/sequence/range libraries across langauges nowadays to handle infinite streams, just through a method other than Haskell's inherent laziness.
I'm learning a bit of Haskell with the help of the book "Programming in Haskell", can you imagine how surprised i was when i realized the man in the video IS the Graham Hutton author of the book?! Btw i strongly recommend his book, a very clear and fun introduction to Haskell. As other people in the comment section I would definitely enjoy to see more videos with the professor
For those who don't understand list comprehension, the sieve program can be written as follows using filter instead: primes = sieve [2..] sieve (p:ps) = p : sieve (filter (\x -> x `mod` p /= 0) ps)
With an object oriented programming language using the sieve of eristothanes and making it dynamically increase as more output is required would be way more complicated. This is awesome!
Thank you very much for this video about this very elegant way of programming in a functional language. And kudos to Mr Hutton for his friendly, relaxed, controlled, and - most important - understandable way of explaining this topic.
I know C# copied the functional languages here but Haskel really reminds me of LINQ and enumerables in C#, except without the pureness and elegance. But nevertheless kind of shocking how I intuitively understood all the programming without ever once having written Haskell.
Alot of functional concepts are adapted in other languages. Even monads which are irritating for most newcomers in Haskell are actually quite deeply built in to languages such as javascript (async/await)
I am just fascinated by how practical Haskell is. I always thought of it as an old, assembly-like language. Now I want to learn more haskell or see if python can do this as well.
Was so impressed. Decide to implement it in python: def inf_numbers(start_with): while True: yield start_with start_with += 1 def sief(iterator): prime = next(iterator) yield prime while True: yield next(sief(i for i in iterator if i%prime!=0)) primes = sief(inf_numbers(2)) list(islice(primes, 1000)) UPD: After reasonable comments code become simpler from itertools import islice, count def sief(iterator): prime = next(iterator) yield prime yield from sief(i for i in iterator if i%prime!=0) primes = sief(count(2)) list(islice(primes, 10)) But this version will work slower and because of yield from instruction will fail to get more than 1500 primes due to fact of maximum recursion. Where first sief implementation will work well on bigger size of iterations.
Too complicated! This one is simpler: def sieve (prime = None, *rest): if not prime: return [] return [prime, *sieve(*[x for x in rest if x % prime != 0])] primes = sieve(*range(2, 30))
@@khai96x Yep, your simpler, but my implementation aimed to use infinite generator, I can iterate through it forever, and it used lazy evaluation as in original code on haskell, where yours code will be evaluated on passing into function.
Axel Ulmestig there’s no specific optimisation in Haskell for tail calls, all calls to functions are simply jumps to that function, which gives tail call optimisation for free if the function called in the tail is a recursive call. This means you get the same “optimisation” in mutually recursive loops too, f x = ... g y; g x = ... f y is no different to direct recursion.
Alex Mason I don't think that's entirely true. For example, in the function f x = sqrt (exp x) It would be ok to jump to sqrt but not to exp. If you jumped to exp, you would never call sqrt, so you would return the wrong thing unless you remembered to jump back at the end, which requires a call stack.
Games14159 GHC’s implementation of Haskell does not use a call stack, it uses a stack of evaluations - you’re forgetting that Haskell is lazy, so the evaluation is actually sqrt , so sqrt will jump to exp and push its computation onto the stack of evaluations to perform after exp has been evaluated. If you look at the code produced by GHC, there are no call or ret instructions generated for Haskell functions. We have a stack, but it is not a call stack.
It would have been nice if he would have explained how the lazy evaluation and recursion actually works together. He simply stated "it removes all of the multiples of 2." No it doesn't. It removes them when it needs to, but he completely glossed over that part.
Thank you for showing this, it's really neat and I hope I might one day find a use for this, hopefully in chemistry, which I study; but at least my brain will have one more concept to play around with.
What I dont understand is, the language was not able to close the search for values below 100 since it didn't know there are not going to be any more values below 100 since the list goes on and on. So how can it move on from dividing by 2 in the last example to dividing by 3? How does it know there are no more values that can be divided by 2?
It never actually completes the first pass of dividing by two. It does just enough--one element at a time--to get the elements you need. That's part of how the lazy evaluation works.
Hey guys!! I really love your videos but I’ve got hearing comprehension issues so they’re hard for me to understand. If it’s not too much to ask, could you guys possibly add subtitles? I’m a computer science major and I’d really love to be able to fully enjoy your videos!!
Numberphile's proof of it was wrong (specifically the very first identity they stated was wrong, from which they derived everything else). Unsurprisingly the sum of all natural numbers doesn't actually converge.
Ehh... the analytic continuation thing is the sort of deal where you cannot apply the form of the zeta-function defined for x over 1 for inputs less than or equal to 1. I.e. we don't know if the zeta function applied to -1 actually looks like 1+2+3+4+..., which would be suggested by zeta(x) = 1^-x + 2 ^ -x + ..., but that definition only works for x > 1. Besides, the sum of all natural numbers clearly diverges.
Except that this is *not* the sieve of Eratosthenes, because he uses mod, i. e. division. Do it with pen and paper and you will never divide anything. Division makes this algorithm a different and more expensive one.
Lazy evaluation is convenient for specific cases but it should be noted that it will substantially slow a program that repeatedly uses the same data structure, in fact lazyness/eagerness in a language is analogous to the larger choice of interpret/pre-compile. When I say repeatedly I mean millions or billions of iterations, recursions, or general laps around a loop, which is something that would likely be encountered more often in programs that would choose a fully pre-compiled language than in programs that would choose an on-demand interpreted language.
Haskell can be compiled, but does suffer performance and stable ABI problems even when compiled. I think the solution to this is to discover a parallel to DeMorgan's laws for actually infinite structures and arbitrarily large finite structures that would allow for some "conjunctive normal form" where all the infinity is at the outermost level and each "step" can be eagerly evaluated while the OS manages the laziness with a scheduling algorithm.
*_...do you compose your programs in UTF∞..._* *_...I recall hearing that a Honeywell machine did infinite-byte-strings, ca 1970's..._* *_..."eager...lazy" translates to "greedy...nongreedy" in Amer. JavaScript RegExp..._* *_...((do the Brits calls it, 'Kavascript...Avascript...' I prefer just "script" anyway))..._*
The cooler thing is that `tak 5 [1..]` doesn't even evaluate the values of the list, it evaluates to something like [_, _, _, _, _] where each _ is a delayed computation which is resolved by the `show` function when you print the list into the console
Laziness is awesome! I’ve used it to make minimax game tree searches in a much more natural way than I would otherwise. Separating control from data really helps in those situations
I made my sieve in C++ a few years ago, I did double prime steps to reduce the processing needed, and used a list of booleans to save on ram usage. In about a second or two I could output a file with a list of all the primes up to 100,000,000. This looks like fun, but when you want speed you really need to tweak the process on a lower level.
Note that Haskell boxes integers and uses bigints by default. Both of these slow the program down. There is a data type called Word representing machine-precision integers, and there are also GHC-specific options for unboxed integers. It's not pretty, but you can do low-level stuff. That kind of speed isn't the default, but it is possible.
If you really needed a list of primes, I'm sure someone has a few gigabyte file somewhere with a really really long list. The question becomes how fast do you want to search it, and how many Primes do you need stored in RAM for very fast access. I smell a new type of encryption that requires computers with a list of 200 GB of primes in system memory, because it needs to lookup and sum millions of primes to decode messages. An SSD would be way too slow to decode a message. One method, add a bunch of padding to a 1 kb message to get it to 100 kb. Convert it to a number. Start subtracting very very big primes. Make a list of the primes you subtracted from it. To decode you would need to be able to look up primes by their location in the list. Example decoded message: "this is a secret" Example coded message: 2, 3, 4, 12, 21, 25, 88, 143, 2975, 10278, 172193, To decode you take the second prime, 3rd prime, 4th prime etc, and add them all together, then convert from a number to a string with a simple perfect hash function.
In C#, define your function as returning IEnumerable and then use "yield return" to send back the values. (Yes, Haskell's way is way better. But some of these ideas are starting to leak out into the mainstream.)
There's a heck of a lot of Haskellers working on various C# things at Microsoft and Microsoft Research - Linq is famously inspired by haskell's use of Monads.
Python code, Haskell inspired : from itertools import count, islice def factors(x): yield from (i for i in range(1, x + 1) if x % i == 0) def is_prime(x): yield list(factors(x)) == [1, x] def primes(n_first): yield from islice((i for i in count(2) if is_prime(i)), n_first) for prime in primes(100000): print(prime)
Infinite Data Structures are quite practical... Yeah, for a problem which is fundamentally infinite, in circumstances where infinite runtime is acceptable. In other words, if you already have to deal with infinity, more infinity doesn't hurt. I'm disappointed that it doesn't pose any of the use cases of infinite data structures on a less conventional problem for them, such as a finite problem.
Benjamin Lehmann You can get more practical. If you have a stream of data that you can only process online, and you're not sure how long it will be, you can express transformations on the entire stream in a similar way.
Why would it get stuck? It's merely a filter on top of a map, it's generating one list of factors per number and if it's higher than two it's not a prime, I don't see a possibility for an infinite loop to get stuck on (besides the infinite counter iterator, of course)
@@Dorumin Which, although explained well, is kind of unseen here. The trick is lazy evaluation. Haskell hides that. Sometimes explicit is better than implicit.
@@robertkelleher1850 Which is why i love Rust iterators, that have a very clean implementation and it's always completely transparent. Just a next() method
C# is lazy when using IEnumerables and yields, and thus same thing could be done. The only down side is that it doesn't come with most functional programming list operations so you have to either write your own, or just download a library from nuget. And, it's kinda less clean to look at.
would it be possible to do a video explaining how haskell is actually able to keep track of these things in execution? As it runs through the infinite execution, what is it actually storing in the (finite) physical memory? If you left the program running for a long enough time, would it eventually run into errors from the finite physical constraints of the hardware it was running on?
*That is NOT the Sieve of Erathostenes!* Compare the sieve of eratosthenes: mark 2 prime mark 4 composite mark 6 composite mark 8 composite mark 10 composite mark 12 composite mark 3 prime mark 6 composite mark 9 composite mark 12 composite mark 5 prime mark 10 composite mark 15 composite mark 7 prime mark 11 prime Versus what the algorithm described here does: mark 2 prime check 3 divisible by 2 (no) mark 3 prime check 4 divisible by 2 (yes) check 5 divisible by 2 (no) check 5 disivible by 3 (no) mark 5 prime check 6 divisible by 2 (yes) check 7 divisible by 2 (no) check 7 divisible by 3 (no) check 7 divisible by 5 (no) mark 7 prime check 8 divisible by 2 (yes) check 9 divisible by 2 (no) check 9 divisible by 3 (yes) check 10 divisible by 2 (yes) check 11 divisible by 2 (no) check 11 divisible by 3 (no) check 11 divisible by 5 (no) check 11 divisible by 7 (no) check 12 divisible by 2 (yes) There is a huge difference! The Sieve of Eratosthenes never does any division/modulo operation! The distinctive feature of the Sieve is that it obtains the primes "for free"! It uses a known prime to remove known composite numbers but it never "compares" two primes! The algorithm presented here instead simply takes all the primes found until then and checks if the next number is divided by one of these. And this is quite slow. You can see that composite numbers are ruled out pretty fast when when your *x* is a prime number you end up having to check against all other prime numbers
Took me a while to process your comment. What you're basically saying is that he's not sieving out numbers of kind 'pn' by just adding 'p' over and over again, which is faster, he's just iterating over all of them and cheating by dividing numbers by 'p' to check if it is 'pn'. So yeah, you are right.
how does the program know, that it finishes searching primes less than 100 at 13:43 but does not know, if it finishes searching all numbers less than 100 at 03:16? isn't it contradictory?
The "takewhile" terminates upon reaching its condition, so as soon as it hits a single item in the list >100 it's done. If the list weren't sorted, it most likely wouldn't give a complete answer.
@@wliaputs Yeah but I mean, the entirety of functional programming is based on mathematical functions so that goes without saying. List comprehensions correspond more precisely with the set generator notation.
Because it doesn't :D well - at least not at any given time. It only ever filters one number at a time and passes it to the next command (or the console, at last) and only after that all finished doing whatever it wants to do, it takes the next number into concideration :)
I wish more students learning Haskell would go to this effort - lazy evaluation becomes completely obvious once you step through the definitions of the functions and look at what is being evaluated at each step. Gold star! 🌟
He's not _really_ generating an infinite list. He just gives boundaries (or just one) and then evaluates every element on its own. Thinking of it as filtering out infinite list is deceptive. It's just a stream of numbers. The example, nicely explained, is twisted to a format Haskell is good at processing. A lot of languages are good a dealing with infinite stream of data.
What's the difference between an infinite list and a stream of integers? If I apply some transformation to a stream and observe the resulting stream, the transformation has been applied to every element in the original stream to produce every element of the new stream I observe, and ever could observe. What's the problem with saying that the transformation has been applied to the whole stream?
In Haskell the difference it doesn't really matter but afaik most languages people use need lists to be well defined. So thinking of it as a stream of data instead, makes more sense. Trying to allocate memory for a list of infinite length sure is fun.
@@timh.6872 An infinite list is a list (an inductive structure) with infinite elements. A stream is a coinductive structure that looks like a list. Theoretically, we build lists up, but we break streams down.
at 13:47 how did takeWhile statement take a finite amount of time to find the numbers less than 100 from an infinite list and at 3:22 filter operation failed to submit the answer of all numbers in the infinite list less than 100 in finite amount of time?
I don't think I would have understood most of this if I hadn't used Lisp (for head/tail), Python (for generators), and been exposed to pattern matching in Erlang or Prolog. I didn't quite follow the syntax of sieve, even though I've implemented it before in other languages.
It's important to understand that "infinite" data structures can never be totally evaluated hints why they only work with lazy evaluation. Further the juxtaposition of infinite and data structures only makes any sense in languages where function and structure are the same thing called purely functional. Normally data structure is separate from function so lazy evaluation is accomplished with generators instead. However purely functional languages trade off random access for procedural access. It would seem Haskel would be the holy grail for complicated 3d rendering but this procedural trade off would make them excruciatingly slow. Which is why imperative object-oriented is best for game design. You can have both extremely complex data structures while also maintaining random access.
Completely wrong, you don't know that functional has entirely different data structures that have data sharing and is far better at parallelism. Also almost no games require anything close to cutting edge
It seems like In this style of programming, it's possible to accidentally altar the limits of the evaluation of a given functions terms, and cause runaway computation. But then doesn't that mean that you have to debug multiple functions simultaneously to prune out the problem arguments from the pipeline? How can a development environment help the programmer in that situation?
@@SuperManitu1 so in the case of 2, it wouldn't remove anything since 3 is next, right? But then when it evaluates 3 wouldn't it just go to 4 since it never made it that far when checking for 2 factors?
@@bonesmalin No, it still know that it has to remove all multiples of two, just does not do it yet. Every time you get the next number it checks if it should remove it or not. So when the first prime (2) is requested Haskell just returns it. When you ask for the next one, Haskell checks that it is not divisable by the previous primes (only 2 in this case) and of not, returns it. When you need the next prime it takes the next number from the natural numbers, checks if it is divisable by the previous primes (it is by 2), so we do not return it and try the next number. The point is everything happens only when you need the prime
An infinite list "acts" like a value in the language. It can passed to and returned from functions as well as be assigned to variables. When was the last time you assigned a while loop to a variable in C++?
Sorry I was a business language programmer for 25 years Clipper VB and SQL (don't laugh it paid the bills and bought my house) When I see syntax like (1...10) I just think array. The computer doesn't actually have to create that structure in memory but it does 'exist' in my mental image of the solution to the problem. (1...) is just a neat way of declaring an array with no upper bounds. Which instantly makes me think does the syntax (...100) exist in Haskell. I know in the rarefied atmosphere of computer science these concepts are different things but delighting in showing the shortest possible programme code that the compiler interpreter is designed to handle doesn't prove anything other than what the language is optimised for not it's inherent strength.. Watch a video with Brian Kernighan on successful language design. He has a text processing example where he ends up showing an awk program that is basically one word. Being Brian his tongues is firmly in his cheek as he works through the comparisions BTW I've seen some very clever and experienced people do amazing and useful things with DOS batch files, BASH scripts and SQL Procedures.
You don't, you just process the return value of the function containing the while true loop. I know this shows my complete misunderstanding of functional programming but for all Prof Huttons undoubted fluency and knowledge I just want a simple functional progamming 101 definition. Please can someone give a simple straigtforward example of something that is possible in FP that is impossible or at least tortuous in other language styles. I repeat using examples which show how little code you need to type in any given language is pointless. In clipper I could do something like @ 10, 10 SAY "Acct No" GET Customer->Acct_No PICT "999999" VALID Customer->Acct_No > 0 READ How much Haskell or C would you need ??
JavaScript implementation using generators (and making sieve iterative instead of recursive to avoid call stack overflow): function* naturalNumbers(from = 1) { let n = from; while (true) { yield n++; } } function every(predicate, xs) { for (const x of xs) { if (!predicate(x)) return false; } return true; } function* takeWhile(predicate, xs) { for (const x of xs) { if (!predicate(x)) return; yield x; } } function* sieve() { const primes = []; for (const x of naturalNumbers(2)) { if (every( p => x % p !== 0, takeWhile(p => p
One of the most clear explanations of anything that I've ever heard.
I don't know why this comment has me laughing so hard lolol, but I couldn't agree more.
Professor Hutton is a fantastic teacher. The Lambda Calculus video is another prime example of his comprehension of the concepts and how to convey the knowledge effectively.
Unfortunately in the end they made a huge mistake. They claim to have implemented the Sieve while the algorithm implemented is just smart trial division (the Sieve does no modulo operation. It uses a prime to rule out known *composites*, while the algorithm here simply checks for each number if it is a multiple of a prime we found before which is asymptotically slower).
This shows how subtle mistakes can be in math&computer science and make tons of other people fall for them even when explained slowly and clearly.
Agreed
@@Giacr45 Is it slower because of the time complexity of modulo operation which is higher for arbitrarily large numbers? Or is it slower because it checks every number for being a multiple of every smaller prime? I believe the answer to the second question is negative, so it leaves the first one. I don't have time to analyse further but it does appear that it might be a problem for infinite sequences.
For anyone interested, this can be done in C# with IEnumerable and the keyword 'yield'. Essentially you can "describe" a list and a function will yield the next value on demand.
It’s a pleasure to listen to Prof. Hutton, he speaks clearly, well-structured and without ever saying “um” or anything. Also I love your videos on Haskell, it’s an elegant language that deserves a broader audience!
Hes got quite a gift, I don't even think hes reading from a script
True, but his accent is making me so curious, it's like Scottish-adjacent or something and I can't wrap my head around it
@@morgansearle3912
'Hutton' is a toponymic surname from Scotland, specifically from Berwickshire. That, of course, doesn't mean that he is from there, just his name is.
How do you know he doesn't edit out his "um"s?
I’m from Glasgow, but have spent some time in Australia, Sweden, The Netherlands, and England, so my accent is a bit all over the place! But I hope it still sounds a bit Scottish :-)
Simple and beautiful. Also, this professor is a joy to listen to. He gives very clear and concise explanations.
I feel like I just watched a 15 minute commercial for Haskell..
That describes every one of Hutton's videos on this channel.
try it. ;)
That describes every conversation with every Haskell programmer I've ever had
All of this guy's videos are like that.
It's free :-)
"infinite list of twin primes" - do you have a secret proof you're keeping hidden from us all?
yes, just let the program run forever.
:')
@@aka5 and make sure you're using very wide integers :-)
@@aliedperez if you use the Integer type instead of Int, it uses arbitrarily wide integer values. Perfect for infinity, so long as you have enough RAM.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Very understandable english, clear presentation and formidable examples!
This video was extremely enjoyable and interesting. Prof. Hutton was extremely clear and concise in his explanation.
Hope to see more content from him.
Thank you for this video. It kind of made me want to try to approach functional programming once more.
As a classical programmer, this is blowing my mind and making me wanna pick up Haskell.
They have a browser-based tutorial directly on the Haskell landing page. Fills around 1/2h.
just learn the functional part of Java :)
@ That is just as cool as it is horrible when you think of all those function objects and garbage collection
@@zitt4147literally who cares Christ you're making CRUD apps
Is a classical programmer a guy that wears a toga while coding?!
Functional programming is a wondrous thing, isn't it?
Bro it's like four lines of code. Take your cringe elsewhere.
@@Pat315 The wondrous thing is that it takes four lines of code to do what C would take 20 to do, with much uglier syntax, and no polymorphic re-usability for the code creating laziness.
@@Pat315 Haskell is the mathematicians language
@@suponjubobu5536 stop being such a virgin
This makes me want to learn Haskell SO MUCH!
One does not simply learn Haskell
@@framegrace1 One does simply learn Haskell, check out the book "Learn you a Haskell for great good"
You can do exactly this with Java. Check Stream API.
Update: I was wrong. I couldn't implement this in Java. The Stream API has a lot of deficiency. You can do this in Scala though. Or in Java using the jOOL library.
@@Masterplan79th One just bashes one's head repeatedly against the compiler's type checker until it compiles. But once it does, it runs ;)
@@kleavenae You should be able to. Streams include the filtering etc. and the starting infinite stream can be generated via Stream.iterate, e.g., Stream.iterate(1, i -> i + 1) for [1..]. I'd expect most stream/sequence/range libraries across langauges nowadays to handle infinite streams, just through a method other than Haskell's inherent laziness.
Professeur Graham, you are such a great presentator ! It makes this video very enjoyable to watch. Thank you.
I'm learning a bit of Haskell with the help of the book "Programming in Haskell",
can you imagine how surprised i was when i realized the man in the video IS the Graham Hutton author of the book?!
Btw i strongly recommend his book, a very clear and fun introduction to Haskell.
As other people in the comment section I would definitely enjoy to see more videos with the professor
Glad you are enjoying the book Mario :-)
I'm really enjoying Brady's editing in this one.
you mean Sean's editing...
For those who don't understand list comprehension, the sieve program can be written as follows using filter instead:
primes = sieve [2..]
sieve (p:ps) = p : sieve (filter (\x -> x `mod` p /= 0) ps)
This should definitely be cross-posted to the Numberphile channel.
'Just search for the obvious thing' 😂😂
"The first step is to write down the infinite list all the way up to infinity." Yeah, lemme just do that real quick. *never gets to step 2*
This is enough to turn someone into an intuitionist !
It looks like Haskell is pretty efficient for writing codes for numerical computation.
In 2 line you wrote Sieve of Eratosthenes
With an object oriented programming language using the sieve of eristothanes and making it dynamically increase as more output is required would be way more complicated. This is awesome!
Thank you very much for this video about this very elegant way of programming in a functional language. And kudos to Mr Hutton for his friendly, relaxed, controlled, and - most important - understandable way of explaining this topic.
2:32 So no proof that 1 + 2 + 3... = -1/12?
I don't think you're gonna believe me, but 1 +2 +3+... does not equal to -1/12. In fact, this sum doesn't equal to any number, because it diverges
Артём Мухамед-Каримов МПБ-802 based and redpilled
This is the first time I've thought Haskell looks elegant.
I know C# copied the functional languages here but Haskel really reminds me of LINQ and enumerables in C#, except without the pureness and elegance. But nevertheless kind of shocking how I intuitively understood all the programming without ever once having written Haskell.
Alot of functional concepts are adapted in other languages. Even monads which are irritating for most newcomers in Haskell are actually quite deeply built in to languages such as javascript (async/await)
this was great. I'd love to see more videos with actual code
Fantastic introduction to Haskell!
I love the videos with Graham Hutton and Haskell.
I am just fascinated by how practical Haskell is. I always thought of it as an old, assembly-like language. Now I want to learn more haskell or see if python can do this as well.
Melih Durmaz Don't confuse Haskell with Pascal...
Was so impressed. Decide to implement it in python:
def inf_numbers(start_with):
while True:
yield start_with
start_with += 1
def sief(iterator):
prime = next(iterator)
yield prime
while True:
yield next(sief(i for i in iterator if i%prime!=0))
primes = sief(inf_numbers(2))
list(islice(primes, 1000))
UPD: After reasonable comments code become simpler
from itertools import islice, count
def sief(iterator):
prime = next(iterator)
yield prime
yield from sief(i for i in iterator if i%prime!=0)
primes = sief(count(2))
list(islice(primes, 10))
But this version will work slower and because of yield from instruction will fail to get more than 1500 primes due to fact of maximum recursion. Where first sief implementation will work well on bigger size of iterations.
Too complicated! This one is simpler:
def sieve (prime = None, *rest):
if not prime: return []
return [prime, *sieve(*[x for x in rest if x % prime != 0])]
primes = sieve(*range(2, 30))
@@khai96x Yep, your simpler, but my implementation aimed to use infinite generator, I can iterate through it forever, and it used lazy evaluation as in original code on haskell, where yours code will be evaluated on passing into function.
@@MichaelLikvidator
Fair enough, but your code can still be simplified: Remove 'while True', use 'yield from'
@@khai96x Thnx
Also, python already has inf_numbers, it's called range
Whoever edited the thumbnail made a huge mistake. Buzz Lightyear's ICONIC balaclava covers his entire head. Not just his neck. Nice try.
Real buzz friends represent
If that's what you are taking away from this video, you may have missed the point of this video.... :)
@@preferredimage It may not be the only thing in this video, but it is the most important thing.
@@preferredimage without buzz lightyear there is no hascall there are no dreams
If he goes into the function recursively how come he doesn't get a stack overflow eventually?
"tail call optimization". The compiler (or interpreter in this case) converts it to a loop under the hood
Axel Ulmestig there’s no specific optimisation in Haskell for tail calls, all calls to functions are simply jumps to that function, which gives tail call optimisation for free if the function called in the tail is a recursive call. This means you get the same “optimisation” in mutually recursive loops too, f x = ... g y; g x = ... f y is no different to direct recursion.
Alex Mason I don't think that's entirely true. For example, in the function
f x = sqrt (exp x)
It would be ok to jump to sqrt but not to exp. If you jumped to exp, you would never call sqrt, so you would return the wrong thing unless you remembered to jump back at the end, which requires a call stack.
Games14159 GHC’s implementation of Haskell does not use a call stack, it uses a stack of evaluations - you’re forgetting that Haskell is lazy, so the evaluation is actually sqrt , so sqrt will jump to exp and push its computation onto the stack of evaluations to perform after exp has been evaluated. If you look at the code produced by GHC, there are no call or ret instructions generated for Haskell functions. We have a stack, but it is not a call stack.
Alex Mason So it’s not exactly a call stack, and it’s not the processor’s stack; it’s a stack of computations. TIL, thanks!
It would have been nice if he would have explained how the lazy evaluation and recursion actually works together. He simply stated "it removes all of the multiples of 2." No it doesn't. It removes them when it needs to, but he completely glossed over that part.
Wow! Its fascinating how many languages really constrain what programmers can even think about.
This was supremely interesting, thank you. I'm glad others have picked up on his excellent presentation too.
Thank you for showing this, it's really neat and I hope I might one day find a use for this, hopefully in chemistry, which I study; but at least my brain will have one more concept to play around with.
What I dont understand is, the language was not able to close the search for values below 100 since it didn't know there are not going to be any more values below 100 since the list goes on and on.
So how can it move on from dividing by 2 in the last example to dividing by 3? How does it know there are no more values that can be divided by 2?
It never actually completes the first pass of dividing by two. It does just enough--one element at a time--to get the elements you need. That's part of how the lazy evaluation works.
Hey guys!! I really love your videos but I’ve got hearing comprehension issues so they’re hard for me to understand. If it’s not too much to ask, could you guys possibly add subtitles? I’m a computer science major and I’d really love to be able to fully enjoy your videos!!
Subtitles for the main video and extra bits are now up. It takes a few days for these once the videos come out as they are done by hand.
2:30 should've given us -1/12
Daniel Astillero Numberphile crossover alert.
Numberphile's proof of it was wrong (specifically the very first identity they stated was wrong, from which they derived everything else). Unsurprisingly the sum of all natural numbers doesn't actually converge.
Debated
Analytical continuation provides us the result of -1/12
Ehh... the analytic continuation thing is the sort of deal where you cannot apply the form of the zeta-function defined for x over 1 for inputs less than or equal to 1.
I.e. we don't know if the zeta function applied to -1 actually looks like 1+2+3+4+..., which would be suggested by zeta(x) = 1^-x + 2 ^ -x + ..., but that definition only works for x > 1.
Besides, the sum of all natural numbers clearly diverges.
Except that this is *not* the sieve of Eratosthenes, because he uses mod, i. e. division. Do it with pen and paper and you will never divide anything. Division makes this algorithm a different and more expensive one.
2:15 note that most of the time is actually spent on outputting into stdout, so its a lot quicker
Lazy evaluation is convenient for specific cases but it should be noted that it will substantially slow a program that repeatedly uses the same data structure, in fact lazyness/eagerness in a language is analogous to the larger choice of interpret/pre-compile.
When I say repeatedly I mean millions or billions of iterations, recursions, or general laps around a loop, which is something that would likely be encountered more often in programs that would choose a fully pre-compiled language than in programs that would choose an on-demand interpreted language.
Haskell can be compiled, but does suffer performance and stable ABI problems even when compiled. I think the solution to this is to discover a parallel to DeMorgan's laws for actually infinite structures and arbitrarily large finite structures that would allow for some "conjunctive normal form" where all the infinity is at the outermost level and each "step" can be eagerly evaluated while the OS manages the laziness with a scheduling algorithm.
What in the world are you talking about and what is your obsession with performance
Brilliant video, we'd like more!
why cant you make a playlist with Graham Hutton :( they are not grouped!
Great video, glad I've watched it.
*_...do you compose your programs in UTF∞..._*
*_...I recall hearing that a Honeywell machine did infinite-byte-strings, ca 1970's..._*
*_..."eager...lazy" translates to "greedy...nongreedy" in Amer. JavaScript RegExp..._*
*_...((do the Brits calls it, 'Kavascript...Avascript...' I prefer just "script" anyway))..._*
The cooler thing is that `tak 5 [1..]` doesn't even evaluate the values of the list, it evaluates to something like [_, _, _, _, _] where each _ is a delayed computation which is resolved by the `show` function when you print the list into the console
I absolutely love functional programming. Definitely my favorite paradigm
Laziness is awesome! I’ve used it to make minimax game tree searches in a much more natural way than I would otherwise. Separating control from data really helps in those situations
You can do that in any programming language. The trick is to not generate the list internally unless the user calls a function on the list.
I made my sieve in C++ a few years ago, I did double prime steps to reduce the processing needed, and used a list of booleans to save on ram usage. In about a second or two I could output a file with a list of all the primes up to 100,000,000.
This looks like fun, but when you want speed you really need to tweak the process on a lower level.
Note that Haskell boxes integers and uses bigints by default. Both of these slow the program down. There is a data type called Word representing machine-precision integers, and there are also GHC-specific options for unboxed integers. It's not pretty, but you can do low-level stuff. That kind of speed isn't the default, but it is possible.
why not just build a dedicated chip that computes primes, that would be faster than any software solution on consumer chips
If you really needed a list of primes, I'm sure someone has a few gigabyte file somewhere with a really really long list. The question becomes how fast do you want to search it, and how many Primes do you need stored in RAM for very fast access.
I smell a new type of encryption that requires computers with a list of 200 GB of primes in system memory, because it needs to lookup and sum millions of primes to decode messages.
An SSD would be way too slow to decode a message.
One method, add a bunch of padding to a 1 kb message to get it to 100 kb. Convert it to a number. Start subtracting very very big primes. Make a list of the primes you subtracted from it. To decode you would need to be able to look up primes by their location in the list.
Example decoded message: "this is a secret"
Example coded message: 2, 3, 4, 12, 21, 25, 88, 143, 2975, 10278, 172193,
To decode you take the second prime, 3rd prime, 4th prime etc, and add them all together, then convert from a number to a string with a simple perfect hash function.
In C#, define your function as returning IEnumerable and then use "yield return" to send back the values.
(Yes, Haskell's way is way better. But some of these ideas are starting to leak out into the mainstream.)
There's a heck of a lot of Haskellers working on various C# things at Microsoft and Microsoft Research - Linq is famously inspired by haskell's use of Monads.
Why did the program stop when using takeWhile
takeWhile stops when the condition fails so it terminates even with the infinite list; filter tries to find all values that satisfy the condition
@@pedrovasconcelos8260 Thanks!
Python code, Haskell inspired :
from itertools import count, islice
def factors(x):
yield from (i for i in range(1, x + 1) if x % i == 0)
def is_prime(x):
yield list(factors(x)) == [1, x]
def primes(n_first):
yield from islice((i for i in count(2) if is_prime(i)), n_first)
for prime in primes(100000):
print(prime)
Infinite Data Structures are quite practical... Yeah, for a problem which is fundamentally infinite, in circumstances where infinite runtime is acceptable. In other words, if you already have to deal with infinity, more infinity doesn't hurt. I'm disappointed that it doesn't pose any of the use cases of infinite data structures on a less conventional problem for them, such as a finite problem.
Benjamin Lehmann You can get more practical. If you have a stream of data that you can only process online, and you're not sure how long it will be, you can express transformations on the entire stream in a similar way.
How long does the program run before the macbook runs out of memory?
I was expecting the two line program for generating all the primes out of the infinite list to get stuck dividing numbers by 2
Yes, I dont understand why that didnt happen?
Why would it get stuck? It's merely a filter on top of a map, it's generating one list of factors per number and if it's higher than two it's not a prime, I don't see a possibility for an infinite loop to get stuck on (besides the infinite counter iterator, of course)
@@Dorumin Which, although explained well, is kind of unseen here. The trick is lazy evaluation. Haskell hides that. Sometimes explicit is better than implicit.
@@robertkelleher1850 Which is why i love Rust iterators, that have a very clean implementation and it's always completely transparent. Just a next() method
This is my favourite Prof Hutton video to date. (Daaaay'm Haskell is elegant. Its so sexy that it feels impossible.)
C# is lazy when using IEnumerables and yields, and thus same thing could be done. The only down side is that it doesn't come with most functional programming list operations so you have to either write your own, or just download a library from nuget. And, it's kinda less clean to look at.
Why does the sieve program not hang trying to remove every number divisible by two the way the earlier program hung looking for numbers less than 100?
Because the list keeps feeding it successive numbers, where as in the former, the list stops at 100.
More like this please that was very interesting. (Even in a language which I don't "Speak" as it were)
will the twin result in all the primes getting generated twice, or is the zip with tail smart enough to use the same list?
would it be possible to do a video explaining how haskell is actually able to keep track of these things in execution? As it runs through the infinite execution, what is it actually storing in the (finite) physical memory? If you left the program running for a long enough time, would it eventually run into errors from the finite physical constraints of the hardware it was running on?
*That is NOT the Sieve of Erathostenes!*
Compare the sieve of eratosthenes:
mark 2 prime
mark 4 composite
mark 6 composite
mark 8 composite
mark 10 composite
mark 12 composite
mark 3 prime
mark 6 composite
mark 9 composite
mark 12 composite
mark 5 prime
mark 10 composite
mark 15 composite
mark 7 prime
mark 11 prime
Versus what the algorithm described here does:
mark 2 prime
check 3 divisible by 2 (no)
mark 3 prime
check 4 divisible by 2 (yes)
check 5 divisible by 2 (no)
check 5 disivible by 3 (no)
mark 5 prime
check 6 divisible by 2 (yes)
check 7 divisible by 2 (no)
check 7 divisible by 3 (no)
check 7 divisible by 5 (no)
mark 7 prime
check 8 divisible by 2 (yes)
check 9 divisible by 2 (no)
check 9 divisible by 3 (yes)
check 10 divisible by 2 (yes)
check 11 divisible by 2 (no)
check 11 divisible by 3 (no)
check 11 divisible by 5 (no)
check 11 divisible by 7 (no)
check 12 divisible by 2 (yes)
There is a huge difference!
The Sieve of Eratosthenes never does any division/modulo operation!
The distinctive feature of the Sieve is that it obtains the primes "for free"! It uses a known prime to remove known composite numbers but it never "compares" two primes! The algorithm presented here instead simply takes all the primes found until then and checks if the next number is divided by one of these.
And this is quite slow. You can see that composite numbers are ruled out pretty fast when when your *x* is a prime number you end up having to check against all other prime numbers
Took me a while to process your comment. What you're basically saying is that he's not sieving out numbers of kind 'pn' by just adding 'p' over and over again, which is faster, he's just iterating over all of them and cheating by dividing numbers by 'p' to check if it is 'pn'.
So yeah, you are right.
...I was looking at Python and getting scared of weird funny one-liners it has.
This makes me even more scared.
how does the program know, that it finishes searching primes less than 100 at 13:43 but does not know, if it finishes searching all numbers less than 100 at 03:16? isn't it contradictory?
The "takewhile" terminates upon reaching its condition, so as soon as it hits a single item in the list >100 it's done. If the list weren't sorted, it most likely wouldn't give a complete answer.
So I tried his code on my Raspberry Pi. Here's my primes.hs file:
primeslow = filter (
->[x | x
That's why I love python generators and list comprehension
Ricard Miras I believe these are both features inspired by Haskell.
Exactly what I thought
List comprehension is inspired by math
@@wliaputs Yeah but I mean, the entirety of functional programming is based on mathematical functions so that goes without saying. List comprehensions correspond more precisely with the set generator notation.
immediately when i saw his face I said, "Its this Haskell dude again oh no"
Haskell!! shudder, I still have nightmare about this language, and I studied it 20 years ago!!!
What happened?
Videos like this make me want to learn Haskell, but then I wonder what I'd ever use that knowledge for.
This was great.
What causes that wavy banding in the sunlight in the window?
Damn I haven't looked at Haskell before but it's easy to see how optimized it is for this type of work. Really cool language!
What is the O() of this program?
I still don't understand why the part in brackets that filters all multiples of n didn't take an infinite time to run.
Because it doesn't :D
well - at least not at any given time. It only ever filters one number at a time and passes it to the next command (or the console, at last) and only after that all finished doing whatever it wants to do, it takes the next number into concideration :)
Because of laziness :D
Say I want to have the 3rd prime (primes !! 2), and I define
sieve (p:ps) = p : sieve [x | x
I wish more students learning Haskell would go to this effort - lazy evaluation becomes completely obvious once you step through the definitions of the functions and look at what is being evaluated at each step. Gold star! 🌟
He's not _really_ generating an infinite list. He just gives boundaries (or just one) and then evaluates every element on its own. Thinking of it as filtering out infinite list is deceptive. It's just a stream of numbers. The example, nicely explained, is twisted to a format Haskell is good at processing. A lot of languages are good a dealing with infinite stream of data.
What's the difference between an infinite list and a stream of integers? If I apply some transformation to a stream and observe the resulting stream, the transformation has been applied to every element in the original stream to produce every element of the new stream I observe, and ever could observe. What's the problem with saying that the transformation has been applied to the whole stream?
In Haskell the difference it doesn't really matter but afaik most languages people use need lists to be well defined. So thinking of it as a stream of data instead, makes more sense. Trying to allocate memory for a list of infinite length sure is fun.
Thinking about infinite data structure is the right way to go. It is just hard to understand if you start with a conventional language.
@@timh.6872 An infinite list is a list (an inductive structure) with infinite elements. A stream is a coinductive structure that looks like a list. Theoretically, we build lists up, but we break streams down.
I just realized that I love Haskell
Fun fact, this is technically a proof about the Riemann Hypothesis.
You just have to show if it's for or against.
Curious, what about time complexity when using an infinite set? What happens when I want prime numbers (not pseudoprime ) of n bits, n>100 ?
at 13:47 how did takeWhile statement take a finite amount of time to find the numbers less than 100 from an infinite list and at 3:22 filter operation failed to submit the answer of all numbers in the infinite list less than 100 in finite amount of time?
takeWhile runs as long as a Boolean is True in this case (
I don't think I would have understood most of this if I hadn't used Lisp (for head/tail), Python (for generators), and been exposed to pattern matching in Erlang or Prolog. I didn't quite follow the syntax of sieve, even though I've implemented it before in other languages.
This was actually really cool!
but how is this infinite list actually implemented in a language
is it just a function?
It's important to understand that "infinite" data structures can never be totally evaluated hints why they only work with lazy evaluation. Further the juxtaposition of infinite and data structures only makes any sense in languages where function and structure are the same thing called purely functional. Normally data structure is separate from function so lazy evaluation is accomplished with generators instead. However purely functional languages trade off random access for procedural access. It would seem Haskel would be the holy grail for complicated 3d rendering but this procedural trade off would make them excruciatingly slow. Which is why imperative object-oriented is best for game design. You can have both extremely complex data structures while also maintaining random access.
Completely wrong, you don't know that functional has entirely different data structures that have data sharing and is far better at parallelism. Also almost no games require anything close to cutting edge
Big respect for the white screen!
dark theme rules
You forgot the Amazon link to his Haskell book!
Every coding test involves prime numbers but I've been programming for like 10 years and I have never once needed a prime number.
I'm sorry, since when iterators are considers to be data structures?
Wat
It seems like In this style of programming, it's possible to accidentally altar the limits of the evaluation of a given functions terms, and cause runaway computation.
But then doesn't that mean that you have to debug multiple functions simultaneously to prune out the problem arguments from the pipeline? How can a development environment help the programmer in that situation?
How does the program not hang when it's removing all of the factors of 2 from the infinite list?
Because it doesnt. It only removes as much as needed to get to the next number
@@SuperManitu1 so in the case of 2, it wouldn't remove anything since 3 is next, right? But then when it evaluates 3 wouldn't it just go to 4 since it never made it that far when checking for 2 factors?
@@bonesmalin No, it still know that it has to remove all multiples of two, just does not do it yet. Every time you get the next number it checks if it should remove it or not.
So when the first prime (2) is requested Haskell just returns it. When you ask for the next one, Haskell checks that it is not divisable by the previous primes (only 2 in this case) and of not, returns it. When you need the next prime it takes the next number from the natural numbers, checks if it is divisable by the previous primes (it is by 2), so we do not return it and try the next number.
The point is everything happens only when you need the prime
@@SuperManitu1 thank you! It makes sense now.
When he typed in sum [1..] i was kinda expecting to see -1/12 😐
the operation was interrupted. It will print -1/12, If you give it enough time, that is infinite time
Do a video about modern cpu architecture
How can one possibly do programming on such a bright white theme? O.O
So what is the difference between a Haskell 'infinite' list and 'while true'
An infinite list "acts" like a value in the language. It can passed to and returned from functions as well as be assigned to variables. When was the last time you assigned a while loop to a variable in C++?
Sorry I was a business language programmer for 25 years Clipper VB and SQL (don't laugh it paid the bills and bought my house)
When I see syntax like (1...10) I just think array. The computer doesn't actually have to
create that structure in memory but it does 'exist' in my mental image of the solution to the problem. (1...) is just a neat way of declaring an array with no upper bounds.
Which instantly makes me think does the syntax (...100) exist in Haskell.
I know in the rarefied atmosphere of computer science these concepts are different things but delighting in showing the shortest possible programme code that the compiler interpreter is designed to handle doesn't prove anything other than what the language is optimised for not it's inherent strength..
Watch a video with Brian Kernighan on successful language design. He has a text processing example where he ends up showing an awk program that is basically one word. Being Brian his tongues is firmly in his cheek as he works through the comparisions
BTW I've seen some very clever and experienced people do amazing and useful things with DOS batch files, BASH scripts and SQL Procedures.
while true is a control structure not a data structure. How do you process the output of while true?
You don't, you just process the return value of the function containing the while true loop. I know this shows my complete misunderstanding of functional programming but for all Prof Huttons undoubted fluency and knowledge I just want a simple functional progamming 101 definition.
Please can someone give a simple straigtforward example of something that is possible in FP that is impossible or at least tortuous in other language styles.
I repeat using examples which show how little code you need to type in any given language is pointless. In clipper I could do something like
@ 10, 10 SAY "Acct No" GET Customer->Acct_No PICT "999999" VALID Customer->Acct_No > 0
READ
How much Haskell or C would you need ??
@@kmac499 I think this video gives you such an example. How do you do this in clipper?
You know what? Haskell is neat.
Will primes evaluate twice in the example with twins primes?
The list 'primes' will be computed once, and shared between the two uses in the twin primes example.
TL;DW: Haskell is intuitive for writing generators.
JavaScript implementation using generators (and making sieve iterative instead of recursive to avoid call stack overflow):
function* naturalNumbers(from = 1) {
let n = from;
while (true) {
yield n++;
}
}
function every(predicate, xs) {
for (const x of xs) {
if (!predicate(x)) return false;
}
return true;
}
function* takeWhile(predicate, xs) {
for (const x of xs) {
if (!predicate(x)) return;
yield x;
}
}
function* sieve() {
const primes = [];
for (const x of naturalNumbers(2)) {
if (every(
p => x % p !== 0,
takeWhile(p => p
Why doesn't "takeWhile (
"while
takeWhile keeps taking elements while the condition is true. Once it hits 101, the condition (