C9 Lectures: Dr. Erik Meijer - Functional Programming Fundamentals, Chapter 1 of 13

Play C9 Lectures: Dr. Erik Meijer - Functional Programming Fundamentals, Chapter 1 of 13
Sign in to queue


Welcome to a new technical series on Channel 9 folded into a different kind of 9 format: C9 Lectures. These are what you think they are, lectures. They are not conversational in nature (like most of what you're used to on 9), but rather these pieces are entirely focused on education, coming to you in the form of a series of high quality technical lectures (1 or more per topic) on a single topic.

We kick off C9 Lectures with a journey into the world of Functional Programming with functional language purist and high priest of the lambda calculus, Dr. Erik Meijer (you can thank Erik for many of the functional constructs that have shown up in languages like C# and VB.NET. When you use LINQ, thank Erik in addition to Anders). 

Lecture Context:

Over the past two years, you've learned a fair amount about the functional programming paradigm's foray into general purpose imperative progamming languages (LINQ, Lambda's, etc in C# and VB.NET). And, of course, the newest language to join the Visual Studio family of languages, F#, is a functional language. You've heard us say how important functional language constructs are to the our current languages' capabilities to evolve in the right direction to meet the needs of the many-core future (the need for reliable and comprehensible concurrency, parallelism, etc) and, most importantly, to help vault computer programming into an age of compositionality (remember our talks on 9 regarding composability and evolution of software engineering as an engineering discipline?). Well, we decided to take a step back and teach you the fundamentals of functional programming at a level equivalent to any university. We even have a text book and professor who will expand our minds.

Dr. Erik Meijer will teach us Functional Programming Fundamentals using Haskell as the language for understanding the basic functional principles (in fact, the specific language isn't all that important, but Haskell is a pure functional language so it is entirely appropriate for learning the essential ingredients of functional programming. It is also a relatively small language and should be easy for you to get up to speed with Haskell once you understand the Why, What and How that underlies all functional languages...).

In Chapter 1, Dr. Meijer takes us through the fundamental fundamentals of functional programming: The philosophy and history of functional programming. As you can imagine, these lectures will go deeper and deeper as the chapters progress, but you need to understand the philosophical and historical contexts. This will provide a nice layer of fresh conceptual soil in which to plant the seeds of understanding the technical details of functional programming, of functional reasoning.

Welcome to C9 Lectures. Enjoy and learn, learn, learn.

ALWAYS ask questions right here. Erik will answer them. Remember, he is professor Erik Meijer in this context and professors answer the questions of their students. Thank you, Erik, for doing this!

Welcome to C9 Lectures!

See the rest of this great series:

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 this episode

More episodes in this series

Related episodes

The Discussion

  • User profile image

    Sweet -- will watch when I get back from work.  But it's "lambda"  Tongue Out

  • User profile image

    Fixed. Thanks. Crowdsourcing editorial. Smiley


  • User profile image

    Pure joy! Smiley ... Another two books in the basket. Thanks for the discount.

  • User profile image

    Awesome! Awesome! Awesome! Big Smile


    What an awesome idea! ... I'm surprised Eric has time to do this ... but glad he did!!! What a service for the .Net dev community!  I have friends (and me too!) who've bought books about functional programming and have not been able to get through them. This however, is just what is needed!!! FP is obviously a big deal and growing in importance .... mullticore, languages like Scala, FSharp and even CSharp.


    There's a ton of other guest lecturers I would like to hear .... Andrew Kennedy, Simon Peyton Jones, Don Syme ... I'd love to hear Joe Duffy talk about using FP to enable Paralell Extensions for .Net!! The mind boggles ...


    Thanks MS, thanks Charles and thanks Eric!!


    PS: One request ... I havent listened to the recording yet ... however, it would be great if some of the examples were done in FSharp (rather than Haskell) only because quite a few of us are likely to actually use FSharp for work at some point and I doubt many folks are gonna use Haskell for any real work anytime soon ... just my 02 cents.

  • User profile image

    It's probably better to use a pure language to explain pure mathematical functions.

  • User profile image

    The important point here is that the fundamentals are language-agnostic. Haskell is a great language to use for this learning exercise. It's pure, yes, but it's also relatively simple and functional concepts are first class citizens, in your face, in the syntax...


    Language syntax is just an abstraction of fundamental concepts. Haskell is the right choice here and your increase in functional knowledge will be directly applicalble to programming in F# (or any other functional language).


  • User profile image

    Need to come up with some questions but first I stumbled upon this presentation of Clojure on YouTube (not because of some special interest in Clojure as much as some concepts presented by its inventor recently.) The presenter tries to explain functional programming. On the first point he writes "functions are first-order"; it sort of jumped out because actually what I'd expect was: "functions are values", therefore higher-order functions are a consequence of this; higher-orderness is possible because functions are values.


    Speaking of object-orientation, I remember several years ago Java and similar languages being presented as higher-order typed languages (HOT), meaning functions (methods) in these languages were also higher-order because one can pass in objects and these objects can contain other functions (methods) and so in practice one almost ends up with the same "effect". Of course then we have all the dirty side-effects of mutating objects passed into other objects, unless the objects themselves come from classes that are defined as immutable; in a way immutable objects are still-born: after construction they are immutable and become lifeless - and when stopped being used anymore the holy garbage collecter carries the object identity into oblivion.


    One question: would you say this sums up (one of) the selling point of purity and laziness: laziness without purity is dangerous (unpredictable side-effects) whilst purity without laziness is slow (repeated evaluation). It's like "bounded computations" you may not know what's in the box (it's black or your vision is) but you can be sure that whatever is in the box does not escape it (not through the front door (the argument list); nor through the backdoor (the return value)). In effect a prison for sinful computation. Another selling point being compositionality.


    And on expressions vs statements. One thing I seriously miss in C# is having expressions everywhere; for example if is an expression and a {} block is an expression, evaluating to the last expression in the block. To get around this one can use the e?a:b expression pattern. Same for switches. Erik showed "iteration" in Haskell using list comprehension (I believe). In C#, I'd use Enumerable.Range(i,n). It's a more disciplined approach but if discipline is all you have, it'll come natural.


    Appropos "weird" encodings of pure functions.


    (PS - The triangular operator mentioned is the forward pipe operator |>; love that, as well as the >> right composition operator.)

  • User profile image

    I really like this idea! Smiley

  • User profile image

    Right on. Smiley


  • User profile image

    A series of functional programming lectures written and presented by Erik? It's SICP for todays generation. Utterly awesome! Smiley

  • User profile image

    Nice. I love this sort of e-learning type stuff. Great idea.

  • User profile image

    Well, it's presented by Erik, in lecture format, but it is based on the great Graham Hutton's Programming in Haskell book. In the description of this post you will see that you can buy this book for 20% off using the coupon code supplied (thanks Erik and Cambridge U Press!!!).


    Of course, since this is Erik Meijer, he will modify things as he sees fit (and he is certainly qualified to do so - Graham is a peer of Erik's, after all).


  • User profile image

    Downloading the vid now will watch as soon as it's done.


    Thanks Professor! As I told Charles previously, it was watching some of your initial vids on functional programming as well as Brian Beckman's series that got me into learning Haskell. I do enjoy it and wished that F# had some more of the features that Haskell does. I will make a post about it as I would like your POV on the matter. Thanks again, looking forward to the rest of the series.



  • User profile image

    No sound on Win XP Sp3 with Silverlight 2 and IE 8.



    Some other videos do have sound.

  • User profile image

    Interesting. We're getting warmer Smiley So, it could be the combination of platform and some changes that may have been made to our publishing process. Still looking into this, but this is very helpful information. Thanks.


  • User profile image
    Andrew Davey

    Re: Expressions everywhere

    You should check out Nemerle if feels very much like C#, but with everything (within a method) being an expression.

  • User profile image

    This is why I love Channel 9. I'm so stoked about this series. GREAT IDEA Charles! Channel 9 is ROCKING.

  • User profile image

    This is awesome!  Can't wait for the next episode.   The last week as seen some of the best content I've seen on C9 for ages!

  • User profile image
    Justin Bailey

    I love it! Glad to see this happening. I can't wait for the hard stuff.


    One comment - though you are focusing on Haskell, please keep it tied to C# (e.g., "here's how to do it in C#") and keep it practical. By comign back to C#, unfamiliar concepts look familiar. By keeping it practical, we'll see how this stuff can really be used. Haskell - not just for Fibonacci anymore! OK that's a bit facetious.


    As for the homework, here is my solution. I basically transcribed the Haskell version shown. I am sure it can be prettier:


    public static IEnumerable<A> QuickSort<A>(IEnumerable<A> vals)
                where A : IComparable<A>
                if (vals.Skip(1).IsEmpty())
                    return vals;
                    A pivot = vals.First();
                    var rest = vals.Skip(1);
                    var left = from x in rest
                               where x.CompareTo(pivot) <= 0
                               select x;

                    var right = from x in rest
                                where x.CompareTo(pivot) > 0
                                select x;

                    return QuickSort(left).Concat(vals.Take(1)).Concat(right);


    Note : IsEmpty is an extension method which tests if a sequence is empty. I can't believ that is not already defiend in the framework so I am sure i missed it.


    I particularly like the end part, where I concatenate the single pivot value into the sequence:


      return QuickSort(left).Concat(vals.Take(1)).Concat(right);


    Since the list is not empty, I know I can take the first value and stick in the right place. My base case also takes advantage here:


               if (vals.Skip(1).IsEmpty())
                    return vals;



    If the sequence given only has one element, I just return it unchanged and it automatically goes in the right spot. Thank you recursion!


    Full source code & VS2008 project available on github.



  • User profile image

    I couldn't agree more! I haven't been this excited about video content here on Channel 9 since 3-4 years ago, before I joined MSFT and back when I first started watching Channel 9 in the first place.

  • User profile image

    RightOn x


  • User profile image

    Finally, finally had a chance to look at this. Absolutely fantastic! I cannot wait for more. Thanks Erik and C9 for hooking us up with this cool series. It's only ep1 and I am at the edge of my seat.

  • User profile image

    You're welcome! 12 more to go Smiley

  • User profile image

    I know the homework was on VB or C#, but this is a lecture on functional programming. So here  is the homework on F# (I tried to make it as close to the Haskell solution as possible):


    //Not recomended if the list is big. Lists on F# are not lazy. ys and zs would be computed on the spot.

    //Also, the last statement would blow the stack if the list is too big.

    let rec QS = function
        | [] -> []
        | x::xs ->
            let ys = xs |> List.filter((>=) x)
            let zs = xs |> List.filter((<) x)
            QS ys @ [x] @ QS zs


    //Using F# sequences. The equivalent of Haskell lists
    let rec QSLazy = function
        | Empty -> Seq.empty
        | Seq (x,xs) ->
            let ys = xs |> Seq.filter((>=) x)
            let zs = xs |> Seq.filter((<) x)
            Seq.append (QSLazy ys) (Seq.append (seq {yield x}) (QSLazy zs))


    //Active Pattern to make pattern matching over F# sequences. Needed to make it look more like the haskell solution
    and (|Empty|Seq|) xs =
        if xs |> Seq.isEmpty then
            let x = xs |> Seq.hd
            let xs = xs |> Seq.skip 1 |> Seq.cache
            Seq (x,xs)



    Nice lecture. I'm looking forward to the next one. Smiley

  • User profile image

    It is always a joyful brain exercise to watch Erik's presentations.

    Thank's a lot for your generosity in being so generous with sharing your knowledge£!

  • User profile image

    It is, it's called Any and it's the reverse of your IsEmpty, but it should do. I missed the homework, will check after work.

  • User profile image

    Hi all,


    around 18:30 min, Erik starts to talk about Dave Turner's language SASL.  For those interested in the mechanics of compiling SASL into the SKI combinators mentioned by Erik, I have written a tutorial on how to write a functioning SASL compiler (complete from front-end to back-end).  Most of it is based on Dave Turner's original notes on SASL.  


    Available here: The Construction of an SASL Compiler. The SKI-specific material starts with Section 3.3 (page 19).


    (This has always been among the courses my students enjoyed the most — by far.)


    Enjoy, and thanks for these lectures, Erik!


  • User profile image

    awsome awsome stuff.. thank you so much for this Smiley

    this stuff really applies to everyone, regardless of language preference.

  • User profile image

    Thanks Dr Erik Meijer and Channel 9. Big Smile

  • User profile image
    Maddus Mattus



    Distributed the link to my collegues as a must see,..


    Nice shirt again Erik Smiley

  • User profile image

    I'm pretty happy with this, though there really should be better "control" Linq operators.

    		static IEnumerable<T> QuickSort<T>(IEnumerable<T> enumerable) where T : IComparable<T> {
    			var ps = enumerable.Take(1);
    			var pt = from pivot in ps from x in enumerable.Skip(1)
    					 group x by 0 < x.CompareTo(pivot);
    			var lt = pt.Where(g => !g.Key).SelectMany(g => QuickSort(g));
    			var gt = pt.Where(g => g.Key).SelectMany(g => QuickSort(g));
    			return lt.Concat(ps).Concat(gt);


  • User profile image

    "On the first point he writes "functions are first-order"; it sort of jumped out because actually what I'd expect was: "functions are values"


    The presenter in that video is confused by "first class functions" and "higher order functions". He combines the two into "first order functions" which is the opposite of what he meant to say.

  • User profile image

    I'd love to hear Erik expand on his observation about Britain being the home of a lot of the fundamentals in functional programming and related fielsds.

  • User profile image

    Functional programing in general is full of beautifull concepts, unfortunatelly a little shy on engineering concepts that make could make it more usefull than other programming models. F# tries to fix this, and in my opinion has managed to do it to a greater extent than other functional programming languages. But still I feel there's something missing that will allow functional languages to really take off, I don't know exacly what, but "functional OO" languages seem to be better than pure functional languages.






  • User profile image

    More data on the (lack of) audio:


    2 machines, xp sp3, sl3, ie8 -- no audio

    Vista home 64, ie8, sl3 -- works fine


    And, thank you all for the great job you do educating the mere mortals!


  • User profile image

    I would also like to see examples in F# - I understand the arguements for Haskell; however, being a C# developer, I have easy acess to F# which makes trying the examples a little easier.


    David Roh

  • User profile image

    I think someone in this thread should just transcribe the examples for those who can better understand F# examples. Same for C#; as is the case for this first piece of homework.


    Thinking about type-inference and intellisense. An annoying aspect of the C-style adopted by C# is that when you supply type-parameters that are used in the return type, intellisense gets in the way and becomes a nuisance - really not its fault, it's just the way it things are defined.


    e.g. Instead of this,


    IEnumerable<T> foo<T>(IEnumerable<T> xs) ...


    adopt this


    foo<T>(x: IEnumerable<T>): IEnumerable<T> ...


    and in a pure signature, why would you even care that much about parameter names


    foo :: IEnumerable<T> -> IEnumerable<T>


    Then you can always argue about whether using "a sequence" is better than "sequence<a>"; leaning towards the later.


    First attempt at the exercise


    public static IEnumerable<T> Qsort1<T>(this IEnumerable<T> s) where T : IComparable<T> { var ss = from x in s.Take(1) let xs = s.Skip(1) let a = xs.Where(y => y.CompareTo(x) <= 0).Qsort1() let b = xs.Where(y => y.CompareTo(x) > 0).Qsort1()
     select a.Concat(s.Take(1)).Concat(b); return ss.Any() ? ss.First() : Enumerable.Empty<T>(); } 


    The lack of pattern matching is quite annoying here. And also "Any" leans you towards the defined case first, whereas the null case should really come first as it's the simplest. And last, it's annoying that you have to specify a partition using two criteria; really you'd want to have one selector create a partition. So that's next.

  • User profile image

    Thank you. It seems we have an issue with SL3 on XPSP3 with some of our videos. The Silverlight team is working with us to find the cause and cure. Stay tuned. Sorry about the inconvenience. The work around is to watch the problem videos in Windows Movie Player.


  • User profile image

    You're right:  XP SP3/SL 3/IE8 or FF


    WMV works fine.


    The weird thing is, all the other SL videos are fine.  It is just this video that has no audio.



  • User profile image

    Great stuff. Looking forward to the rest of these.

  • User profile image

    I think we made a change to our encoding process. The dev team will look into this.


  • User profile image

    We will ship a chapter per week. That should provide plenty of time for exercises and questions and answers.


  • User profile image

    Thanks for sharing!


  • User profile image
    Justin Bailey

    Very nice solution! How does it deal with empty sequences? I assume Take and Skip don't throw exceptions on empty sequences?


    I think my only suggestion would be to check if s is empty first, then you can rewrite:


    public static IEnumerable<T> Qsort1<T>(this IEnumerable<T> s) where T : IComparable<T>

        return ! s.Any() ? Enumerable.Empty<T>() :
            from x in s.Take(1)
            let xs = s.Skip(1)
            let a = xs.Where(y => y.CompareTo(x) <= 0).Qsort1()
            let b = xs.Where(y => y.CompareTo(x) > 0).Qsort1()
            select a.Concat(s.Take(1)).Concat(b);


    But I don't know if that is allowed syntax.

  • User profile image

    I couldn't believe my eyes tomorrow morning when I saw this new stuff!

    Very very great! Looking forward to see the next chapters!

    Thanks to Channel9 and to my professor Smiley!


  • User profile image

    Hey, thanks for the great debugging info... can you try out this video and see if it works for you on the XP SP3 machine?




  • User profile image

    Hey Charles,


    Another 'no audio in Silverlight' from me.  As requested, here is the information:


    Silverlight version: 3.0.40818.0

    Browser version: Both Google Chrome v3.0.195.24 and IE v7.0.5730.11

    OS: Windows XP SP2 (32-bit, Version 5.1 (Build 2600.xpsp_sp2_qfe.090206-1239 : Service Pack 2))

  • User profile image

    I was about to say I like your solution and you're right my solution is safe. Your ammendment wohn't work but this ammendment to your ammendment will Wink


    public static IEnumerable<T> Qsort1<T>(this IEnumerable<T> s) where T : IComparable<T> { return !s.Any() ? Enumerable.Empty<T>() : (from x in s.Take(1) let xs = s.Skip(1) let a = xs.Where(y => y.CompareTo(x) <= 0).Qsort1() let b =
     xs.Where(y => y.CompareTo(x) > 0).Qsort1() select a.Concat(s.Take(1)).Concat(b)).First(); } 


    I think we should (maybe) use the Maybe monad here 

  • User profile image

    Oh, and this video series idea freakin' rocks.  More, please!  I'm hooked. Smiley

  • User profile image




    That video (audio) works fine on my machine.


    I do have SL3, I earlier said SL2, sorry.


    So again my platform Win XP SP3 SL3 IE8 or FF



  • User profile image

    Please try this: 



    That should work on your system, which means we have isoloated and corrected the issue. Unfortunately, the solution will require that we re-encode a bunch of videos. So, in the meantime, please watch in Windows Movie Maker for a little while longer.


  • User profile image

    Watching that video was like eating a great meal.  Keep them coming!

  • User profile image
    Craig Stuntz

    Very nice series! I've just ordered the book. (CUP was down, but Amazon has it for the same price without the coupon.) Looking forward to the rest. Thanks to Erik and C9 for doing this.

  • User profile image

    Not purely functional with the use of the IF statement.

     Public Function QuickSort(Of T As IComparable)(ByVal x As IEnumerable(Of T)) As IEnumerable(Of T)
      Return If(x.Count < 2, x, QuickSort( _
      x.Where(New Func(Of T, Boolean)(Function(xn2 As T) xn2.CompareTo(x.ElementAt(x.Count \ 2)) < 0))).Union( _
      x.Where(New Func(Of T, Boolean)(Function(xn2 As T) xn2.CompareTo(x.ElementAt(x.Count \ 2)) = 0))).Union( _
    QuickSort(x.Where(New Func(Of T, Boolean)(Function(xn3 As T) xn3.CompareTo(x.ElementAt(x.Count \ 2)) > 0)))))
     End Function

  • User profile image

    You really shouldnt be enumerating the list twice (if you dont have to, like you dont in this case).  I converted my IEnumerable<IGrouping<bool,T>> to a nicer Dictionary<bool,IEnumerable<T>> with a usefull helper method.



    public static IEnumerable<T> QuickSort<T>(this IEnumerable<T> input) where T : IComparable<T>
                var first = input.FirstOrDefault();
                var result = (from current in input.Skip(1) 
                        group current by first.CompareTo(current) > 0 into grouping
                        select grouping).GroupIntoBool(); 
                        return !input.Any() ? Enumerable.Empty<T>() : 
    public static Dictionary<bool,IEnumerable<T>> GroupIntoBool<T>(this IEnumerable<IGrouping<bool,T>> input)
                         return (from bools in new List<bool>() { true, false } 
                                     join grouping in input on bools equals grouping.Key into joinedgroup
                                     select new 
                                           val = bools, 
                                           rest = joinedgroup.FirstOrDefault() ?? Enumerable.Empty<T>()
                                     }).ToDictionary(a => a.val, a => a.rest); 



  • User profile image

    I think it's more interesting if you don't bother, and just use where on group.Key, in which case if there is no grouping, you get the empty enumerable for free. I also used .Take(1) instead of FirstOrDefault(), then selected over the 0 or 1 element enumerable, instead of explicitly handling the empty case, which I find far too satisfying for words Smiley

  • User profile image

    My simplest version.

    Dim CompareValues() As Integer= {-1, 0, 1}
     Public Function QuickSort(Of T As IComparable(Of T))(ByVal input As IEnumerable(Of T)) As IEnumerable(Of T)
      Dim result = (From cv As Integer In CompareValues _
                    Group Join iv As T In input _
                    On iv.CompareTo(input(0)) Equals cv _
                    Into Group _
                    Select Group)
      Return If(input.Count < 2, _
                input, _
                QuickSort(result(0)) _
                .Concat(result(1)) _
                .Concat( _
                  QuickSort(result(2)) _
                 ) _
     End Function

    Just wish i could get rid of the if statement.

  • User profile image

    This is nothing short of wonderful and I want to really thank Erik, Charles and the team. I've had the first lecture playing on loop all Friday afternoon - just letting it sink in. It's great stuff, I would have paid hard cash for something of this quality and here you guys are just giving it away. Huge respect!

  • User profile image

    Still, only 3 people bothered to rate with a "thumbs up" although obviously it's very popular.


    Next in line -


    public static IEnumerable<T> Flatten<T>(this IEnumerable<IEnumerable<T>> xs) { return xs.SelectMany(x => x); } public static IEnumerable<T> Qsort<T>(this IEnumerable<T> s) where T : IComparable<T> { return (from x in s.Take(1) let
     xs = s.Skip(1) let a = xs.Where(y => y.CompareTo(x) <= 0).Qsort() let b = xs.Where(y => y.CompareTo(x) > 0).Qsort() select a.Concat(s.Take(1)).Concat(b)).Flatten(); } 


    Looks like flatten is a "recursive" monadic bind. Still, much less elegant than the Haskell definition.


    And now doing away with the horrible IComparable noise that obfuscates the code


    public static IEnumerable<int> QiSort(this IEnumerable<int> s) { var Qi = from z in s.Take(1) let xs = s.Skip(1) let p = from x in xs where x ≤ z select x let q = from x in xs where x > z select x select p.QiSort().Concat(s.Take(1)).Concat(q.QiSort());
     return Qi.Flatten(); } 


  • User profile image

    Excellent lecture!  Historical background was fascinating - indeed history is often overlooked among programmers.  Looking forward to the next lecture.

  • User profile image

    Thank you for the kind words. We're all thrilled that C9 Lectures has evoked such positive feedback and generated such excitement.


    Our experiment = successful! Smiley




  • User profile image

    still no sound. Surprisingly though, I tried the VS Documentary again and this time there was sound, but part two had no sound still.

  • User profile image

    We've figured out the issue and we will have to re-encode many of our latest files... In the meantime, please watch this and other pieces in Windows Media Player -> Click on the Formats link under the inline player and select your format of choice (WMV or MP4...). These will have sound as the problem stems from an encoding setting we use in Expression Encoder that causes audio playback problems in SL3 running on XP SP2/3.



  • User profile image

    Here's my ugly attempt at writing a functional qsort in C#. First I'll introduce a pair data structure:

    public struct Pair<A, B>
        public A First { get; set; }
        public B Second { get; set; }

    Then a few extension methods:

    public static Pair<IEnumerable<T>,IEnumerable<T>>
        Partitions<T>(this IEnumerable<T> xs, Func<T, bool> p)
        var partitions =
            (from x in xs
             group x by p(x) into g
             select g).ToDictionary(g => g.Key);
        return new Pair<IEnumerable<T>,IEnumerable<T>>()
            First = partitions.ContainsKey(true)
                ? partitions[true].AsEnumerable() 
                : Enumerable.Empty<T>(),
            Second = partitions.ContainsKey(false) 
                ? partitions[false].AsEnumerable() 
                : Enumerable.Empty<T>()
    public static bool IsNil<T>(this IEnumerable<T> xs)
        return !xs.GetEnumerator().MoveNext();
    public static bool LessThan<T>(this T x, T y) where T : IComparable<T>
        return x.CompareTo(y) < 0;


    Finally, QSort itself:

    public static IEnumerable<T> QSort<T>(this IEnumerable<T> xs) where T : IComparable<T>
        if (xs.IsNil())
            return Enumerable.Empty<T>();
            var pivot = xs.First();
            var p = xs.Skip(1).Partitions(y => y.LessThan(pivot));
            var smaller = p.First;
            var larger = p.Second;
            return smaller.QSort()
                .Concat(new List<T>{pivot})


    Edit: I was bored and also wrote a Python version... Tongue Out

    def partition(xs, p):
        z = ([],[])
        for x in xs:
        return z
        # Note that partition is not quite functional, as it uses mutation.
        # The mutation, however, only affects local values. The function
        # partition for the outside world is referential transparent.
    def qsort(xs):
        if not xs:
            return []
            pivot = xs[0]
            smaller, larger = partition(xs[1:], lambda x: x < pivot)
            return qsort(smaller) + [pivot] + qsort(larger)


  • User profile image

    Hey Charles,


    Just wanted to let you know that your link did the trick; that video plays sound as expected.


    Thanks! Smiley

  • User profile image

    This series is a great idea!  Thanks to Erik, Charles, and the C9 team for making this happen.  I'm really looking forward to the other episodes.  And maybe we will get another lecture series after this one???


  • User profile image

    You can take any Lambda expression, and compile it to a single expression.  

    And that’s kinda beautifull 


    Thank you so much !

  • User profile image

    Yes! C9 Lectures is a new type of content (series) on 9 and after Erik's amazing FP series of lectures you will continue to see more. Smiley



  • User profile image

    It's strange that Eric just had a passing reference on Scheme. It is my favorite language and I wish he had talked about some of the contributions and influences on  programming languages.


    What's really surprising is the power of combinators. I didnt know that one of them  would suffice.  Could somebody show a small example of this powerful deduction?

  • User profile image

    For future reference these fast assembled depictions should do


    First, GHCi


    Generic Comment Image


    Next, WinGHCi


    Generic Comment Image


    Then, concept denotation


    Generic Comment Image


    And a small reference


    Generic Comment Image

  • User profile image

    /sigh -- no little controls like full-screen pause, rewind a little?

    (never mind, i found out the new way -- click on the alternative formats and get the media player or what not)

  • User profile image

    Thank you for the lecture and I have already bought the book to follow the lectures



    open System

    open System.Threading

    open Microsoft.FSharp.Control


    // create a random list

    let maxSize=4

    let rand = new Random()

    let list=[ for i in 1..maxSize do yield rand.Next(100*maxSize)]


    printfn "%A" list


    //1. Simple version

    // 'a list -> 'a list

    let rec simpleQuickSort(inL)=

        match inL with

        | []->[]

        | h::t->List.partition(fun e->e<=h) t|>fun(l,r)->simpleQuickSort(l)@ h::simpleQuickSort(r)



    let sL=simpleQuickSort(list)

    printfn "%A" sL

    Erlang :





    %% generates a list of random numbers



       lists:map(fun(_)->random:uniform(MaxNumber) end,lists:seq(1,N)).


    %% simple version





    F# :

    ////2 ASynchronous version

    // create asynchronous task for list partition

    //'a list * ('a -> bool) -> Async<'a list>

    // f is function for partition

    let asyncPartition(l,f)= async{ return l|>List.filter(f)}



    let rec asyncQuickSort(inL)=

           match inL with


             |h::t-> let asynTasks=[asyncPartition(t,fun(x)->x<=h);asyncPartition(t,fun(x)->x>h)]

           let asynResult=Async.Run(Async.Parallel asynTasks)// execute

    1.        asyncQuickSort(asynResult.[0])@h::asyncQuickSort(asynResult.[1])//join                                 


    let asynSortedList=asyncQuickSort(list)

    printfn "%A" asynSortedList


    //3. Message Passing Style Version

    type MsgListPartition = | GetList of int list*(int->bool)*AsyncReplyChannel<int list>

                            | Stop


    type PartitionServer(srvName:string)=

         let receiver =  MailboxProcessor<MsgListPartition>.Start(fun inbox->

                  let rec loop() =

                        async {

                                let! msg=inbox.Receive()

                                match msg with


                                |GetList(l,f,rep)-> let p =l|>List.filter(f)


                                                    return! loop()





         member o.Stop() = receiver.Post(Stop)

         member o.GetList(l,f)=receiver.AsyncPostAndReply(fun aS->GetList(l,f,aS))



    let s1Server = new PartitionServer("Server-l")

    let s2Server = new PartitionServer("Server-r")

    let rec mpsQuickSort(inL)=

            match inL with


             |h::t-> let asynL=[s1Server.GetList(t,fun(x)->x<=h);s2Server.GetList(t,fun(x)->x>h)]

            let asynResult=Async.Run(Async.Parallel asynL)



    let z=mpsQuickSort(list)

    printfn "%A" z



    %% parallelversion



        {From,Pivot,List} -> From ! {self(),[X||X<-List,X<Pivot]}





        {From,Pivot,List} -> From ! {self(),[X||X<-List,X>=Pivot]}



    gather(SPId) ->


                            {SPId, Ret} -> Ret





    psort([H|Tail])-> [LPId,RPId]=[spawn(fun left_sort/0),spawn(fun right_sort/0)],

                      LPId! RPId! {self(),H,Tail},





  • User profile image

    Excellent, really enjoyed this!

  • User profile image

    For the Haskell:

       f (x:xs) = f ys ++ [x] ++ f zs


    If you're working with IEnumerable<IComparable> as your lists, what's the preferred C# w LINQ mapping for the right-hand side of this?

  • User profile image

    The standard LINQ sequence operators contain a definition for (++) namely Concat. There is no operation for creating singletons, but you can use new[]{ x } for that. So you would write f(ys).Concat(new[]{x}).Concat(f(zs). Which does not look too bad.


    If you want to be fancy, you could imitate LINQ to XML's Add method on XElement and can create a version of Concat that takes a params[] of object (https://msdn.microsoft.com/en-us/library/system.xml.linq.xelement.add.aspx) and write Enumerable.Concat(f(ys),x,f(zs)). But you run the risk that the static typing police starts chasing you Wink

  • User profile image

    It's amazing what you are doing for the .NET community (and programmers looking to learn in general).  Thank you!

  • User profile image

    Great lecture. "You know"

  • User profile image

    I tried to download wmv file but it stopped in 1/3 of the download. Could it be corrected?

  • User profile image

    Very good lecture.  Is the PPT available for download?

  • User profile image

    I am starting these lectures a little late. I beleive 5 just came out. I'm having trouble following the function equations. Is there someplace with a good consice explaniation of this? I am a programmer and my background is Cobol, but I've allways have trouble understand the point with somthing like f(x) = x.



  • User profile image
    Wiep Corbier

    If you drop the zillion "you know" this video would be 10 minutes shorter.

    Futhermore, if "i know", why are you telling me this?


    Just a suggestion Smiley

  • User profile image

    Hi am new to this, I find fn programming hard, did it at uni but was not good at it, but now I'm going to TRY to understand it. thanks.

  • User profile image

    Erik Meijer, and everyone involved with this project, thank you so much!  I'm studying haskell and f# on my own alongside my university courses and I cannot express how much I appreciate you guys putting hard work in explaining fairly what functional programming is about.  I don't want to be greedy and keep all the fun to myself  =).


    Much regards.  Good day!

  • User profile image

    Thanks so much Dr. Erik and Charles. 

    It's a great chance to become a student of Professor Erik.

    I always wanna learn a pure functional programming language. 

    What a great chance fore me!


    Thanks much.

  • User profile image

    Dear ,


    The following is my ugly and stupid attempt to the homework. 


    class Program
            delegate IEnumerable<T> QSortFunc<T> (IEnumerable<T> source) where T: IComparable<T>;
            static void Main(string[] args)
                QSortFunc<int> qsort = null;
                qsort = nums => nums.Count() < 1
                                ? Enumerable.Empty<int>()
                                : qsort(nums.Where(num => num.CompareTo(nums.FirstOrDefault()) <= 0).Skip(1))
                                    .Concat(qsort(nums.Where(num => num.CompareTo(nums.FirstOrDefault()) > 0)));
                var seq = new[] { 1, 1, 2, 9, 7, 8, 3, 9, 7, 8, 3, 0, -1 };            
                var result = qsort(seq);
  • User profile image

    In case anyone else was trying to find it, Erik briefly references:


    Jeroen Fokker, The Systematic Construction of a One-combinator Basis for Lambda-Terms.
    Formal Aspects of Computing 4 (1992), pp. 776-780.




  • User profile image
    Todd Hunter

    Because its what i know best, here is it in perl... 


    #!/usr/bin/perl sub qsort { my @array = @_; return () unless @array; my $pivot = shift @array; my @larger = (); my @smaller = (); map {$_ >= $pivot ? push @larger, $_ : push @smaller, $_} @array; return (qsort(@smaller), $pivot, qsort(@larger));


    The question i have about the haskell version, when smaller and larger are constructed, does that walk the xs list twice to generate the two lists, or is it optimised to do it once?

  • User profile image

    Eric I do think you're brilliant, but you know a brilliant person you know should also you know have a decent way you know of expressing you know himself you know. You're making some great videos and a lot of people are watching them, so please pay a little more attention on how you speak.

  • User profile image

    Very late to the class. 


    My solution to the Home work ...


    //Find x(member of xs), such that the x is central value
    void sort(int *array, int size) {
       int count, lcount = 0, mcount = 0; 
       //To hold the smaller xs(than x)
       int less[size - 1];
       //To hold the larger xs(than x)
       int more[size - 1];
       for(count = 1; count < size; count++) {     
          //array[0] is the x
          if(array[0] > array[count]) {
             //The xs smaller than x        
             less[lcount] = array[count];
          else if(array[0] <= array[count]) {
             //The xs larger than x 
             more[mcount] = array[count];        
       //Put the x in the middle of the array
       array[lcount] = array[0];
          for(count = 0; count < lcount; count++)
              array[count] = less[count];     
          for(count = 0; count < mcount; count++)
             *(array + lcount + 1 + count) = more[count];                 
       if(lcount > 1)
          sort(array, lcount);
       if(mcount > 1)
          //array[lcount] is x
          sort((array + lcount + 1), mcount);   


    Sohail Qayum Malik.

  • User profile image

    anybody still got excited here and watching this like me, at the end of year 2017 :)?

  • User profile image
    Link Chen

    Thanks for teaching.
    But please try not to speak "You Know" so much.
    I come here to learn because I don't know.

  • User profile image

    revisiting this and its still awesome.

Add Your 2 Cents