Choice, An Algebraic Answer

C# allows you to model sets via enumerations (the enum kind of type). Take for example

public enum Choice
{
    Either,
    Or
}

Now how if one wanted to model not just a choice but a choice between values. There is no way to do that with C# enums as of today.

Languages with algebraic data types (ADTs) allow this, witness this example

public enum Either<α, β>
{
    either(x: α);
    or(x : β);
}

Notice that this specification does not depend on the choice of values to necessarily have the same type or any particular type, this is just using parametric polymorphism. Don’t be distracted by the greek symbols, you could have used any identifier, such as S and T, as is common in .Net land.

Suffice it to say I wanted to adapt this for C# to see if I could possibly model choice in a nice way. And so I first tried this

public enum Choice
{
    Either,
    Or
}

public sealed class Either<α, β>
{
    private Either(α a = default(α), β b = default(β))
    {
        this.First = a;
        this.Second = b;
    }

    ...

    public readonly α First;

    public readonly β Second;

    public readonly Choice Choice;
}

Now of course in this example we could have used a bool because the set only has two types, but really we don’t want to be limited to that, and we also want the type to say what “true” is and what “false” is.

The real dissatisfying aspect of this solution is that it separates the “tag set” from the value set – you have two constructs instead of one. This is clearly a dissatisfactory solution.

And so working a bit more with this, I came up with this solution

public abstract class Choice<α, β>
{
    protected Choice(α a = default(α), β b = default(β))
    {
        this.First = a;
        this.Second = b;
    }

    public readonly α First;

    public readonly β Second;
}

public sealed class Either<α, β> : Choice<α, β>
{
    public Either(α x)
        : base(x, default(β))
    {
    }
}

public sealed class Or<α, β> : Choice<α, β>
{
    public Or(β x)
        : base(default(α), x)
    {
    }
}

This specification, although not as clean as a pure ADT specification, has desirable properties. A type of choice is expressed as a subtype. Testing a value for what kind of choice it is amounts to using the is operator, as in “a is Either<int,bool>”.

I’m going to be experimenting with what can be done with this style and this type family in particular.

The solution has some validation because I believe it is similar to the hybrid functional object-oriented language Scala uses, which is quite state-of-the-art in this respect; some memories of Scala must have been floating around when solving this.

Feel free to use.

Advertisements

About xosfaere

Software Developer
This entry was posted in Program, Software, Technical, Uncategorized and tagged , , , , , , . Bookmark the permalink.

One Response to Choice, An Algebraic Answer

  1. xosfaere says:

    I just found a nice article on this for Java. It is much more in-depth and can be translated to C# as well. See http://bit.ly/naENH

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s