Jak kodujesz algebraiczne typy danych w języku C # - lub języku podobnym do Java?

Istnieją pewne problemy, które można łatwo rozwiązać za pomocą Algebraicznych typów danych, na przykład typ listy można bardzo zwięźle wyrazić jako:

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

Ten konkretny przykład jest w języku Haskell, ale byłby podobny w innych językach z natywną obsługą algebraicznych typów danych.

Okazuje się, że istnieje oczywiste odwzorowanie na podtypy w stylu OO: typ danych staje się abstrakcyjną klasą bazową, a każdy konstruktor danych staje się konkretną podklasą. Oto przykład w Scali:

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+)

Jedyną rzeczą potrzebną poza naiwną podklasą jest sposób uszczelniania klas, tj. Sposób uniemożliwiający dodanie podklas do hierarchii.

Jak podchodziłbyś do tego problemu w języku takim jak C # lub Java? Dwa potknięcia, które znalazłem podczas próby użycia Algebraicznych Typów Danych w C # to:

• Nie mogłem dowiedzieć się, jak nazywa się typ dna w C # (tzn. Nie mogłem dowiedzieć się, w co należy włożyć class Empty : ConsList< ??? >)
• Nie mogłem wymyślić sposobu uszczelnienia ConsList , aby nie można było dodawać żadnych podklas do hierarchii

Jaki byłby najbardziej idiomatyczny sposób implementacji Algebraicznych typów danych w C # i / lub Javie? Lub, jeśli nie jest to możliwe, jaki byłby idiomatyczny zamiennik?

Istnieje prosty, ale prosty sposób na uszczelnianie klas w Javie. Umieszczasz prywatnego konstruktora w klasie bazowej, a następnie tworzysz z niego podklasy klasy wewnętrzne.

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;
      }
   }
}

Przypnij wzór gościa do wysyłki.

Mój projekt jADT: Java Algebraic DataTypes generuje dla Ciebie całą tę podstawkę https://github.com/JamesIry/jADT

Możesz to osiągnąć za pomocą wzorca odwiedzającego , który uzupełni dopasowanie wzorca. Na przykład

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

może być napisany w Javie jako

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);
    }
}

VisitorKlasa jest uszczelniona . Każda z jego metod deklaruje sposób zdekonstruowania jednej z podklas. Możesz dodać więcej podklas, ale musiałoby się to zaimplementować accepti wywołać jedną z visit...metod, więc albo musiałoby się zachowywać tak jak Conslub tak Nil.

Jeśli nadużyjesz parametrów o nazwie C # (wprowadzonych w C # 4.0), możesz tworzyć algebraiczne typy danych, które można łatwo dopasować:

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);

Oto implementacja Eitherklasy:

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);
    }
}

W języku C # nie możesz mieć tego Emptytypu, ponieważ z powodu weryfikacji typy podstawowe są różne dla różnych typów członków. Możesz tylko mieć Empty<T>; nie takie użyteczne.

W Javie możesz to zrobić z Empty : ConsListpowodu skasowania typu, ale nie jestem pewien, czy sprawdzanie typów gdzieś nie krzyczy.

Ponieważ jednak oba języki mają null, możesz traktować wszystkie ich typy referencyjne jako „Cokolwiek | Null”. Więc użyjesz go nulljako „Pustego”, aby uniknąć konieczności określania, co wyprowadza.

Jedyną rzeczą potrzebną poza naiwną podklasą jest sposób uszczelniania klas, tj. Sposób uniemożliwiający dodanie podklas do hierarchii.

W Javie nie możesz. Ale możesz zadeklarować klasę podstawową jako pakiet prywatny, co oznacza, że ​​wszystkie bezpośrednie podklasy muszą należeć do tego samego pakietu co klasa podstawowa. Jeśli następnie zadeklarujesz podklasy jako ostateczne, nie będzie można ich dalej klasyfikować.

Nie wiem, czy to rozwiązałoby twój prawdziwy problem ...

Typ danych ConsList<A>może być reprezentowany jako interfejs. Interfejs udostępnia pojedynczą deconstructmetodę, która pozwala „zdekonstruować” wartość tego typu - to znaczy obsługi każdego z możliwych konstruktorów. Wywołania deconstructmetody są analogiczne do case offormularza w Haskell lub ML.

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

deconstructMetoda wykonuje funkcję „zwrotnej” dla każdego konstruktora w ADT. W naszym przypadku przyjmuje ona funkcję dla pustej wielkości listy i inną funkcję w przypadku „komórki przeciwnej”.

Każda funkcja zwrotna przyjmuje jako argumenty wartości, które są akceptowane przez konstruktor. Tak więc przypadek „pustej listy” nie przyjmuje argumentów, ale przypadek „komórki przeciw” przyjmuje dwa argumenty: nagłówek i ogon listy.

Możemy zakodować te „liczne argumenty” za pomocą Tupleklas lub curry. W tym przykładzie wybrałem prostą Pairklasę.

Interfejs jest implementowany raz dla każdego konstruktora. Po pierwsze, mamy implementację „pustej listy”. deconstructRealizacja po prostu wywołuje emptyCasefunkcję zwrotną.

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());
  }
}

Następnie podobnie wdrażamy przypadek „komórki przeciwnej”. Tym razem klasa ma właściwości: głowę i ogon niepustej listy. W deconstructimplementacji te właściwości są przekazywane do consCasefunkcji zwrotnej.

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));
  }
}

Oto przykład użycia tego kodowania ADT: możemy napisać reducefunkcję, która jest zwykle składaną listą.

<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))
  );
}

Jest to analogiczne do tej implementacji w Haskell:

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

Jedyną rzeczą potrzebną poza naiwną podklasą jest sposób uszczelniania klas, tj. Sposób uniemożliwiający dodanie podklas do hierarchii.

Jak podchodziłbyś do tego problemu w języku takim jak C # lub Java?

Nie ma na to dobrego sposobu, ale jeśli chcesz żyć z ohydnym hakiem, możesz dodać wyraźne sprawdzanie typu do konstruktora abstrakcyjnej klasy bazowej. W Javie byłoby to coś takiego

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

W języku C # jest to bardziej skomplikowane ze względu na zmienione generyczne - najprostszym podejściem może być przekonwertowanie typu na ciąg i przekształcenie go w magię.

Zauważ, że w Javie nawet ten mechanizm może teoretycznie zostać ominięty przez kogoś, kto naprawdę chce to za pomocą modelu serializacji lub sun.misc.Unsafe.