[Haskell-cafe] Mapping Haskell Concepts To C# 3

[Derek Elkins]

On Sat, 2008-05-17 at 20:51 +0100, Sebastian Sylvan wrote:
> 
> 
> 2008/5/17 Kaveh Shahbazian <kaveh.shahbazian at gmail.com>:
>         I have question on mapping some Haskell concepts to C# 3 ones.
>         Maybe there are not any strict equivalents; yet it helps:
>         
>         1 - What is the equivalent of "Type Constructor" in C#?
> 
> Class declaration. Generic ones. E.g. List<int>, is a type where the
> type constructor List has been applied to the type int.
>  
>         
>         2 - What is the equivalent of "Data Constructor" in C#?
> 
> Constructors, I guess.
>  
>         
>         3 - What is the logical implementation of pattern matching in
>         C#? (For example using structures with indicator fields or
>         using interfaces and inheritance and dynamically dispatch in
>         calling overloaded methods. Also this question contain a
>         hidden one...GADTs!)
> 
> You can use an abstract base class, and then inherit one class for
> each constructor (e.g. base class Expression, and concrete subclasses
> Mul, Add, etc.). Then you can use runtime type reflection to figure
> out which kind of Expression you have and branch on it.

Ideally you would use dynamic dispatch, not "type reflection" for this,
e.g.
abstract class List<A> {
    public abstract int Length();
    public abstract List<A> Append(List<A> xs);
    public abstract B Foldr<B>(Func<A,B,B> cons, B nil);
}

class Nil<A> : List<A> {
    public Nil() {}
    public override int Length() { return 0; }
    public override List<A> Append(List<A> xs) { return xs; }
    public override B Foldr<B>(Func<A,B,B> cons, B nil) { return nil; }
}

class Cons<A> : List<A> {
    public Cons(A a, List<A> as) {
        Head = a; Tail = as;
    }
    public override int Length() { return 1 + Tail.Length(); }
    public override List<A> Append(List<A> xs) {
        return new Cons<A>(Head, Tail.Append(xs));
    }
    public override B Foldr<B>(Func<A,B,B> cons, B nil) {
        return cons(Head,Tail.Foldr(cons,nil));
    }

    public readonly A Head;
    public readonly List<A> Tail;
}

The Foldr method does make some constructors a bit special, but not too
much.

class Append<A> : List<A> {
    public Append(List <A> xs, List<A> ys) {
        Front = xs; Back = ys;
    }
    public override int Length() {
        return Front.Length() + Back.Length();
    }
    public override List<A> Append(List<A> ys) {
        return new Append<A>(this, ys);
    }
    public override B Foldr<B>(Func<A,B,B> cons, B nil) {
        Front.Foldr(cons, Back.Foldr(cons, nil));
    }

    public readonly List<A> Front, Back;
}

We could, of course, define Cons.Append to use the Append class instead.