Entries:
Comments:
Posts:

Loading User Information from Channel 9

Something went wrong getting user information from Channel 9

Latest Achievement:

Loading User Information from MSDN

Something went wrong getting user information from MSDN

Visual Studio Achievements

Latest Achievement:

Loading Visual Studio Achievements

Something went wrong getting the Visual Studio Achievements

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

Download

Right click “Save as…”

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

Tags:

Follow the Discussion

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

  • CharlesCharles Welcome Change

    Fixed. Thanks. Crowdsourcing editorial. Smiley

    C

  • Bent Rasmussenexoteric stuck in a loop, for a while

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

  • keith flokeithfl keithfl

    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.

  • Bent Rasmussenexoteric stuck in a loop, for a while

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

  • CharlesCharles Welcome Change

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


    C

  • Bent Rasmussenexoteric stuck in a loop, for a while

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

  • BassBass Knows the way the wind is flowing.

    I really like this idea! Smiley

  • CharlesCharles Welcome Change

    Right on. Smiley

    C

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

  • BasBas It finds lightbulbs.

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

  • CharlesCharles Welcome Change

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


    C

  • Sparkywil2300 Super #

    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.

    ~sparky

    [http://sdasrath.blogspot.com/]

  • ivan_ivan_ g

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

     

     

    Some other videos do have sound.

  • CharlesCharles Welcome Change

    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.

    C

  • Andrew DaveyAndrew Davey www.​aboutcode.​net

    Re: Expressions everywhere

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

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

  • PerfectPhasePerfectPhase "This is not war, this is pest control!" - Dalek to Cyberman

    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!

  • 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;
                else
                {
                    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;
                else

                     ...

     

    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.

     

    Justin

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

  • CharlesCharles Welcome Change

    RightOn x

    C

  • Sparkywil2300 Super #

    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.

  • CharlesCharles Welcome Change

    You're welcome! 12 more to go Smiley
    C

  • 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
            Empty
        else
            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

  • 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£!

  • Bent Rasmussenexoteric stuck in a loop, for a while

    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.

  • 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!

      —Torsten

  • Allan LindqvistaL_ Kinect ftw

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

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

  • gamefmgamefm no box and no sphere, only humanity as gravity.

    Thanks Dr Erik Meijer and Channel 9. Big Smile

  • Maddus MattusMaddus Mattus Maddus on C9, Is often ​controversi​al, But fun ​none-the-​less -​evildictait​or

    Awesome!

     

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

     

    Nice shirt again Erik Smiley

  • 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);
    		}
    

     

  • "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.

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

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

     

     

     

     

     

  • waswas

    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!

     

  • 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

  • Bent Rasmussenexoteric stuck in a loop, for a while

    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.

  • CharlesCharles Welcome Change

    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.

    C

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

     

    B

  • Great stuff. Looking forward to the rest of these.

  • CharlesCharles Welcome Change

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

    C

  • CharlesCharles Welcome Change

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

    C

  • CharlesCharles Welcome Change

    Thanks for sharing!

    C

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

  • 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!

     

  • Duncan MackenzieDuncanma "yeah that's awful close, but that's not why I'm so hard done by"

    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?

     

    http://channel9.msdn.com/posts/Duncanma/Testing-the-Audio-issue-with-XP/

     

  • 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))

  • Bent Rasmussenexoteric stuck in a loop, for a while

    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 

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

  • ivan_ivan_ g

    Duncan,

     

    http://channel9.msdn.com/posts/Duncanma/Testing-the-Audio-issue-with-XP/

    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

     

    Thanks.

  • CharlesCharles Welcome Change

    Please try this: 

    http://channel9.msdn.com/posts/Duncanma/Testing-the-Audio-issue-with-XP/

     

    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.

    C

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

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

  • Adam SpeightAdam​Speight2008 The Bandito Coder

    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
    

  • 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>() : 
                                result[false].QuickSort().Concat(input.Take(1)).Concat(result[true].QuickSort());
    
    } 
     
    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); 
    }
     

     

     

  • 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

  • Adam SpeightAdam​Speight2008 The Bandito Coder

    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.

  • 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!

  • Bent Rasmussenexoteric stuck in a loop, for a while

    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(); } 

     

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

  • CharlesCharles Welcome Change

    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

     

    Cheers,

    C

  • ACGACG

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

  • CharlesCharles Welcome Change

    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.

     

    C

  • 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>();
        else
        {
            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})
                .Concat(larger.QSort());
        }
    }
    

     

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

    def partition(xs, p):
        z = ([],[])
        for x in xs:
            z[1-bool(p(x))].append(x)
        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 []
        else:
            pivot = xs[0]
            smaller, larger = partition(xs[1:], lambda x: x < pivot)
            return qsort(smaller) + [pivot] + qsort(larger)
    

     

  • Hey Charles,

     

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

     

    Thanks! Smiley

  • 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???

     

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

    And that’s kinda beautifull 

     

    Thank you so much !

  • CharlesCharles Welcome Change

    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

     

    C

  • 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?

  • Bent Rasmussenexoteric stuck in a loop, for a while

    For future reference these fast assembled depictions should do

     

    First, GHCi

     

     

    Next, WinGHCi

     

     

    Then, concept denotation

     

     

    And a small reference

     

  • /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)

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

    F#:

    #light

    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 :

    -module(parallelquicksort).

    -export([gen_randomlist/2,simplesort/1]).

     

     

    %% generates a list of random numbers

     

    gen_randomlist(N,MaxNumber)->

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

      

    %% simple version

    simplesort([])->[];

    simplesort([H|Tail])->simplesort([X||X<-Tail,X<H])

                          ++Cool++

                          simplesort([X||X<-Tail,X>=H]).

    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

    F#:

    //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

                                |Stop->return()

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

                                                    rep.Reply(p)

                                                    return! loop()

     

                              }

                  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)

            mpsQuickSort(asynResult.[0])@h::mpsQuickSort(asynResult.[1])

     

    let z=mpsQuickSort(list)

    printfn "%A" z

     

    Erlang:

    %% parallelversion

    left_sort()->

      receive

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

      end.

     

    right_sort()->

      receive

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

      end.

     

    gather(SPId) ->

        receive

                            {SPId, Ret} -> Ret

        end.

     

    psort([])->[];

    psort(Cool)->Cool;

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

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

                      psort(gather(LPId))++Cool++psort(gather(RPId)).

                     

                     

     

  • Excellent, really enjoyed this!

  • 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?

  • 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 (http://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

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

  • Great lecture. "You know"

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

  • Very good lecture.  Is the PPT available for download?

  • Jeff Wyantpdcjlw1 Confused

    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.

     

    Thanks.

  • 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

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

  • 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!

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

  • 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(nums.Take(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);
                result.ToList().ForEach(Console.WriteLine);            
            }        
        }    
  • 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.

     

    http://people.cs.uu.nl/jeroen/article/combinat/index.html

     

  • 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?

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

  • Sohail Qayum MalikAeon Sohail Qayum Malik

    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];
             lcount++;
          }  
          else if(array[0] <= array[count]) {
             //The xs larger than x 
             more[mcount] = array[count];        
             mcount++;
          }          
       }
         
       //Put the x in the middle of the array
       array[lcount] = array[0];
      
       if(lcount)
          for(count = 0; count < lcount; count++)
              array[count] = less[count];     
                                
       if(mcount)              
          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.

Remove this comment

Remove this thread

close

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.