C9 Lectures: Dr. Graham Hutton - Functional Programming Fundamentals Chapter 11 of 13
- Posted: Dec 10, 2009 at 11:15 AM
- 58,211 Views
- 18 Comments
Download
How do I download the videos?
- To download, right click the file type you would like and pick “Save target as…” or “Save link as…”
Why should I download videos from Channel9?
- It's an easy way to save the videos you like locally.
- You can save the videos in order to watch them offline.
- If all you want is to hear the audio, you can download the MP3!
Which version should I choose?
- If you want to view the video on your PC, Xbox or Media Center, download the High Quality WMV file (this is the highest quality version we have available).
- If you'd like a lower bitrate version, to reduce the download time or cost, then choose the Medium Quality WMV file.
- If you have a Zune, WP7, iPhone, iPad, or iPod device, choose the low or medium MP4 file.
- If you just want to hear the audio of the video, choose the MP3 file.
Right click “Save as…”
- High Quality WMV (PC, Xbox, MCE)
- MP3 (Audio only)
- MP4 (iPod, Zune HD)
- Mid Quality WMV (Lo-band, Mobile)
Yes. You read the title correctly! For today's lecture in the Functional Programming Fundamentals series of lectures the great Dr.
Graham Hutton, author of the Programming in Haskell book that Dr. Erik Meijer has based this lecture series on,
is guest lecturing Chapter 11 - The Countdown Problem! Thank you, Graham! What an honor and a treat to have you on Channel 9, especially in this context. 
This lecture was filmed in Dr. Hutton's office at the University of Nottingham. What is the Countdown Problem, exactly? It's a numbers game, based loosely on a very popular television series. The point is that you will need to use, well, functions to solve the Countdown Problem. Of course, it goes without saying that Haskell is very well suited to solve these kinds of problems.
Tune in and learn from a Haskell master. It should be clear that you will want to have had gone through the earlier episodes (if you are beginning with functional programming and Haskell, specifically) to get the most out of this lecture. That said, it's quite amazing to learn directly from the author himself. What a nice surprise!
Enjoy!
This lecture was filmed in Dr. Hutton's office at the University of Nottingham. What is the Countdown Problem, exactly? It's a numbers game, based loosely on a very popular television series. The point is that you will need to use, well, functions to solve the Countdown Problem. Of course, it goes without saying that Haskell is very well suited to solve these kinds of problems.
Tune in and learn from a Haskell master. It should be clear that you will want to have had gone through the earlier episodes (if you are beginning with functional programming and Haskell, specifically) to get the most out of this lecture. That said, it's quite amazing to learn directly from the author himself. What a nice surprise!
Enjoy!
Comments Closed
Comments have been closed since this content was published more than 30 days ago, but if you'd like to continue the conversation,
please create a new thread in our Forums,
or
Contact Us and let us know.
Follow the Discussion
Super excellent material. Great series thus far.
*FX Snoopy Dance! This is a completely awesome series, how ever are you guys going to top it? Can't wait to find out!
Just when I thought that this series couldn’t get better. Thanks Erick and Charles for putting so much effort into these lectures. Also, thanks to Dr. Hutton for taking the time to enlighten all of us.
This is extremely excellent! I'm going to burn this to DVDs and wrap in along with the extra book I also bought as a christmas gift.
I agree with the other responders, very excellent, thank you Dr. Hutton.
I have to say, in a way I was disappointed with the fact that program fusion was so effective at improving the performance of the program. One of the nicest properties of Haskell is that its functions are so very composable. And because Haskell is pervasively lazy, a lot of unnecessary computation is avoided. It seems to me that "by hand" program fusion runs somewhat counter to function composition.
I wonder if there would be some way of doing this kind of program fusion at compile-time, based on some function-algebra rules engine. Perhaps this relates to Dr. Huttons research.
I really enjoy this lecture. The only topic on this one is about Countdown Problem, a French TV show on resolving a mathematical problem. It'll hurt your brain if you try to resolve the problem.
Here are some links about CP:
I pasted the source codes into Notepad and saved as Coundown.hs. Then I used WinHugs to open or load it. To run the problem, just type in main:
Main>main
Enter the source numbers : [23, 12, 3, 5, 67, 78]
Enter the target number : 101
...
You will get one and all the solutions. Enjoy it!
By the way, I am not good at Haskell. Can anyone provide some hints on adding timestamps to get one and all solutions? In this way, I'll be able to see the start, end and execution time.
This series really is excellent.
As side bars off this I've really had numerous hours of exploration into functional concepts, finally got my head around Monads, rediscovered some fun in physics and maths (Monads led to Brian Beckman!), and it's fundamentally changed the way I code in c#.
Functional programming really does enable much easier expression of solutions in the first case. Even if further optimization of the solutions ends up re-introducing complexity.
It interesting also some of the impact this has had on my higher level designs ... much of the examples in functional programming centres around solutions at the small level (in code mostly) but the wider ideas of compositionality scale up extremely well to overall solution designs at the level of full enterprise applications.
Has anyone run this program (I mean the inefficient, naive, obvious first one) through the Supero Haskell Supercompiler? I would imagine that a supercompiler should be able to perform this kind of program fusion on its own, without human intervention. Sadly, I just can't seem to figure out how to install the thing.
Great post in an otherwise excellent series. I am looking forward to seeing all the remaining chapters.
Thanks!!
I remember seeing this Supero (actually thought it was called Superhero heh) Supercompiler and would also like to know how it would impact code like this. Still, that we see this fusing technique is very valuable.
In reply to chudq, here's a version with timing information: http://www.cs.nott.ac.uk/~gmh/countdown2.hs
Current implementations of fusion in compilers focus on completely eliminating intermediate data structures, whereas in this example the idea is to prune a data structure. So I would be surprised if existing compilers were able to perform this fusion step automatically.
I took Dr. Hutton's Haskell course at Nottingham several years ago and it was great. One of the best taught courses at the university and very interesting!
Absolutely fantastic. Up till now I though of comprehensions as conveniences, now I see they can be very elegant processing mechanisms.
I do wonder, if I tried to write this program using C# and as much Linq as possible, how far could I get?
Great series.
A few thoughts though:
- Division can further be optimized with first parameter not equal to 1 also (since fractions are not allowed).
- Would have liked to see performance figures for the second optimization only, since it didnt involve refactoring the "pretty" solution.
Good questions! I tried these changes out, and the extra division optimisation improves the performance of the final solution by around 1-2%. On the other hand, applying the second optimisation without the first only improves the performance of the brute force solution by around 20%, whereas the use of both techniques gives a speedup of around 100 times.
From my limited experience, i think adding the prevent div by 1 or mul by 1, might increase in may be 1-2% of cases, but the extra if will kick in the remaining 98-99% of cases, so average case would go down thereotically.
Again i haven't done the perf testing, so can't comment on actual implementation.
Extremely clearly presented lecture. You're a pro!
Remove this comment
Remove this thread
close