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

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

The Discussion

  • User profile image

    Thank you - excellent series so far. Also Learn You A Haskell A Great Good (http://learnyouahaskell.com/) is an excellent reference source for some of this material. Thanks again Dr. Meijer.

  • User profile image
    Justin Bailey

    Some might like my Haskell Cheatsheet at http://cheatsheet.codeslower.com. It's a short reference & mini-tutorial.


    OK - done pimping now Smiley



  • User profile image

    Well it's the good kind of pimping and that is a nice cheat sheet. I will definitely reference it when my memory fails to remember some construct that I know would be simple in the first place Smiley

  • User profile image

    Exelent! I was looking forward to the next lecture. Smiley

  • User profile image

    I like the syntactic symmetry of inverse associativity for function declarations and function applications. 

    f :: (Int -> (Int -> Int))         f :: Int -> Int -> Int
         ((f 1) 2)                             f 1 2

    So the paranthesis' become denser at the left or the right.


    The zip function is quite beautiful and metaphoric. Erik's definition

    zip :: ([a], [a]) -> [(a, a)]

    is super-symmetrical*. But then there is something nagging me (just a little bit) - here currying is suddenly not as pretty anymore because it breaks the symmetry, which is the motivation for Erik's own definition. 3 notions of structure: curried function (function to function to sequence), list (homogeneous unbounded sequence) and tuple (heterogeneous bounded sequence).


    I assume curried functions can be treated as sequences as well - flipping and reversing arguments. And lazily (always here) so no time is wasted while jusing doing what I think Erik refers to as symbol pushing. Must see...


    The book has not arrived yet, still waiting. That's not unusual, but hopefully it will arrive before the end of the lecture series.


    * Sometimes (especially functional) programming language design looks like the search for a unified theory of everything - for computation, types and syntax. Slowly crawling closer and closer to nirvana. Haskell looks like the closest thing so far, although maybe still susceptible to decades of further axiomatization.

  • User profile image

    This episode is so full of Funk it could do with a 70's porno music track.

  • User profile image

    Last time Eric mentioned his hope about interactive app with C# codes. There is one actually available: LINQPad.net

  • User profile image

    Justin, Thanks for the cheatsheet..

  • User profile image

    One question about this:






    I typed those in hugs and they are not recognized syntax. Are those just description about a function?


    By the way, is there any way to get descriptions like above ones out for a predefined function such as zip?


  • User profile image

    The complete HUGS is 14MB while GHC is 50MB. The size may make the difference or better features?

  • User profile image

    You can type things like

    3 :: Int

    in Hugs or GHCi and it will work. Hugs and GHCi are interpreters that expect expressions, which they'll gladly evaluate and print.


    However, when you type something like

    f :: Int -> Int -> Int

    in Hugs or GHCi, you're asking it to evaluate the expression f and telling the interpreter it has type Int -> Int -> Int. There are several problems with this. First of all, the interpreter does not know what this "f" thing is you're talking about, unless you have defined f in a Haskell script and have loaded that script file. Secondly, if you did define f somewhere, functions themselves cannot be printed to the console.**


    ** Often the cryptic error thrown by the interpreters is something along the lines of "There is no Show instance for Int->Int->Int".

  • User profile image

    You can use ":t" to find the type of something:


    Prelude> :t zip

    zip :: [a] -> [b] -> [(a, b)]


  • User profile image

    For those who are interested, the C# zip function Erik talked about (shown below)...

    IEnumerable zip<T,S,R>(IEnumerable<T> xs, IEnumerable<T> ys, Func<T,S,R> f) { //... }

    ...also exists in Haskell as zipWith

    zipWith :: (a -> b -> c) -> ([a] -> [b] -> [c])

    ...and can be implemented using only two lines of Haskell. Tongue Out

  • User profile image

    Type-inference: An IDE idea


    Suppose we had a Visual Haskell IDE. Then for any function definition, type-inference will kick in and dynamically derrive the type from the function definition. That's nothing new.


    Now imagine these two scenarios -


    Scenario 1: While we are typing a definition, the IDE will assist by displaying a ghostly function type definition for our function above the function definition itself, as we go


    Scenario 2We start out by typing in the function type definiton, then we lock-in the definition (context/lock definition). Second we go on to define the function itself. Here we are dynamically informed about mis/matching as we type while being able to see both the lock-in type of the function as well as the inferred type of the function.

    First of all if we don't want to, we don't have to type the function type definition. When we are satisfied with a definition we can lock it in.


    Then there's point vs point-free style. There the IDE will always normalize a function into a point-free style (good idea?) and then on the right show it in point style; or one can switch between point and point-free styles globally for a file (well, at least while we still keep the notion of a file).


    Sounds like there are many interesting things a Haskell IDE could help with.

  • User profile image

    I don't think it's a good idea if a function would automatically be transformed to a point-free notation by the IDE. Sometimes the point-free version is much harder to read**. Nevertheless, it would be a great optional tool in an IDE.


    ** Example:

    -- pointful: mult x y z = z*y*x -- pointfree generated by lambdabot's @pl tool: mult = flip (flip . ((*) .) . (*))

    Btw, the pointfree version of this example can be made simpler if you'll use the commutativity of (*). The only problem is that the commutativity property is not garantueed, so a (syntactic) pointfree tool cannot rely on it.

  • User profile image

    Nice. Thanks for your replies, @ShinNoNoir and @sylvan. By the way, here is an alternative I got:


    Hugs> :find zip


    This will open the source file by Vim (in my computer) and point to the definition of zip.

  • User profile image

    I can't believe you're doing 13 of these. Fantastic.

  • User profile image

    This is the precise definition (abbreviated)

    IE<C> Zip<A,B,C>(this IE<A> a, IE<B> b, Func<A B,C> f);

    Now Erik mentions we don't have a tuple type, but in BCL 4 we now do, so it would not surprise if we see this later on

    IE<Tuple<A, B>> Zip<A, B>(this Tuple<IE<A>, IE<B>> ab)
         return ab.Item1.Zip(ab.Item2, Tuple.Create);

    Although I'm not sure it's so useful in C# when we have the "fusion zipper". Appropos, Erik, didn't you define IE<A> as A* in Cω? So then we could write this more succintly as

    Tuple<A, B>* Zip<A, B>(this Tuple<A*, B*> ab)
         return ab.Item1.Zip(ab.Item2, Tuple.Create);

    And if C# had syntactic support for tuples, maybe we could even write something like

    (A, B)* Zip<A, B>(this (A*, B*) ab)
         return ab.Item1.Zip(ab.Item2, Tuple.Create);

    Or, now going completely mad

    (A, B)* Zip<A, B>(this (A* a, B* b))
         return a.Zip(b, Tuple.Create);

    with pattern matching syntax in method signatures (tuple deconstruction).


    Now why do we have to suffer with a block declaration if we just want a one-liner definition?

    (A, B)* Zip<A, B>(this (A* a, B* b)) = a.Zip(b, Tuple.Create);

    At this level the "reversed" signature (return type before argument type) also starts to grind a little (or even the fact that the types need be there at all).

    Zip<A, B>(this (a: A*, b: B*)): (A, B)* = a.Zip(b, Tuple.Create);

    Now we might as well just use Haskell...


    Then of course the question becomes - now that we've also given IE special treatment, then what is the syntactic form of the semantic dual of A*?

  • User profile image
    Joerg W Mittag

    Am I right that the Zip LINQ sequence operator in .NET 4.0 whose signature Erik wrote down actually corresponds to Haskell's zipWith function, not zip?

    Without looking it up, using kind of my mental type inferencer, the type of zipWith would have to be

    zipWith :: (a → b → c) → [a] → [b] → [c] 
    , which is exactly the signature of .NET 4.0's Zip.

  • User profile image

    Actually, the new BCL zip (looking up) is

    zip :: ([a], [b], (a, b) -> c) -> [c]

    And the type of the Haskell zip (looking up) is

    zip :: [a] -> [b] -> [(a,b)]

    So the BCL definition is closer to Erik's super-symmetric version, except that it uses a constructor function rather than just returning tuples. Well... actually it's just as far away...

  • User profile image

    That's cool!


    Actually it could use Brian's definition of simpler: shorter!


    If the point-free style is shorter, then choose that, if not, then don't. Keep both side-by side for reference (left side the shortest; right side the longest - whichever form is whichever)


    And yes, the point-transformer should use maximal type knowledge.

  • User profile image

    I can appreciate these lectures, but I think it would be nice if there was a series of lectures which dealt with beginners. I guess Erik is trying to convert the C# crowd by repeatedly bringing up references to it, but I think it would have been better had he presented the problems and then just showed how it is done in Haskell.


    One drawback of having an Uber-Expert teach something like this is that things that seem trivial to them will only make sense (and therefore appeal) to "the initiated" .. that leaves beginners like me out. 


    I'm just checking Haskell out and was hoping I'd be able to learn something from these lectures but he is constantly delving into advanced material and constantly keeps comparing with C# ... I don't really know what the purpose of this series of lectures is. To compare and contract C# vs Haskell or to elaborate on Functional Programming Fundamentals using Haskell? 


    I find Erik's teaching style a little hap-hazard and rather opaque from an outside learner's perspective. If the idea is to appeal to the Haskell initiates, then I guess the lectures are going well. Not all of us are super mathematicians waiting for the "triple curried function" manna to descend from the Redmond heaven... ROLLEYES


    How about a little less pretentious, and a little more concrete? How about writing a little game? Like Tetris or something?


    We'll figure out the Currying and the C# comparisons on our own thankyouvery much. [\RANT]

  • User profile image

    Thanks for the feedback.


    The idea here is not to preach to the Haskell choir (obviously)... It's to teach imperative-minded programmers to think functionally, to understand how to program in a functional way, to understand that the future of programming will involve an increasingly functional style embedded inside imperative languages like C#.


    Yes, you do need to understand currying. You do need to understand polymorphic functions, higher order functions, lazy evaluation, etc. It's awesome, in my mind, that Erik is including references to languages that most of you already program in as a way to hammer home the fundamentals. Doesn't that make sense in context?


    This is not a Haskell 101 class. Haskell is the concrete language reference point used here ( it's a pure functional language so it forces the fundamentals to the top of your mind, then out of your fingers onto the keyboard -> you can do the exercises in it...).



  • User profile image

    I can only show you the door, you have to walk through it.

  • User profile image

    First off, I have the utmost respect for Dr. Meijer and I think he is a great "fundamentalist" evangelist for functional programming. For a long time,  Haskell seemed too ivory tower to me and I didn't bother checking it out.


    You know what made me take a serious look? A mario brothers clone ("nario") written in Haskell by a Japanese hacker.

    video:  & code here. So I've been looking at the LYaHfGG and the Haskell Books ... and I guess I was hoping these lectures would be more accessible but I guess not. Most talks on Haskell involve the high falootin' higher order this and monad vs monoid that .... I mean yeah, sure, that all is possible, but where are we supposed to go learn basic stuff? Especially when claims are made that FP is destined to replace Procedural programming etc (which it probably is). 


    Is anyone willing to come down from the mountain and teach us mere mortals? or is Haskell for big shot brainiacs?  For the "real problems" out there? because if so, isn't there the possiblity that it will end up in Lisp-Lisp-Land ? 


    Anyways, don't mind me. I'll shut up now.

  • User profile image

    > You know what made me take a serious look? A mario brothers clone ("nario") written in Haskell by a Japanese hacker.


    That is indeed very impressive.


    But to get the spirit of functional programming you have to learn to "understand" concepts such as currying, monads, ... It is really not that hard. Wax on, wax off. Wax on, wax, off. Wax on, wax off.

  • User profile image

    I think you're missing a great opportunity here. Please ask questions about all the thing that Erik is presenting and you don't understand. I bet you would get a lot of help in the forum. That would help a lot of people that might be having the same issues as you. Also it would give Erik an inside of what concepts are difficult to grasp and help him to better present future chapters.


    Another think hat you can do is read the chapter of the book that Erick is going to present in advance. That way you know what's going to be covered. If you don't have the book, the slides are here: http://www.cs.nott.ac.uk/~gmh/book.html#slides.


    I hope this helps. Smiley


  • User profile image

    I think I get what reddit is saying, but I have the advantage of working with haskell many moons ago and therefore the concepts are not new to me. The reason I can sympathise is that even though I can read Erik's homework questions and immediatly know the answers, when I watch through the explaination, I immediately think of what scenario it could apply to. So with the zip function, I couldn't think of a use of converting two lists to a list of tupples, as data is never that precise to make a perfect match. (maybe to many outer joins in SQL dealing with fuzzy logic) So with all that said, I think it could possibly help a subset of us, if Erik could also include some quick examples of application of a function or two to assist in the learning process. I think that is what reddit was alluding to with the small game comment.


    Maybe it's just me, but I've programmed in so many languages now, that comparing one to another to help learn the new one become information overload and I tune out. By seeing something in it's own right, rather than a reflection of something else, I find it easier to invent new things using it. eg. I wrote recursion in C for my first assignment. Not because I understood what recurrsion was, but that it looked like the simpliest and least amount of code way of solving the problem; and especially as it didn't core dump like my previous attempts.

  • User profile image

    Nice, but with .NET 4.0 this is actually even cleaner:


    var xs = new List<int> { 1, 2, 3 };
    var ys = new List<string> { "X", "Y", "Z" }; 
    var zs = xs.Zip<int, string, Tuple<int, string>>(ys, 
                 (x, y) => Tuple.Create<int, string>(x, y)); 
    // shorter version: 
    zs = xs.Zip(ys, (x, y) => Tuple.Create(x, y));
    // zip a list of Tuples and another list: 
    var ts = new List<DateTime> { DateTime.Parse("2009-01-02"), DateTime.Parse("2009-01-03") };
    // long way 
    var us = zs.Zip<Tuple<int, string>, DateTime, Tuple<int, string, DateTime>>(ts, 
                  (z, t) => Tuple.Create<int, string, DateTime>(z.Item1, z.Item2, t)); 
    // Love type inference: 
    var vs = zs.Zip(ts, (z, t) => Tuple.Create(z.Item1, z.Item2, t));


  • User profile image

    Not sure it's cleaner but it shows how to use it without having an overloaded Zip for tuples. And even shorter

    var zs = xs.Zip(ys, Tuple.Create);

    I'll buy that for a dollar. Quite short, but I still want the overload.

  • User profile image

    Got my copy of Graham Hutton's Programming in Haskell yesterday and can't wait to put my nose into it.

    Thanks a lot Dr. Meijer for this fantastic series!


    btw: I love the lecture / chapter based format of this webcast series. Hope to see more webcasts like this in the future.

  • User profile image

    I don't think the criticism by reddit is quite fair - but the part that you mention - practical uses of certain more complex abstract functions is quite reasonable. And that doesn't imply that a game needs to be built to show it.


    Erik compares and contrasts Haskell to what we already know (C#) so that we may better understand it - As he should! And he actually does this with respect despite his love for Haskell: arguing about the  OO and the benefits of Intellisense and so on. And the same for F# which too is not fundamentalist like Haskell. But I find the laziness of Haskell liberating because I don't have to constantly worry about explicitly introducing it where needed. It remains to be seen how the purity will play out.


    As for preaching to the choir: I personally have no prior practical experience with Haskell. It always looked too scary. But I am armed with an interest in functional programming and some playing around with ML and functional style C# and Javascript. This lecture definitely has helped pass the threshold into Haskell. I could have used this a couple of years ago.


    So I say: the series is on track, possibly with one or two more practical examples thrown in here and there to kick-start the imagination.


    Basic Mathematica and Haskell should be used in primary school to help prime kids for transferring mathematics directly to practical applications and as a learning tool for testing assumptions. Actually Haskell and Logo would be cool companions.

  • User profile image

    exoteric, I appreciate your comment and perhaps I could have worded my comment in a less belligerent way.  I do have a few comments about your assertions:


    "practical uses of certain more complex abstract functions is quite reasonable. And that doesn't imply that a game needs to be built to show it."


    Yes, one would have to agree with the general spirit of the comment, but there is a time and place for teaching complex abstractions. Complex abstractions without a "hook" are useless from a pedagogical perspective because pretty soon you have no-one new to teach and the choir is already well versed in the black art of whatever-it-is-that-rings-your-collective-bell.


    I don't think a game needs to be built, but maybe something concrete instead of "lists within lists within lists".. perhaps that is immediately accessible to some here, but for most people, it is better to sort of feel their way around a new paradigm, and Functional Programming _is_ a new paradigm especially for people whose brains have been "messed with" by languages like C or BASIC etc ... 


    So, that is what  I was trying to get at, and at the root of it was a misplaced assertion that perhaps these lectures were for general consumption. Personally, I would love if someone would explain what that game is doing. For example, I looked at the code, and learned something new about "Data" and the "Deriving" part. So I went and looked it up in the Haskell documentation to see what exactly it does.


    You see, when I have the hook, I'll do the leg-work. The "hook" is the concrete part. Something "I" (the proverbial outsider programmer/analyst ie "non haskeller" ) can relate to. Something in the real world which I can anchor myself to and then start feeling around this new "elephant" trying to understand what it is. And I disagree that abstract comparisons between two language definitions (C# and Haskell) are somehow useful for the general population (or that they constitute this "hook" that I speak of.) The people who can be worthwhile contributers to Haskell (if that is a goal at all) are scattered within the technical community, and not necessarily within just C# community. So to claim it is the right thing to do is going a bit far.


    An average programmer (especially a C# programmer) moves bits around and does daily drudge-work and not necessarily spend his/her time philosophizing about higher order functions and how they could be used to optimize the inventory reports. So, it would be more helpful -- maybe not in this lecture series as this is "not Haskell 101" -- if an average daily problem encountered by a generic programmer/developer/ (dare I say Systems Admin?) was presented and then in every lecture the solution was built upon.


    Again, Haskell appeals to me because it strives to be "pure" and is simpler to understand because it presents mathematical concepts without extra fluff or baggage. But I get the feeling that the "high priest" class (the alpha nerds .. not Mr. Meijer or Brian etc.) thinks that certain problems are worthy of their attention while the more pedestrian and mundane aspects of programming are kind of better left on the wayside as they're just not sexy enough to merit any serious intellectual effort in terms of teaching, even though, IMO, mundane things can get you started and then you can go on and spend more time on the hi-fi stuff... but you'd have to be "in the game" to do that. If you walked off because people insisted on teaching you currying (it's great! please don't get me wrong) and really esoteric stuff ... then I don't know if it is realistic to say that FP should be the premier mode of computing. It just won't happen and I don't think the revolution will come from the ranks of play-it-safe hordes of C# programmers. (no offense to play it safe C# programmers I'm sure you're great people to have a beer or two with).


    Again, this is just what I think and I don't mean to hurt anyone's feelings. 



  • User profile image

    Perception is a truth in itself. So if one perceives this lecture series as inaccessible then that is a truth. It may not be the truth for all people but it is for at least a non-empty set of people. I can only speak for myself saying that I can't perceive how it could start out much simpler than what it's done - but for sure: the earlier the practical examples are introduced, the better. Over 'n out. 


    (...Not quite: I don't agree with Charles that this is not a Haskell 101 class. It may be that teaching Haskell is not the purpose of the lecture series but is definitely a significant side-effect of it. And since Haskell has such a compact noiseless syntax it really is ideal for that. It's almost like you don't see the syntax, you only see the core semantics. And the semantics is exactly what you can reuse elsewhere.)

  • User profile image

    I loaded an haskell file with following code on hugs:


    double x = x + x
    quad x = double (double x)
    quadrup = double . double


    If I try "quad 1.01" (without quotes), the correct result of 4.04 is returned but if I try "quadrup 1.01" (without quotes) hugs returns following error message.


    ERROR - Cannot infer instance

    *** Instance : Fractional Integer

    *** Expression : quadrup 1.01


    Hugs returns the following types for quad and quadrup.


    Main> :type quad
    quad :: Num a => a -> a
    Main> :type quadrup
    quadrup :: Integer -> Integer


    Why does quadrup end up with type of Integer -> Integer instead of "Num a => a -> a" ?




  • User profile image
  • User profile image
    var zs = xs.Zip(ys, Tuple.Create);

    Ah, nice, I missed that one!  It can infer up to 8 parameters, I wonder what happens when you use more, or try to zip and list of tuples to itself ....


    Well, I found out ... VS2010 hangs and I had to kill it.  Intellisense was getting slower and slower, and the type became huge in the tooltip.  Eventually with every new line where you are inferring something else, it just locks up.

  • User profile image

    Took Haskell in school and these lectures are great refreshers.


    Looking forward to lecture 4.

  • User profile image

    This is shaping up to be a very nice series. I probably missed it but are the slide decks somewhere? Occasionally a slide is only seen in the far view - and my eyes can't quite pick it up.



  • User profile image

    The slides can be found here.

  • User profile image
    Alexey Zakharov

    Awesome. Perhaps the most hard think to work with haskell is to work without IDE. Only now I recognize how lazy I become after 4 years of C# programming =)


    Erik could u please name IDE you are prefer for Haskell?

  • User profile image

    Actually: name the top IDE's for Haskell.


    PS - looking forward to hearing about non-/termination. I see now that the book you previously recommended, which I hadn't started on yet, Introduction to functional programming using Haskell, does mention this undefined business - i.e. the bottom type.

  • User profile image

    Here is part of the homework:


    1.- What type are the following values:
        ['a','b','c'] :: [Char]
        ('a','b','c') :: (Char,Char,Char)
        [(False,'0'),(True,'1')] :: [(Bool,Char)]
        ([False, True],['0','1']) :: ([Bool],[Char])
        [tail, init, reverse] :: [[a] -> [a]]
    -- 2.- What are the type of the following functions:
    second :: [a] -> a
    second xs = head (tail xs)
    swap :: (a,b) -> (b,a)
    swap (x,y) = (y,x)
    pair:: a -> b -> (a,b)
    pair x y = (x,y)
    double :: (Num a) => a -> a
    double x = x*2
    palindrome :: (Eq a) => [a] -> Bool
    palindrome xs = reverse xs == xs
    twice :: (a -> a) -> a -> a
    twice f x = f (f x)


    Nice lecture, please keep up the good work!!! Smiley

  • User profile image

    It's great man.

  • User profile image

    I have the same problem in ghci.
    What does work though is to type:

    let f :: Int -> Int -> Int; f a b = a + b

    So you need to type the type definition and the function definition in one statement.
    I think this is because you're using an interpreter instead of a compiler.

    I'm a beginner myself so, my apologies if any of the terminology is incorrect.



    Apparently there are multiple pages of comments and this question has already been answered, oops Smiley

  • User profile image

    Erik, can you explain a little about the pseudo "for all" notation you mentioned - why would you use it, when would you not use it?

  • User profile image

    Will we get a video today?

  • User profile image
  • User profile image

    Justin, that is one cool cheat sheet. Thanks!


  • User profile image
  • User profile image

    @DrErikMeijer: .Net has a Pair class, It's tucked away in the System.Web.UI namespace

  • User profile image
    Le garagiste

    I believe from the book or the video that classes are, as types, inferred.

    For example, in exercise 2 the type double accept a Num a class constraint as argument; it's unclear if it is inferred from the operator * , the number 2 or both.

    How does it work effectively?

  • User profile image

    Excellent series so far.  As mentioned previously, I am looking forward to seeing a "real" haskell program.

  • User profile image

    I completely disagree with reddit that the contents of these early lectures are too high falootin'


    I too am a beginner with functional programming, but I recognise that this is the basics, the easy stuff. I'm sure that watching a competent functional programmer write something 'concrete' would knock us beginners on our * and have us longing for content like this.

Add Your 2 Cents

More episodes in this series

Related episodes