Algebraiczne typy w C#

Konkretnie – mamy dwa rodzaje typów algebraicznych danych, które nas interesują: produkty i sumy. Produkty mamy w C# za darmo poprzez wymienienie kilku pól (lub własności) w klasie. Za to z sumami jest trochę ciężej, ale da się!

Niestety, ze strony kompilatora nie mamy na co liczyć i takiego pięknego jednolinijkowca nie zobaczymy (F#):

type Option<'a> = None | Some of 'a

Więc trzeba to jakoś rozwiązać inaczej, żeby jednocześnie było wydajne. Będę nieco bazował na tym co zrobiłem w ramach pracy magisterskiej odnośnie tej wydajności. W pewnym sensie kompilując Haskella do C# mamy jakieś tam typy algebraiczne, ale ja robię type erasure i ich de facto nie mam. To w mojej magisterce, a ten post będzie o praktycznym użyciu sum w C#.

Zacząłem od zdefiniowania bazy dla typów sum.

public abstract class SumType<TEnum> where TEnum : System.Enum
{
    public readonly TEnum Tag;
    
    protected SumType(TEnum tag) => this.Tag = tag;
    
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public S As<S>() where S : SumType<TEnum>
    {
        var p = this;
        return Unsafe.As<SumType<TEnum>, S>(ref p);
    }
}

Bardzo prosta klasa. Parametryzujemy ją enumem, żeby tag miał jasno opisane opcje do późniejszego robienia switchów, a do tego dorzucamy niebezpieczną metodę As, która pozwoli nam na bardzo szybkie rzutowanie instancji na typ zgodny z tagiem.

W oparciu o nią możemy zaimplementować wspomniany wcześniej typ Option<T>:

public abstract class Option<T> : SumType<Option<T>.Enum>
{
    public enum Enum { None = 0, Some = 1 }

    private Option(Enum tag) : base(tag) { }
    
    public sealed class None : Option<T>
    { public None() : base(Enum.None) { } }

    public sealed class Some : Option<T>
    {
        public readonly T Value;

        public Some(T value) : base(Enum.Some)
            => this.Value = value;
    }
}

Nasz typ algebraiczny dziedziczy po SumType i definiuje Enum z elementami określającymi jego konstruktory. Jego konstruktor jest prywatny, co oznacza że tylko wewnętrzne typy mogą po nim dziedziczyć. Dzięki temu nikt nie może nam popsuć kodu tworząc nową podklasę tego typu.

Następnie zadeklarowałem dwa publiczne konstruktory None i Some, które inicjalizują się z odpowiednim tagiem. 16 linijek to nie jedna, ale i tak ten kod jest bardzo zwięzły i czytelny.

W jaki sposób będziemy tego używać? Spróbujmy zaimplementować np. funkcję map

public static Option<U> Map<T,U>(this Option<T> @this, Func<T, U> mapper)
{
    switch (@this.Tag)
    {
        case Option<T>.Enum.None:
            return new Option<U>.None();
        case Option<T>.Enum.Some:
            var x = @this.As<Option<T>.Some>().Value;
            var nx = mapper(x);
            return new Option<U>.Some(nx);
        default: throw new PatternMatchException<Enum>(@this.Tag);
    }
}

Robimy switch na tagu, jak chcemy się dobrać do danych, to robimy As. Niestety ten kod jest trochę mocno verbose, i wszędzie musimy pisać Option<T>.

Ale mamy za to pięknie działające typy algebraiczne. Dzięki temu, że używamy Unsafe.As do castowania, to jest ono bardzo szybkie (bo w zasadzie typ nie jest sprawdzany). W dodatku używając switch z enumem, który pod spodem jest liczbą, możemy skorzystać z optymalizacji w postaci tabeli skoków, przy conajmniej 3 konstruktorach.

Kiedy w kolejnej wersji C# zostaną wdrożone rekordy (przy czym początkowo nie będą wspierać dziedziczenia), to implementowanie typów algebraicznych będzie jeszcze przyjemniejsze.

Kiedy robimy bibliotekę w .NET Standard 2.0, to żeby używać Unsafe trzeba dołączyć referencję do paczki NuGet w pliku projektu:

<ItemGroup>
    <PackageReference Include="System.Runtime.CompilerServices.Unsafe" Version="4.7.1" />
</ItemGroup>

Pełny przykład: gist.

Podziel się: