C9 Lectures: Dr. Graham Hutton  Functional Programming Fundamentals Chapter 11 of 13
Description
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!
Chapter 1
Chapter 2
Chapter 3
Chapter 4
Chapter 5
Chapter 6
Chapter 7
Chapter 8
Chapter 9
Chapter 10
Chapter 11
Chapter 12
Chapter 13
Download
Right click or Alt+Enter to download this episode
 High Quality WMV (837.8 MB)
 MP3 (22.6 MB)
 Low Quality MP4 (256.7 MB)
 Mid Quality WMV (383.3 MB)
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 compiletime, based on some functionalgebra 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:
 Online Countdown Numbers Problem. Amazingly fast!
 Source codes in Haskell by Dr. Graham Hutton.
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 reintroducing 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 12%. 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 12% of cases, but the extra if will kick in the remaining 9899% 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!