CODEWITHSUNDEEP
c#consgreenspunning
Alexey
Alexey

Reputation: 1424

Statically typed well-formed cons list in C#

I've asked myself a stupid question and have been wracking my brain for a few hours now with no result.

Let's say you want to implement a cons cell in C# for whatever reason (Greenspun's tenth rule should be enough). Since it's in C#, you want it to be statically typed. Something like this should suffice:

interface ICons<T, U>
{
    T Left { get; }
    U Right { get; }
}

struct Cons<T, U> : ICons<T, U>
{
    public T Left { get; }
    public U Right { get; }

    public Cons(T left, U right)
    {
        Left = left;
        Right = right;
    }
}

struct Nil : ICons<Nil, Nil>
{
    public Nil Left => this;
    public Nil Right => this;
}

Now there's a static void VisitList<T>(? list, Action<T> action) method that accepts a well-formed list of T and does something to each element. A well-formed list of T is a Nil or a cons cell that has T as its left element and a well-formed list of T as its right element. Now we can replace ? with a real type (yes, imagine there's an Either not-monad): static void VisitList<T, U>(Either<Nil, ICons<T, U>> list, Action<T> action) where U : Either<Nil, ICons<T, U>>.

The impossible question is: how the heck do you construct a value that you can pass to this method? Can anyone write a working snippet? The rest of the sample code follows.

class Either<T, U>
{
    public bool IsRight { get; }
    public bool IsLeft => !IsRight;
    public T Left { get; }
    public U Right { get; }

    public Either(T left)
    {
        IsRight = false;
        Right = default(U);
        Left = left;
    }

    public Either(U right)
    {
        IsRight = true;
        Left = default(T);
        Right = right;
    }

    public static implicit operator Either<T, U>(T value) => new Either<T, U>(value);
    public static implicit operator Either<T, U>(U value) => new Either<T, U>(value);
}

class Program
{
    static void VisitList<T, U>(Either<Nil, ICons<T, U>> list, Action<T> action)
        where U : Either<Nil, ICons<T, U>>
    {
        while (list.IsRight) {
            action(list.Right.Left);
            list = list.Right.Right;
        }
    }

    static void Main(string[] args)
    {
        VisitList(/*put your well-formed cons list here*/, WriteLine);
        ReadKey(true);
    }
}

Upvotes: 5

Views: 476

Answers (0)

Related Questions