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

58

Есть некоторые проблемы, которые легко решаются алгебраическими типами данных, например, тип 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? Или, если это невозможно, какой будет идиоматическая замена?

Йорг Миттаг
источник
3
C # является языком ООП. Решать проблемы с помощью ООП. Не пытайтесь использовать любую другую парадигму.
Эйфорическая
7
@Euphoric C # стал достаточно удобным функциональным языком с C # 3.0. Первоклассные функции, встроенные общие функциональные операции, монады.
Маурисио Шеффер
2
@Euphoric: некоторые домены легко моделировать с помощью объектов и трудно моделировать с алгебраическими типами данных, а некоторые - наоборот. Знание того, как сделать оба, дает вам больше гибкости в моделировании вашего домена. И, как я уже сказал, отображение алгебраических типов данных на типичные концепции ОО не так сложно: тип данных становится абстрактным базовым классом (или интерфейсом, или абстрактной чертой), конструкторы данных становятся конкретными подклассами реализации. Это дает вам открытый алгебраический тип данных. Ограничения на наследование дают вам замкнутый алгебраический тип данных. Полиморфизм дает вам случайную дискриминацию.
Йорг Миттаг
3
@ Эйфория, парадигма, шмарадигм, кого это волнует? ADT ортогональны к функциональному программированию (или ООП или что-то еще). Кодирование AST любого языка является довольно сложной задачей без поддержки приличных ADT, а компиляция этого языка является проблемой без другой независимой от парадигмы функции - сопоставления с образцом.
SK-logic

Ответы:

42

Существует простой, но сложный способ герметизации классов в 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

Джеймс Ири
источник
2
Почему-то я не удивлен, увидев ваше имя всплывающее здесь! Спасибо, я не знал эту идиому.
Йорг Миттаг
4
Когда вы сказали «тяжелый шаблон», я был готов к чему-то гораздо худшему ;-) Java иногда может быть довольно плохим с шаблонным шаблоном.
Йоахим Зауэр
но это не значит: у вас нет способа специализировать тип A без необходимости утверждать его с помощью актерского состава (я думаю)
nicolas
Это, к сожалению, кажется неспособным представить некоторые более сложные типы сумм, например Either. Смотрите мой вопрос
Зои Хьюлл
20

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

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.

Петр Пудлак
источник
13

Если вы злоупотребляете именованными параметрами 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);
    }
}
Джои Адамс
источник
Я уже видел версию этой техники на Java, но лямбда-выражения и именованные параметры делают ее настолько удобочитаемой. +1!
Довал
1
Я думаю, что проблема здесь в том, что право не является общим по типу ошибки. Что-то вроде:, class Right<R> : Either<Bot,R>где Either изменен на интерфейс с ковариантными (out) параметрами типа, а Bot является нижним типом (подтип любого другого типа, противоположный Object). Я не думаю, что C # имеет нижний тип.
Кройд
5

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

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

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

Ян Худек
источник
Проблема в nullтом, что он слишком общий: он представляет отсутствие чего-либо , то есть пустоту вообще, но я хочу представить отсутствие элементов списка, то есть, в частности, пустой список. Пустой список и пустое дерево должны иметь разные типы. Кроме того, пустой список должен быть фактическим значением, потому что он все еще имеет свое собственное поведение, поэтому он должен иметь свои собственные методы. Чтобы построить список [1, 2, 3], я хочу сказать Empty.prepend(3).prepend(2).prepend(1)(или на языке с правоассоциативными операторами 1 :: 2 :: 3 :: Empty), но я не могу сказать null.prepend ….
Йорг Миттаг,
@ JörgWMittag: Нули имеют разные типы. Вы также можете легко создать типизированную константу со значением null для этой цели. Но это правда, что вы не можете вызывать методы для этого. В любом случае ваш подход к методам не работает без пустого элемента, зависящего от типа элемента.
Ян Худек
некоторые хитроумные методы расширения могут подделывать вызовы метода для нулей (конечно, все они действительно статичны)
jk.
Вы можете использовать операторы неявного преобразования Emptyand и an, Empty<>чтобы разрешить довольно практичное моделирование, если хотите. По сути, вы используете Emptyв коде, но все сигнатуры типов и т. Д. Используют только общие варианты.
Имон Нербонн
3

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

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

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

Стивен С
источник
У меня нет реальной проблемы, иначе я бы опубликовал это в StackOverflow, а не здесь :-) Важное свойство алгебраических типов данных заключается в том, что они могут быть закрыты , что означает, что число случаев фиксировано: в этом примере , список либо пуст, либо нет. Если я могу статически гарантировать, что это так, то я могу сделать динамическое приведение или динамическую intanceofпроверку «псевдобезопасного типа» (то есть: я знаю, что это безопасно, даже если компилятор этого не делает), просто гарантируя, что я всегда проверьте эти два случая. Однако, если кто-то еще добавляет новый подкласс, тогда я могу получить ошибки времени выполнения, которых я не ожидал.
Йорг Миттаг
@ JörgWMittag - Ну, Java явно не поддерживает это ... в том сильном смысле, о котором вы, похоже, мечтали. Конечно, вы можете делать разные вещи, чтобы блокировать нежелательный подтип во время выполнения, но затем вы получаете «ошибки времени выполнения, которые вы не ожидаете».
Стивен С.
3

Тип данных 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
jameshfisher
источник
Интересный подход, очень приятно! Я вижу связь с F # Active Patterns и Scala Extractor (и там, вероятно, есть также ссылка на Haskell Views, о которой я, к сожалению, ничего не знаю). Я не думал о переносе ответственности за сопоставление с образцом над конструкторами данных в сам экземпляр ADT.
Йорг Миттаг
2

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

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

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

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

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

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

Питер Тейлор
источник
1
Это не будет сложнее в C #:Type type = this.GetType(); if (type != typeof(Empty<T>) && type != typeof(ConsCell<T>)) throw new Exception();
svick
@svick, хорошо заметили. Я не принимал во внимание, что базовый тип будет параметризован.
Питер Тейлор
Brilliant! Я полагаю, что этого достаточно для «ручной статической проверки типов». Я больше стараюсь устранить честные ошибки программирования, а не злонамеренные намерения.
Йорг W Mittag