Computerphile - 2018-11-06
Infinite data structures sound impossible. Professor Graham Hutton shows how laziness can win them over. EXTRA BITS: https://youtu.be/yCyBdeJmHM0 https://www.facebook.com/computerphile https://twitter.com/computer_phile This video was filmed and edited by Sean Riley. Computer Science at the University of Nottingham: https://bit.ly/nottscomputer Computerphile is a sister project to Brady Haran's Numberphile. More at http://www.bradyharan.com
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.
"infinite list of twin primes" - do you have a secret proof you're keeping hidden from us all?
@Alied Pérez Martínez 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.
WHich in Haskell no doubt is something like LEN(CHAR(AVG(1..)))
@Zangetsu: well, it depends on how long you leave it running. I was responding to @Akașșș "(...)just let the program run forever."
There just wasn't enough space at the margin of this video :-)
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!
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
He's Irish, with a bit of Glaswegian and generic-English accents thrown in to the mix. He's a professor, so he's probably picked them up at the various universities.
@Morgan Searle
'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 :-)
This makes me want to learn Haskell SO MUCH!
@FF Fanatic Try to implement it. You won't be able to. Java Streams are not lazy enough.
@kleavenae Are you sure they aren't lazy enough?
public static void main(String[] args) {
Iterator<Integer> iterator = Stream.iterate(2, i -> i + 1).iterator();
while (iterator.hasNext()) {
final Integer lastPrime = iterator.next();
System.out.print(lastPrime + ",");
iterator = StreamSupport.stream(Spliterators.spliteratorUnknownSize(iterator, Spliterator.ORDERED), false)
.filter((candidate) -> candidate % lastPrime != 0).iterator();
}
}
Admittedly it creates a new stream for every prime it finds and eventually throws a StackOverflowException (because every stream is seeded by the preceeding stream), I much prefer the stateful solution:
public static void main(String[] args) {
final List<Integer> primes = new ArrayList<>();
Stream.iterate(2, i -> i + 1).filter((candidate) -> {
for (final Integer prime : primes) {
if (candidate % prime == 0) {
return false;
}
}
return true;
}).forEach((prime) -> {
primes.add(prime);
System.out.print(prime + ",");
});
}
don't, it's a tremendous waste of time. what you saw here is the sales pitch, just like the quicksort example on their homepage. real Haskell is very shitty.
C++20 will also have this, BTW.
@Web Dog prove it
Functional programming is a wondrous thing, isn't it?
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.... :)
@Mat Recardo It may not be the only thing in this video, but it is the most important thing.
@Mat Recardo - If that's what you're taking away from his comment, you missed the point of his comment.
@Mat Recardo without buzz lightyear there is no hascall there are no dreams
Simple and beautiful. Also, this professor is a joy to listen to. He gives very clear and concise explanations.
Haskell is so incredibly elegant. I really need to start learning it, looks like a lot of fun!
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 :)
@Dénes Sebestyén That is just as cool as it is horrible when you think of all those function objects and garbage collection
'Just search for the obvious thing' 😂😂
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.
This is the first time I've thought Haskell looks elegant.
Professeur Graham, you are such a great presentator ! It makes this video very enjoyable to watch. Thank you.
This should definitely be cross-posted to the Numberphile channel.
Fantastic introduction to Haskell!
immediately when i saw his face I said, "Its this Haskell dude again oh no"
this was great. I'd love to see more videos with actual code
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
This is enough to turn someone into an intuitionist !
I mean ... Martin-Löf didn't do that already‽
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.
When he typed in sum [1..] i was kinda expecting to see -1/12 😐
If he goes into the function recursively how come he doesn't get a stack overflow eventually?
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 <the thunk which, when evaluated, computes exp x>, 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!
Have a look at the CPS monad. (Which is not how GHC is implemented, AFAIK.)
"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
Haskell!! shudder, I still have nightmare about this language, and I studied it 20 years ago!!!
What happened?
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.
You forgot the Amazon link to his Haskell book!
Videos like this make me want to learn Haskell, but then I wonder what I'd ever use that knowledge for.
This was actually really cool!
More like this please that was very interesting. (Even in a language which I don't "Speak" as it were)
This confirms my previous impression that I am not smart enough to use Haskell.
In C#, define your function as returning IEnumerable<YourType> 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.
...I was looking at Python and getting scared of weird funny one-liners it has.
This makes me even more scared.
but how is this infinite list actually implemented in a language
is it just a function?
Typically implemented using a generator
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 reccomend 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 :-)
lol let’s try summing infinity. I love you!
This feels like the "How to send an Email"-Video
/watch?v=szdbKz5CyhA
completely lost me at around 15 min in. I need to be more awake for this....
For anyone interested, this can be done in C# with IEnumerable<T> and the keyword 'yield'. Essentially you can "describe" a list and a function will yield the next value on demand.
5:00 the demand here is actually not the take - it's the reply trying to print out the result - if you don't print no list will ever be produced/taken at all
2:30 -1/12 lol
This here c/c++/matlab n00b is in awe of Haskell!
Oh dope I actually used the Sieve of Eratosthenes in a Discrete Structures class for doing some simple public key decrypting.
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.
Implemented in python3 as a generator :)
from itertools import count
def primes():
def sieve(nums):
p = next(nums)
yield p
yield from sieve(x for x in nums if x % p != 0)
yield from sieve(count(2))
I'm really enjoying Brady's editing in this one.
you mean Sean's editing...
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))...
I never thought Haskell could rhyme with Pascal
acid - 2018-11-06
I feel like I just watched a 15 minute commercial for Haskell..
Darik Datta - 2018-11-08
I was just about to say....
Thorsten Altenkirch - 2018-11-10
Ok and are you going to buy it?
Jeff Spaulding - 2018-11-11
@Thorsten Altenkirch I'll be more than happy to sell you a copy.
Thorsten Altenkirch - 2018-11-12
@Jeff Spaulding Got one already. Actually it is free.
Trae Watkins - 2019-02-24
@RecklessHeroism But this is the first time I thought ... "You know, Haskell might actually be useful for something"