Back to Profile: ShinNoNoir


  • C9 Lectures: Dr. Erik Meijer - Functional Programming ​Fundamental​s, Chapter 3 of 13

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

  • C9 Lectures: Dr. Erik Meijer - Functional Programming ​Fundamental​s, Chapter 2 of 13

    Let's mention the M-word in this thread. Tongue Out

    -- from the slides: double x = x + x quadruple x = double (double x) -- Erik's pointfree version of quadruple from the whiteboard: quadruple = double . double -- The version of a Haskell programmer in love with the Reader monad: double
     = join (+) quadruple = join (.) double 

  • C9 Lectures: Dr. Erik Meijer - Functional Programming ​Fundamental​s, Chapter 2 of 13

    You could introduce a safeHead function if you really want to be safe:

    safeHead :: [a] -> Maybe a safeHead [] = Nothing safeHead (x:xs) = x

    Otherwise you have to make sure you never use head on an empty list. Regarding non-empty lists, here's how you'd define them in Haskell:

    data Stream a = Cons a (Stream a)

  • C9 Lectures: Dr. Erik Meijer - Functional Programming ​Fundamental​s, Chapter 2 of 13

    You cannot define functions in Hugs using "let foo x = bar", but you can in GHCi. So if you're using Hugs, you have to define your function in a file or use a "let ... = ... in ..." expression:

    > let double x = x + x  in  double 4

  • C9 Lectures: Dr. Erik Meijer - Functional Programming ​Fundamental​s, Chapter 2 of 13

    Regarding ≤ and ≠, yes, they are legal operator names, but no, they are not defined in the Prelude. Here's how you would define ≤:

    x ≤ y = x <= y

    Or alternatively:

    (≤) :: Ord a => a -> a -> Bool
    (≤) = (<=)

  • C9 Lectures: Dr. Erik Meijer - Functional Programming ​Fundamental​s, Chapter 1 of 13

    Here's my ugly attempt at writing a functional qsort in C#. First I'll introduce a pair data structure:

    public struct Pair<A, B>
        public A First { get; set; }
        public B Second { get; set; }

    Then a few extension methods:

    public static Pair<IEnumerable<T>,IEnumerable<T>>
        Partitions<T>(this IEnumerable<T> xs, Func<T, bool> p)
        var partitions =
            (from x in xs
             group x by p(x) into g
             select g).ToDictionary(g => g.Key);
        return new Pair<IEnumerable<T>,IEnumerable<T>>()
            First = partitions.ContainsKey(true)
                ? partitions[true].AsEnumerable() 
                : Enumerable.Empty<T>(),
            Second = partitions.ContainsKey(false) 
                ? partitions[false].AsEnumerable() 
                : Enumerable.Empty<T>()
    public static bool IsNil<T>(this IEnumerable<T> xs)
        return !xs.GetEnumerator().MoveNext();
    public static bool LessThan<T>(this T x, T y) where T : IComparable<T>
        return x.CompareTo(y) < 0;


    Finally, QSort itself:

    public static IEnumerable<T> QSort<T>(this IEnumerable<T> xs) where T : IComparable<T>
        if (xs.IsNil())
            return Enumerable.Empty<T>();
            var pivot = xs.First();
            var p = xs.Skip(1).Partitions(y => y.LessThan(pivot));
            var smaller = p.First;
            var larger = p.Second;
            return smaller.QSort()
                .Concat(new List<T>{pivot})


    Edit: I was bored and also wrote a Python version... Tongue Out

    def partition(xs, p):
        z = ([],[])
        for x in xs:
        return z
        # Note that partition is not quite functional, as it uses mutation.
        # The mutation, however, only affects local values. The function
        # partition for the outside world is referential transparent.
    def qsort(xs):
        if not xs:
            return []
            pivot = xs[0]
            smaller, larger = partition(xs[1:], lambda x: x < pivot)
            return qsort(smaller) + [pivot] + qsort(larger)