Posted By: Charles | Nov 5th, 2009 @ 7:53 AM | 40,181 Views | 24 Comments
We've kicked 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). 

We will release a new chapter in this series every Thursday.

In Chapter 6, Dr. Meijer guides us through the world of recursive functions. In Haskell, functions can be defined in terms of themselves.  Such functions are called recursive.
For example: 

factorial 0 = 1
factorial (n+1) = (n+1) * factorial n

factorial maps 0 to 1, and any other positive integer to the product of itself and the factorial of its predecessor.

Some functions, such as factorial, are simpler to define in terms of other functions. As we shall see, however, many functions can naturally be defined in terms of themselves.

Properties of functions defined using recursion can be proved using the simple but powerful mathematical technique of induction.


You should watch these in sequence (or skip around depending on your curent level of knowledge in this domain):

Chapter 1
Chapter 2
Chapter 3
Chapter 4
Chapter 5

Now, we do have a textbook and you should go buy it: The great Graham Hutton's Programming in Haskell. We worked with the publisher, Cambridge University Press, to get all Niners a 20% discount on the book. Now, you don't need the book to learn a great deal from this lecture series since Graham's website has all the slides and samples from the book as well as answers to the exercises. That said, it's highly recommended reading and you should consider it.

The promotion code is 09HASK and it is vaild on both the Hardback:

9780521871723 and Paperback: 9780521692694. The catalog pages are:

Hardback:

http://www.cambridge.org/us/catalogue/catalogue.asp?isbn=9780521871723 and the paperback is:

http://www.cambridge.org/us/catalogue/catalogue.asp?isbn=9780521692694

Note: This special offer is valid until December 31, 2009

Rating:
13
0

Did Erik get sign-off on the poster-frame for chapter 6? Smiley

Any chances of Don Syme doing a similar training series on F#???

 

I'd love to learn me some F#  Wink

 

I'd use the word 'Brilliant', Charles, but for that I think we need to break out 'Awesome'!

 

I'm looking forward to that already! Smiley

 

exoteric
exoteric
embarassingly sequential

I think it's truly great that you do these, I know Don has already spoken several places about F# but a concentrated lecture series is really something which will be even more beneficial to it.

 

Allright, back to the lazy world Wink

 

I couldn't resist the Zip homework first, it looks extremely simple, first with tuple-zip

public static IEnumerable<Tuple<A, B>> Zip<A, B>(this IEnumerable<A> ps, IEnumerable<B> qs)
{
    var pe = ps.GetEnumerator();
    var qe = qs.GetEnumerator();
    while (pe.MoveNext() && qe.MoveNext())
        yield return new Tuple<A, B>(pe.Current, qe.Current);
}

Then we can verify that this behavior is correct by matching up with the built-in behavior

var ps = new[] { 1, 2, 3 };
var qs = new[] { 1, 2, 3, 4, 5, 6 };
var z1 = ps.Zip(qs, Tuple.Create);
var z2 = ps.Zip(qs);
foreach (var x in z1)
{
    Console.Write(x);
    Console.Write(", ");
}
Console.WriteLine();
foreach (var x in z2)
{
    Console.Write(x);
    Console.Write(", ");
}
Console.WriteLine();
Console.Read();

It's trivial to rewrite the tuple definition to the generic function definition.

chudq
chudq
Life is beautiful, and sharing is wonderful!

Very nice show on recursive, even the topic is a basic programming skill.

 

Hugs is new for me. Sometimes I could not get examples in the show to work. Anyway, here are some interfactive examples I played during the time I watch the show.

 

take 2 [1..] -- take first two items as a list from a unlimited list

-- simlar as above with a condiction x > 3 in list -1 to 20

take 2 x where x = filter (>3) [-1..20]

 

I would like to see more codes related to the topics. Enjoy it!

It seems that the animation got lost in the full screen slides.

 

Anyway, if anyone gets stuck on implementing a more efficient reverse function, here's a hint:

  • Define reverse in terms of an auxiliary function.
  • The auxiliary function uses an accumulator.

 

 About the presented Haskell zip function, its definition can be shorter if you reorder the clauses:

zip (x:xs) (y:ys) = (x,y) : zip xs ys
zip _      _      = []

 

exoteric
exoteric
embarassingly sequential

Took a look at Bart's Zip blog post, it also mentions exceptions. How about an expression tree transformation that takes an exception-throwing iterator and rewrites it to force the exceptions first, defining a second helper iterator for the rest. Don't know if it's possible.

 

A less ambitious (and alas less desirable) approach is to implement a first-is-strict combinator that forces and memoizes the first element of the iterator, if there is one, thus forcing the initial exception into the light.

 

Nontheless, both of these approaches are inferior: they delay the inevitable: that some nested throws clause will pop up in the middle of an iterator. This sucks for exceptions as "control flow" rather than proper return types you can examine using regular if statements rather than try/catch.

 

(Not appropos: see this video (from LtU post): - is the world of tomorrow a flashback to the past? Beautiful unicode in APL - when will this come to mainstream; waiting since the sixties seems cruel and inhuman to me! The video also contains a mention of funny puns on the APL name, like APL π, pronounced "apple pie"; and a quote: "changes of a fundamental kind take a long time" - I'll buy that for a dollar)

Microsoft Communities