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 6 of 13

Download

Right click “Save as…”

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

Chapter 6
Chapter 7
Chapter 8
Chapter 9
Chapter 10
Chapter 11
Chapter 12
Chapter 13

Tags:

Follow the Discussion

  • 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

     

  • CharlesCharles Welcome Change

    Yes, in fact. Smiley Stay tuned.

    C

  • 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

     

  • CharlesCharles Welcome Change

    The Don Syme lectures will be broken up into 3 parts. These won't air until after the PDC.

    C

  • Bent Rasmussenexoteric stuck in a loop, for a while

    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.

  • David Chuchudq Life is beautiful, and sharing is ​wonderful&#​33;

    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 _ _ = []

     

  • Bent Rasmussenexoteric stuck in a loop, for a while

    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)

  • wewe

    The factorial function defined with the (n+k) pattern will not go into an infinite loop when given a negative number. (n+k) patterns only match with numbers >=k. So you would rather get an exception about non-exhaustive patterns.

  • wewe

    It's so cool to hear Erik saying that explicit recursion can be abstracted. I can't wait to see you mention the paper "Functional programming with bananas, lenses, envelopes and barbed wire"!

  • My book finally arrived, after just over a month of waiting... Tongue Out

  • Again, nice lecture.  I'm lloking forward to the rest.

     

    Here is my take on Append:

    public static IEnumerable<T> Append<T>(this IEnumerable<T> a, IEnumerable<T> b) { foreach (var t in a) { yield return t; } foreach (var t in b) { yield return t; } } 

  • More homework:

    1) Prove that fac n = recfac n

     

    Definition of recfact n:

    (1)        recfac 0 = 1

    (2)        recfac (n+1) = (n+1) * recfact n

     

    Definition of fac n:

    (3)        fac n = product [1...n]

                            where

    (4)                                product [] = 1

    (5)                                product [1..n] = 1 * 2 * … (n-1) * n

     

    We want to prove that:

    Devil                    fact n = recfac n

     

    Using induction:

     

    Case n = 0

                fac 0 = recfac 0

     

                fac 0 = 1 (Eq. 1)

     

                recfac 0 = product [1 .. 0] = product [] = 1 (Eq. 4)

     

                1 = 1

     

    Case (m + 1):

    (7)        fac (m+1) = recfac (m+1)

     

    fac (m+1) = product [  1..(m+1)] = 1 * 2 *….* m * (m+1)

     

    1. Using Eq.5:       1 * 2 *….* m  = product [1..m]

     

                fac (m+1) = 1 * 2 *….* m * (m+1)  =(product [1..m]) * (m+1)

     

    (8)        fac (m+1) = (product [1..m]) * (m+1)

     

    Using Eq 2 :  recfac (m+1) = (m+1) * recfac m

     

     

    Replacing Eq 8 into Eq 7:

                fac (m+1) = (product [1..m]) * (m+1) = recfac (m+1)

     

    Using Eq 2 on the right side:

                (product [1..m]) * (m+1) = (m+1) * recfac m

     

    Dividing by (m+1) on both sides:

                product [1..m] = recfac m

     

    Using Eq 3 on the left side:

                fac m = recfac m

     

    Q.E.D.! Smiley

  • Bart De Smetbdesmet Bart De Smet ​[MSFT::SQL::​Cloud​Programmabi​lity::Rx]

    Concerning the Zip homework, a couple of things to keep in mind:

    • Do proper argument validation: both input IEnumerable objects and the zipper function should not be null. This is a bit tricky. (Tip: when does the exception get thrown by the iterator?)
    • IEnumerator objects implement IDisposable. Make sure the enumerator objects get disposed correctly under all circumstances. (Tip: don't overcomplicate it; the language can do lots of work for you)

    Additional brain gymnastics can be triggered by trying to define Zip in terms of other LINQ Standard Query Operators. Enjoy!

  • Bent Rasmussenexoteric stuck in a loop, for a while

    (I'm not at home right now so no thorough answer, but -) I know you need to force exception handling by using another method to do the actual implementation, otherwise the exceptions will be thrown when the stream is enumerated and for disposal, well we have using statements, need to check that later. Nice having you here, Bart.

     

    Smiley

  • Towards the end of the video Erik referred to the slides. Where are those slides???

    It's a hassle working on the homework off the video stream, would be much easier if looking thru the PPT.

    Can we get the download link?

     

    Thanks

  • wewe

    http://www.cs.nott.ac.uk/~gmh/book.html#slides

  • Bent Rasmussenexoteric stuck in a loop, for a while

    OK, this is a quick write-up that would seem to fit the bill

     

    public static class Extensions { public static IEnumerable<Tuple<A, B>> Zip<A, B>(this IEnumerable<A> ps, IEnumerable<B> qs) { if (ps == null) throw new ArgumentNullException("ps"); if (qs == null) throw new ArgumentNullException("qs");
     return ps.DoZip(qs); } private static IEnumerable<Tuple<A, B>> DoZip<A, B>(this IEnumerable<A> ps, IEnumerable<B> qs) { using (var pe = ps.GetEnumerator()) { using (var qe = qs.GetEnumerator()) { while (pe.MoveNext() && qe.MoveNext()) yield return new Tuple<A,
     B>(pe.Current, qe.Current); } } } }

    • Using nested using statements for resource disposal, as prescibed by C# for easy exception safe resource disposal.
    • Using a separate method to ensure exceptions are thrown upon calling the method.
    This doesn't use the more generic version using a function but the pattern is the same (the lower-order Zip can of course be written in terms of the higher-order Zip using Tuple.Create).
    As for writing Zip in terms of other LINQ operators: haven't looked into it but you wrote about that, I remember, although not what your precise solution was.

  • I think it's amusing that you refer to Hughes paper on FP as such a good paper, because I'm taking a class of his right now, and he strongly recommends this video series Smiley And, yes, it's a great paper. Good read. Thanks for the awesome video lectures, they complement his course very well!

  • Here is my take on the homework:

     

    1.- Define:

     

    and :

    and' :: [Bool] -> Bool and' [] = True and' (False:_) = False and' (_:xs) = and xs 

     

    concat:

    concat' :: [[a]] -> [a] concat' [] = [] concat' (xs:xss) = xs ++ concat' xss

     

    replicate:

    replicate' :: Int -> a -> [a] replicate' 0 x = [] replicate' (n+1) x = x:replicate' n x

     

    Select the Nth statement of a list:

    (!!@) :: [a] -> Int -> a (!!@) (x:_) 0 = x (!!@) (_:xs) (n+1) = xs !!@ n

     

    elem:

    elem' :: (Eq a) => a -> [a] -> Bool elem' _ [] = False elem' x (y:ys) | x == y = True | otherwise = elem' x ys

     

    2. Define merge :: [Int] -> [Int] -> [Int]

    merge:: (Ord a) => [a] -> [a] -> [a] merge [] [] = [] merge xs [] = xs merge [] ys = ys merge (x:xs) (y:ys) | x < y = x:merge xs (y:ys) | x == y = x:y:merge xs ys | otherwise = y:merge (x:xs) ys

     

    3. Define merge sort:

    msort :: (Ord a) => [a] -> [a] msort [] = [] msort [x] = [x] msort xs = merge (msort ys) (msort zs) where [(ys,zs)] = halve xs halve :: [a] -> [([a],[a])] halve [] = [] halve xs = [(take n xs, drop n xs)] where n = (length xs `div` 2)

     

    I'm having a blast with this series. Smiley

  • Bent Rasmussenexoteric stuck in a loop, for a while

    It's probably not a complete coincidence that Charles speaks of the high priests of the Lambda calculus.

     

    - folded hands, closed eyes, tilted head, pointing to the sky

     

    May the monad be with you!

     

    Big Smile

  • CharlesCharles Welcome Change

    Indeed! You are right, brothers. That still shot captures a moment of extreme reverence, a moment in time where Dr. Meijer, a reverend of the Lambda, evangelist of the functional composition of the monadic universe, exudes his deep thanks and praises for the higher-order function in the sky.

     

    C

  • Somewhere closer to the end of the talk, Mr. Meijer says that segregation of common parts

    of a function from the distinct parts is only possible with lazy evaluation (with the two clouds

    drawn on the board). Didn't he really mean functional composition instead, which is more

    general than lazy evaluation? If the distinct parts have no side-effects and the common part has

    no influence on the distinct parts besides parametrization (as is the case with pure functions),

    then you can also call the common part as a function with distinct parts as pure functional or

    value parameters to that common function.

     

    Of course you might save some computations with lazy evaluation, but I am quite sure I have

    applied this technique with eager evaluation as well!

     

    Am I missing something?

  • Sohail Qayum MalikAeon Sohail Qayum Malik

    Finally got some time and went through this lecture too...

     

    (!!) :: [a] -> Int -> a
    (a:as) !! 0 = a
    (a:as) !! (n + 1) = as Main.!! n

    (++) :: [a] -> [a] -> [a]
    [] ++ [] = []
    as ++ [] = as
    [] ++ bs = bs
    (a:as) ++ (bs) = a : (Main.++) as bs

    (&&) :: Bool -> Bool -> Bool
    True && True = True
    _ && _ = False

    length :: Num a => [a] -> Int
    length [] = 0
    length [x] = 1
    length (a:as) = 1 + Main.length as

    take :: Num a => Int -> [a] -> [a]
    take 0 _ = []
    take _ [] = []
    take (n + 1) (a:as) = a : Main.take n as

    drop :: Num a => Int -> [a] -> [a]
    drop 0 as = as
    drop _ [] = []
    drop (n + 1) (a:as) = Main.drop n as

    qsort :: Ord a => [a] -> [a]
    qsort [] = []
    qsort [a] = [a]
    qsort (a:as) = qsort smaller Main.++ [a] Main.++ qsort greater
         where
    smaller = [x | x <- as, x <= a]
    greater = [x | x <- as, a < x]

    and :: [Bool] -> Bool
    and [] = True
    and (a:as) = a Main.&& Main.and as

    concat :: [[a]] -> [a]
    concat [] = []
    concat (a:as) = a Main.++ Main.concat as

    replicate :: Int -> a -> [a]
    replicate 0 a = []
    replicate (n + 1) a = a : Main.replicate n a

    elem :: Eq a => [a] -> a -> Bool
    elem [] _ = False
    elem (a:as) s = if a == s then True else Main.elem as s

    merge :: [Int] -> [Int] -> [Int]
    merge [] [] = []
    merge [] bs = bs
    merge as [] = as
    merge as bs = qsort $ as Main.++ bs

    msort :: [Int] -> [Int]
    msort [] = []
    msort [a] = [a]
    msort as = merge (msort $ Main.take n as) (msort $ Main.drop n as)
          where
              n = Main.length as `div` 2

     

    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.