Как вы кодируете алгебраические типы данных в C # или Java-подобном языке?

Есть некоторые проблемы, которые легко решаются алгебраическими типами данных, например, тип List может быть очень кратко выражен как:

data ConsList a = Empty | ConsCell a (ConsList a)

consmap f Empty          = Empty
consmap f (ConsCell a b) = ConsCell (f a) (consmap f b)

l = ConsCell 1 (ConsCell 2 (ConsCell 3 Empty))
consmap (+1) l

Этот конкретный пример написан на языке Haskell, но в других языках он будет аналогичным с нативной поддержкой алгебраических типов данных.

Оказывается, существует очевидное сопоставление с подтипами в стиле ОО: тип данных становится абстрактным базовым классом, а каждый конструктор данных становится конкретным подклассом. Вот пример в Scala:

sealed abstract class ConsList[+T] {
  def map[U](f: T => U): ConsList[U]
}

object Empty extends ConsList[Nothing] {
  override def map[U](f: Nothing => U) = this
}

final class ConsCell[T](first: T, rest: ConsList[T]) extends ConsList[T] {
  override def map[U](f: T => U) = new ConsCell(f(first), rest.map(f))
}

val l = (new ConsCell(1, new ConsCell(2, new ConsCell(3, Empty)))
l.map(1+)

Единственное, что нужно помимо наивного подкласса - это способ запечатать классы, то есть способ сделать невозможным добавление подклассов в иерархию.

Как бы вы подошли к этой проблеме на языке, таком как C # или Java? Два камня преткновения, которые я обнаружил при попытке использовать алгебраические типы данных в C #:

• Я не мог понять, как называется нижний тип в C # (то есть я не мог понять, что поместить в class Empty : ConsList< ??? >)
• Я не мог найти способ запечатать, ConsList чтобы никакие подклассы не могли быть добавлены к иерархии

Каков был бы самый идиоматический способ реализации алгебраических типов данных в C # и / или Java? Или, если это невозможно, какой будет идиоматическая замена?

Существует простой, но сложный способ герметизации классов в Java. Вы помещаете частный конструктор в базовый класс, а затем создаете его подклассы.

public abstract class List<A> {

   // private constructor is uncallable by any sublclasses except inner classes
   private List() {
   }

   public static final class Nil<A> extends List<A> {
   }

   public static final class Cons<A> extends List<A> {
      public final A head;
      public final List<A> tail;

      public Cons(A head, List<A> tail) {
         this.head = head;
         this.tail = tail;
      }
   }
}

Прикрепите шаблон посетителя для отправки.

Мой проект jADT: Java Algebraic DataTypes генерирует все эти шаблоны для вас https://github.com/JamesIry/jADT

Вы можете добиться этого с помощью шаблона посетителя , который будет дополнять сопоставление с шаблоном. Например

data List a = Nil | Cons { value :: a, sublist :: List a }

может быть написано на Java как

interface List<T> {
    public <R> R accept(Visitor<T,R> visitor);

    public static interface Visitor<T,R> {
        public R visitNil();
        public R visitCons(T value, List<T> sublist);
    }
}

final class Nil<T> implements List<T> {
    public Nil() { }

    public <R> R accept(Visitor<T,R> visitor) {
        return visitor.visitNil();
    }
}
final class Cons<T> implements List<T> {
    public final T value;
    public final List<T> sublist;

    public Cons(T value, List<T> sublist) {
        this.value = value;
        this.sublist = sublist;
    }

    public <R> R accept(Visitor<T,R> visitor) {
        return visitor.visitCons(value, sublist);
    }
}

Запечатывание достигается Visitorклассом. Каждый из его методов объявляет, как деконструировать один из подклассов. Вы могли бы добавить больше подклассов, но это должно было бы быть реализовано acceptи путем вызова одного из visit...методов, так что он должен был бы вести себя как Consили как Nil.

Если вы злоупотребляете именованными параметрами C # (введено в C # 4.0), вы можете создавать алгебраические типы данных, которые легко сопоставить:

Either<string, string> e = MonthName(2);

// Match with no return value.
e.Match
(
    Left: err => { Console.WriteLine("Could not convert month: {0}", err); },
    Right: name => { Console.WriteLine("The month is {0}", name); }
);

// Match with a return value.
string monthName =
    e.Match
    (
        Left: err => null,
        Right: name => name
    );
Console.WriteLine("monthName: {0}", monthName);

Вот реализация Eitherкласса:

public abstract class Either<L, R>
{
    // Subclass implementation calls the appropriate continuation.
    public abstract T Match<T>(Func<L, T> Left, Func<R, T> Right);

    // Convenience wrapper for when the caller doesn't want to return a value
    // from the match expression.
    public void Match(Action<L> Left, Action<R> Right)
    {
        this.Match<int>(
            Left: x => { Left(x); return 0; },
            Right: x => { Right(x); return 0; }
        );
    }
}

public class Left<L, R> : Either<L, R>
{
    L Value {get; set;}

    public Left(L Value)
    {
        this.Value = Value;
    }

    public override T Match<T>(Func<L, T> Left, Func<R, T> Right)
    {
        return Left(Value);
    }
}

public class Right<L, R> : Either<L, R>
{
    R Value { get; set; }

    public Right(R Value)
    {
        this.Value = Value;
    }

    public override T Match<T>(Func<L, T> Left, Func<R, T> Right)
    {
        return Right(Value);
    }
}

В C # этот Emptyтип не может быть , потому что из-за reification базовые типы различаются для разных типов элементов. Вы можете только иметь Empty<T>; не так полезно

В Java это может произойти Empty : ConsListиз-за стирания типа, но я не уверен, что средство проверки типов не будет кричать где-нибудь.

Тем не менее, поскольку оба языка имеют null, вы можете думать о всех их ссылочных типах как о «Безотносительно | Нуль». Таким образом, вы просто использовали бы nullкак «Пустой», чтобы не указывать, что он получает.

Единственное, что необходимо помимо наивного подкласса - это способ запечатать классы, то есть способ сделать невозможным добавление подклассов в иерархию.

В Java вы не можете. Но вы можете объявить базовый класс как частный пакет, что означает, что все прямые подклассы должны принадлежать тому же пакету, что и базовый класс. Если вы затем объявите подклассы как окончательные, они не могут быть разделены на подклассы.

Я не знаю, решит ли это вашу настоящую проблему, хотя ...

Тип данных ConsList<A>может быть представлен как интерфейс. Интерфейс предоставляет единственный deconstructметод, который позволяет вам «деконструировать» значение этого типа, то есть обрабатывать каждый из возможных конструкторов. Вызов deconstructметода аналогичен case ofформе в Haskell или ML.

interface ConsList<A> {
  <R> R deconstruct(
    Function<Unit, R> emptyCase,
    Function<Pair<A,ConsList<A>>, R> consCase
  );
}

deconstructМетод принимает функцию «обратного вызова» для каждого конструктора в ADT. В нашем случае, она принимает функцию для случая пустого списка и другую функцию для случая "cons-ячейки".

Каждая функция обратного вызова принимает в качестве аргументов значения, которые принимаются конструктором. Таким образом, случай «пустой список» не принимает аргументов, а случай «cons cell» принимает два аргумента: заголовок и конец списка.

Мы можем закодировать эти «множественные аргументы», используя Tupleклассы или используя карри. В этом примере я решил использовать простой Pairкласс.

Интерфейс реализован один раз для каждого конструктора. Во-первых, у нас есть реализация для «пустого списка». deconstructРеализация просто вызывает emptyCaseфункцию обратного вызова.

class ConsListEmpty<A> implements ConsList<A> {
  public ConsListEmpty() {}

  public <R> R deconstruct(
    Function<Unit, R> emptyCase,
    Function<Pair<A,ConsList<A>>, R> consCase
  ) {
    return emptyCase.apply(new Unit());
  }
}

Затем мы реализуем случай «cons клетка» аналогично. На этот раз у класса есть свойства: голова и хвост непустого списка. В deconstructреализации эти свойства передаются в consCaseфункцию обратного вызова.

class ConsListConsCell<A> implements ConsList<A> {
  private A head;
  private ConsList<A> tail;

  public ConsListCons(A head, ConsList<A> tail) {
    this.head = head;
    this.tail = tail;
  }

  public <R> R deconstruct(
    Function<Unit, R> emptyCase,
    Function<Pair<A,ConsList<A>>, R> consCase
  ) {
    return consCase.apply(new Pair<A,ConsList<A>>(this.head, this.tail));
  }
}

Вот пример использования этой кодировки ADT: мы можем написать reduceфункцию, которая является обычным сворачиванием списков.

<T> T reduce(Function<Pair<T,A>,T> reducer, T initial, ConsList<T> l) {
  return l.deconstruct(
    ((unit) -> initial),
    ((t) -> reduce(reducer, reducer.apply(initial, t.v1), t.v2))
  );
}

Это аналогично этой реализации в Haskell:

reduce reducer initial l = case l of
  Empty -> initial
  Cons t_v1 t_v2  -> reduce reducer (reducer initial t_v1) t_v2

Единственное, что необходимо помимо наивного подкласса - это способ запечатать классы, то есть способ сделать невозможным добавление подклассов в иерархию.

Как бы вы подошли к этой проблеме на языке, таком как C # или Java?

Нет хорошего способа сделать это, но если вы хотите жить с отвратительным взломом, вы можете добавить некоторую явную проверку типов в конструктор абстрактного базового класса. В Java это было бы что-то вроде

protected ConsList() {
    Class<?> clazz = getClass();
    if (clazz != Empty.class && clazz != ConsCell.class) throw new Exception();
}

В C # это более сложно из-за усовершенствованных обобщений - самый простой подход может состоять в том, чтобы преобразовать тип в строку и исправить это.

Обратите внимание, что в Java даже этот механизм теоретически может быть обойден кем-то, кто действительно хочет через модель сериализации или sun.misc.Unsafe.