C9 Lectures: Dr. Graham Hutton - Functional Programming Fundamentals Chapter 11 of 13

Sign in to queue

More episodes in this series

Related episodes

The Discussion

  • User profile image

    Super excellent material. Great series thus far.

  • User profile image

    *FX Snoopy Dance! This is a completely awesome series, how ever are you guys going to top it? Can't wait to find out!

  • User profile image

    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. Smiley

  • User profile image

    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.

  • User profile image

    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.

  • User profile image

    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:



    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.

  • User profile image

    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.

  • User profile image
    Joerg W Mittag

    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.

  • User profile image

    Great post in an otherwise excellent series. I am looking forward to seeing all the remaining chapters.


  • User profile image

    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.

  • User profile image
    Graham Hutton

    In reply to chudq, here's a version with timing information: http://www.cs.nott.ac.uk/~gmh/countdown2.hs

  • User profile image
    Graham Hutton

    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.

  • User profile image

    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!

  • User profile image

    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?

  • User profile image

    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.

  • User profile image
    Graham Hutton

    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.

  • User profile image

    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.

  • User profile image

    Extremely clearly presented lecture. You're a pro!  Smiley

Add Your 2 Cents