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

I'm enjoying this series so much and can't wait to see where Erik takes us by the 13th episode! I very much like the 'comp.sci culture and history' asides that Erik provides along with the main course content, keep this up - it both animates and roots the lectures!

I've been waitin for this all day (time difference, you know) -- and it was well worth it.

I love the “back to school” feeling I get with these lectures. I like Novox have been waiting all day for this. Keep up the good work

I love currying and partial application and sectioning just elevates that to a higher level of bliss.

It would be great if this expression type-checked in C#: s.Select(1+).

Then about \x -> x vs x |-> x. I must admit the mathematical notation is less noiseful.

In both situations an IDE should automatically transform both symbols into their unicode equivalents.

So even if typing ==, it will be transformed (graphically) to =, possibly colored differently, and remain unambiguous.

It's also funny, because when trying to model boolean expressions in Java back in 2002, it became very obvious to use this approach outlined by Erik. Still, not entirely convinced it's superior to the functional approach but indeed it does provide some abstraction over structure: F# has these Active Patterns which may be a solution to that problem, haven't looked into it. Let me try again, forgot the old implementation...

It's definitely it's something interesting to ponder.

n+k patterns. Not enough data to conclude non-/justification, must search...

public abstract class Bool { public abstract Bool Not(); public abstract Bool And(Bool _); public abstract Bool Or(Bool _); } public class False : Bool { private False() { } public static readonly Bool A = new False(); public override
 Bool Not() { return True.A; } public override Bool And(Bool _) { return this; } public override Bool Or(Bool that) { return that; } } public class True : Bool { private True() {} public static readonly Bool A = new True(); public override Bool Not() { return
 False.A; } public override Bool And(Bool that) { return that; } public override Bool Or(Bool _) { return this; } } public static class Bools { public static Bool Box(this bool x) { return x ? True.A : False.A; } public static bool Unbox(this Bool x) { return
 x is True; // unsafe : x == True.A; unless we seal } public static Bool Andy(this Bool a, Bool b) { return (a.Unbox() && b.Unbox()).Box(); } public static Bool Ory(this Bool a, Bool b) { return (a.Unbox() || b.Unbox()).Box(); } } 

Day.Exit;

There are editors that replace certain Haskell symbols with their unicode equivalents. One example is emacs as shown in this blog post.

Erik, the series is wonderful -- I have been watching every chapter with much interest.

Fantastic job. Thanks so much and I am really looking forward to watching all the remaining chapters!

Radu

Ok that does it. Time to install Emacs.

...It's a fun idea to use a Lisp-based editor to "type" Haskell

There is not much actual hands-on programming in this show.  For example, for a simple function of abs, I could not figure out how to define it in Hugs. I notice that my Hugs has abs predefined already for using. Then I tried to type in:

 abs1 n = n, n >=0

I got error and could not coninue the next branch. I guess I have to edit my script and load it. How?

This is the fourth new T-shirt Erik wears, however, I think I saw him with this one on a talk about the reverse of IEnumerable in VS 2010. Will Erik have 13 different T-shirts in this series?

I don't think Erik said that was legal Haskell syntax - it was just a personal preference. This is what he showed

abs n | n >= 0    =  n

      | otherwise = -n

@exoteric. I understand Erik's explaination in his script. What is the codes to create similar function in Hugs if possible? Such as abs1 or f x like:

f x = 4711

(what Sylvan says after this)

To be honest, people really don't use hugs/ghci for actually writing definitions. It's more for testing the definitions you have in a .hs file... Once you know more Haskell you'll understand better what the ghci prompt is (it's essentially right in the IO monad, hence the need for "let" etc. to declare things). 

Do yourself a favour and type your code in a .hs file, use ":r" to reload it each time and just use the interactive prompt to test the functions, it'll save you some head aches!

This series is fast becomming one of my favorties on Channel9 (second to the Parallelism discussions). Erik does an excellent job in his explainations and as always is a joy to watch.

Keep up the great work!

I am delighted to have found this series. Really great stuff, and it's a real pleasure to have access to such a top-tier instructor.  Thanks Erik!

In the function

    add = \x -> (\y -> x+y)

how can the inner function \y access the value of x when it is defined to take only a single parameter y?

And why does the expression

   (-1) 3

return an error, but

  (/2) 6

is fine?

-Roy

That's simple: (-) is both a unary (-a) and binary (a - b) operator, so to partially apply the binary overload just flip the first argument to the left side to section the binary operator: i.e. (1-) instead of (-1), then it can't possibly be misread by the compiler as meaning "minus one". (/2) on the other hand is unambiguous since there is no unary definition of (/). And to be absolutely clear, the error arises from the fact that when you say (-1) you have a number literal which is not a function and therefore it makes no sense to try to apply 3 to it.

Second (or first as it were) problem. See this code in C#

Func<int, Func<int, int>> add = a => b => a + b; int add_1_2 = add(1)(2); Console.WriteLine(add_1_2);

This is the same pattern as in Haskell and all the outer values are captured and accessible to the inner expressions. Erik can elaborate on this more than me.

A more philosophical question, is this

abs n | n >= 0 = n | otherwise = -n

really better than this

abs n | n ≥ 0 = n | n < 0 = -n 

Function application is like search/replace. If we have the following definition:

add = \x -> (\y -> x+y)

If we apply the function to e.g. 3, we'll get:

add 3 = {- replace add by its definition -} (\x -> (\y -> x+y)) 3 = {- now substitiute 3 for x, i.e. function application -}  {- no further substitution possible -}

Now, if we'll apply this result to e.g. 4, we'll get:

(\y -> 3+y) 4 = {- function application, sub 4 for y -} 3+4 = {- use the definition of (+) -} 7

I understand, as exoteric says, that the symbol - is overloaded to mean both unary negation and binary subtraction, but it seems wrong that the only solution is to flip the arguments in the section. Subtraction isn't commutative so it's not equivalent. For example: (1-) 3 yields -2 while, if it worked, I would expect (-1) 3 to yield positive 2.

The only solution I can come up with is to bind it to a name (prefix though) and then use that name in a secion (infix), something like: let subtract = (-) in (`subtract` 1) 3

There must be a better way...

To get what  you want you can use the function flip that is on the haskell prelude.

The Haskell  prelude defines flip as:

-- flip f  takes its (first) two arguments in the reverse order of f.
flip             :: (a -> b -> c) -> b -> a -> c
flip f x y       =  f y x

using flip we can write (-1) 3 as:

(flip (-) 1) 3  

Also, the prelude has a substract function defined as:

subtract         :: (Num a) => a -> a -> a
subtract         =  flip (-)

Hello to all the other newcomers, I saw this on reddit and I think this series of lectures is suitable for people new to Haskell? For people like me Erik is a bit out of reach right now, but after learning some more I will be able to grasp the C9 lectures better I think?

Please also check this out: 

FP Course using Haskell: In English (class notes or 'transparencies' in PDF format are on this page and are also helpful):

http://verify.rwth-aachen.de/fp05/

Course and Exercise Sessions Videos:

http://video.s-inf.de/#FP.2005-SS-Giesl.%28COt%29.HD_Videoaufzeichnung

All videos starting with V are videos. Videos Starting with U are exercise session. Full resolution videos are about 800mb and lowres are about half that (400mb or so?)

the reddit thread is here.

http://www.reddit.com/r/programming/comments/9xo3m/lectures_on_functional_programming_using_haskell/

Pretty cool although I think Erik is more clear in his explanations but nice "high-fidelity" video.

Thanks ShinNoNoir and exoteric.  

This is analogous to correlated subqueries in SQL, which also tax my brain.

I guess what I find weird about \x -> (\y -> x+y) is:

1. the syntax suggests to me that the definition of \y is complete within the parentheses, but it has a dependency that reaches outside the parens and raises questions about the limits of scope; and (related)

2. in other programming contexts one learns to read parentheses from innermost to outermost.  But here we need to read it left to right.

I guess it's just going to take a while to learn to think like the Haskell parser. 

Another example that twists my C/C++ programmer's brain: we can define tail as

   mytail (_:xs) = xs

Very logical, but this assumes that the language is able to deconstruct the list input to understand that it can be thought of as a single element added to a list.  Cool that the language can do that, but not obvious, and leaves me wondering what other sorts of deconstructions it is capable of making that are not obvious.  Can I do drop2 (b:(a:xs)) = b:xs to drop the second item?  How will we know the limits of such constructs without just trial and error?  I'm sure this will become more clear as we go on.

re: (-1) 3 --- agreed that the problem is that -1 can be read (and apparently IS read) as negative 1.  Surprising then that we can't use ((-)1) 3 or something analogous.  The flip business seems very convoluted.  But I suppose this is a minor syntactic quirk originating from the overloaded use of the - symbol, and since it only impacts a syntax shortcut, it's probably not worth worrying too much about.

Re: parentheses, the ones around the lambda are just the same as in any ordinary expression, for example:

foo x y = x * (y+x)

About the language being able to deconstruct lists, that's because Haskell is designed to deconstruct any algebraic data type (ADT).

-- ADT for a linked list: data List a -- [a] <--> List a = Cons a (List a) -- (:) <--> Cons | Nil -- [] <--> Nil -- ADT for a binary tree: data BTree a = Node (BTree a) (BTree a) | Empty

And yes, your drop2 function does exactly what you say it does, although you don't need the inner parentheses in the pattern.

About the minus business, yes, that's a syntax quirk.

You have to enter a script into a file and load it into the interpreter. ghci will let you type

let abs x = if x < 0 then -x else x

but it won't let you enter the type information. WinHugs doesn't allow this at all.

Here is my take on part of the homework

1. safetail

safetaila :: [a] -[a] safetaila xs = if null xs then [] else tail xs safetailb :: [a] -[a] safetailb xs | null xs = [] | otherwise = tail xs safetailc :: [a] -[a] safetailc [] = [] safetailc (_:xs) = xs 

2. Implement (||)  in three different ways

(||!) :: Bool -Bool -Bool True ||! True = True True ||! False = True False ||! True = True False ||! False = False (||@) :: Bool -Bool -Bool False ||@ False = False _ ||@ _ = True (||#) :: Bool -Bool -Bool False ||# b = b True ||# _ = True

(&&$) a b = if a == True && b == True then True else False

(&&%) a b = if a == True then b else False

Code seems to be good, paks8150, but why are your definition arrows (-) instead of (->)?

Did Erik misspeak or did I misunderstand the point during the discussion about lazy evaluation compared to short-circuit evaluation behavior in C#, etc?  Compiler optimizations aside, the second parameter would not be evaluated if the first were false.  NB: because I don't trust myself I even wrote a small C# test harness with an if statement whose first argument always evaluates to false and whose second argument is a call to a function that would loop forever (and verified using Reflector that it wasn't inlined or otherwise optimized away) and it returned as expected without looping.  Again, maybe the point of the discussion was some more subtle meaning of "evaluated" than my coarse brain grokked...

*Excellent* series, btw.  Can't thank you all enough for doing this (and I must say I'm enjoying the commentary from the clearly knowledgable community members such as exoteric and ShinNoNoir nearly as much...).  Cheers!

@charles - I'm having some trouble getting the Zune version of this lecture (and a couple of other ones from the series).  When I try to open it in the Zune player it says "file is corrupt or invalid", but they do play just fine in Media player.  BTW, I downloaded the windows media version of this episode, and Zune player opens it without complaint.

Very late to the class... again

my shot at the homework. Incomplete, of course.

--Case of dynamic dispatch...

class Bool {

   public:
      virtual Bool* operator!(void) = 0;   
      virtual Bool* operator&&(Bool&) = 0;
      virtual Bool* operator||(Bool&) = 0;
};

class True : public Bool {

   Bool* operator!(void);
 
   Bool* operator&&(Bool& ref) {
     
      return &ref;      
   }

   Bool* operator||(Bool& _) {
   
      return new True();     
   }      
};

class False : public Bool {

      
   Bool* operator!(void);
     
   Bool* operator&&(Bool& _) {
  
      return new False();       
   }

   Bool* operator||(Bool& ref) {
   
      return &ref;   
   }      
};

Bool* True::operator!(void) {

   return new False();  
}

Bool* False::operator!(void) {

   return new True(); 
} 

int main(void) {

   class Bool *Bt = new True();
   class Bool *Bf = new False();
  
   *Bt&&*Bf;
   *Bf&&*Bt;

   *Bf||*Bt;

   !*Bf;

   return 0; 
}

--Case of double dispatch...

 #include <iostream>

using namespace::std;

class Bool {
  
   public:
      virtual Bool* AND(Bool&) = 0;
      // TF is for true or false
      virtual Bool* TF(void) = 0;
};

class True : public Bool {
 
   Bool* TF(void) {

      cout<<"True"<<endl;
      return new True();   
   }

   Bool* AND(Bool& ref) {

      return ref.TF();    
   }   
};

class False : public Bool {

   Bool* TF(void) {
     
      cout<<"False"<<endl;
      return new False();   
   }

   Bool* AND(Bool&) {

      return TF();
   }      
};

int main(void) {

   Bool *Bt = new True();
   Bool *Bf = new False();

   Bt->AND(*Bf);

   Bf->AND(*Bt);

   Bt->AND(*Bt);

   return 0;
}

Sohail Qayum Malik