2014-10-31-better-typeclass-encoding.md

The type class encoding in my previous post on the subject is a bit rubbish:

• type class instances are classes, which have a non-zero creation cost;
• they do not have self-type parameters, so are not necessarily distinguishable at the type level; and
• they do not provide for derived operations.

The Maybe type I described could do with some type class instances, so let’s try out a new encoding.

New encoding

Semigroups are simple and useful so we will start with them.

The type class

The semigroup type class consists of a single binary operation which must be associative.

public interface ISemigroup<S, A>
    where S : struct, ISemigroup<S, A>
{
    A Plus(A a1, A a2);
}

The use of the self-type S and the struct constraint mean that implementations of ISemigroup have to be structs and will always have distinct types.

Derived operations

Derived operations go in a struct.

public struct Semigroup<S, A>
    where S : struct, ISemigroup<S, A>
{
    public A Plus(A x, A y)
    {
        return default(S).Plus(x, y);
    }

    public A Sum(A a, params A[] rest)
    {
        var s = default(S);
        return s.Plus(a, rest.Aggregate(s.Plus));
    }
}

Example: bitfield semigroups

[Flags]
public enum Languages
{
    CSharp  = 0x1,
    FSharp  = 0x2,
    Lisp    = 0x4,
    Haskell = 0x8,
    Rust    = 0x10
}

public struct LanguagesSemigroup : ISemigroup<LanguagesSemigroup, Languages>
{
    public Languages Plus(Languages x, Languages y)
    {
        return x | y;
    }
}

Here are two semigroup implementations for int: sum and product.

public struct IntSumSemigroup : ISemigroup<IntSumSemigroup, int>
{
    public int Plus(int x, int y)
    {
        return x + y;
    }
}

public struct IntProductSemigroup : ISemigroup<IntProductSemigroup, int>
{
    public int Plus(int x, int y)
    {
        return x * y;
    }
}