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

## The Discussion

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

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

OK - done pimping now

Justin

• 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

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

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

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

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

• Justin, Thanks for the cheatsheet..

f::Int->Int->Int

or

f::(Int->(Int->Int))

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?

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

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

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

Prelude> :t zip

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

Prelude>

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

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

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

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

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

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

(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*?

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

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

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

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

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

C

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

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

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

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

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

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

```

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

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

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

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

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

double x = x + x
quad x = double (double x)

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

quad :: Num a => a -> a

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

• You have hit a subtlety in the Haskell design

....

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

• Took Haskell in school and these lectures are great refreshers.

Looking forward to lecture 4.

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

Thanks

• The slides can be found here.

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

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

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

• It's great man.

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

-edit-

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

• Will we get a video today?

• Justin, that is one cool cheat sheet. Thanks!

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

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

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

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