Statically-typed Heterogeneous Lists in C♯

I typically don’t write C♯ for fun, but what I’ve been doing at work has gotten the juices flowing and I thought I’d share a taste with you. Read on to taste my delicious mind juices.

public static class Examples {
  public static void SingleMember() {
    var list = HList.Create(15);
    Debug.Assert(list.Peek == 15);

    // Compiler error
    // var wat = list.Pop()
  }

  public static void TwoMembers() {
    var list = HList.Create(20).Push("Puppy");

    // Compiler error
    // var sickAndTwisted = list.Peek / 2;

    var twenty = list.Pop().Peek;

    Debug.Assert(twenty == 20);

    // Compiler error
    // var huh = list.Pop().Pop();
  }

  public static void AndSoOn() {
    var list =
      HList
      .Create(1)
      .Push("2")
      .Push(new DateTimeOffset(3, TimeSpan.FromHours(4)))
      .Push(5.0d);

    Debug.Assert(list.Pop().Pop().Pop().Peek == 1);
  }
}

I’ll start with examples to give you an idea of what I mean by “statically-typed heterogeneous list”. Since I’m using a stack-style API, I’ll go backwards through the term. You should know what “list” means, so I’ll use this opportunity to point out that the HList type doesn’t allow for non-empty lists. Due to the static nature of the list, it just wouldn’t make any sense for one to be empty. “Heterogeneous” means that the list can contain values of multiple types. IList<T> is a statically-typed homogeneous list since it only allows values of type T. Finally, “statically-typed” means that the compiler knows the types of the list’s members. The second example demonstrates this well; uncommenting the “sickAndTwisted” line will cause a compiler error, saving the precious puppy within from being cut in half by demented dynamic typing advocates. ArrayList is a dynamically-typed heterogeneous list; you can put values of multiple types in, but the compiler is unaware of their types.

HList shares the most similarity with the built-in (to .NET 4) Tuple type. However, HList can store an arbitrary number of values, at least until the compiler decides it has had enough of nesting generic types. I don’t know when that happens.

public static class HList {
  public static HList<T> Create<T>(T member) {
    return new HList<T>(member);
  }
}

public class HList<TValue> {
  private readonly TValue _member;

  public HList(TValue member) {
    _member = member;
  }

  public TValue Peek {
    get { return _member; }
  }

  public HList<T, HList<TValue>> Push<T>(T member) {
    // Second type argument doesn't matter, but is necessary.
    return HList<T, StackOverflowException>.Create<T>(member, this);
  }
}

public class HList<TValue, TRest> where TRest : class {
  private readonly TValue _member;
  private readonly TRest _rest;

  private HList(TValue member, TRest rest) {
    if(rest == null) {
      throw new ArgumentNullException("rest");
    }

    _member = member;
    _rest = rest;
  }

  internal static HList<TValue, HList<T>> Create<T>(TValue newMember, HList<T> rest) {
    return new HList<TValue, HList<T>>(newMember, rest);
  }

  public HList<T, HList<TValue, TRest>> Push<T>(T member) {
    return new HList<T, HList<TValue, TRest>>(member, this);
  }

  public TRest Pop() {
    return _rest;
  }

  public TValue Peek {
    get { return _member; }
  }
}

As you can see there is no great magic here; it’s basically the first datatype one learns in any functional language, but encoded in the type system. It’s not terribly practical, but it is pretty fun. My hope is that it’ll inspire you to play more with C♯’s type system and static type systems in general. Enjoy!