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

Download this episode

Download Video

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

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

 

Embed

Format

Available formats for this video:

Actual format may change based on video formats available and browser capability.

    More episodes in this series

    Related episodes

    The Discussion

    • User profile image
      wil2300

      Super excellent material. Great series thus far.

    • User profile image
      tomkirbygre​en

      *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
      paks8150

      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
      exoteric

      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
      dpratt71

      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
      chudq

      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.

    • User profile image
      Parmenio

      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
      rgruian

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

      Thanks!!

    • User profile image
      exoteric

      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
      heebeegeebee

      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
      jlomax

      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
      Jaunte

      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
      dev#

      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
      frou

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

    Comments closed

    Comments have been closed since this content was published more than 30 days ago, but if you'd like to send us feedback you can Contact Us.