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

58

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?

Jörg W Mittag
źródło
3
C # to język OOP. Rozwiązuj problemy za pomocą OOP. Nie próbuj używać żadnego innego paradygmatu.
Euforia
7
@Euphoric C # stał się całkiem użytecznym językiem funkcjonalnym z C # 3.0. Funkcje pierwszej klasy, wbudowane wspólne operacje funkcjonalne, monady.
Mauricio Scheffer,
2
@Euphoric: niektóre domeny są łatwe do modelowania za pomocą obiektów, a trudne do modelowania za pomocą algebraicznych typów danych, niektóre są przeciwne. Wiedza o tym, jak to zrobić, daje większą elastyczność w modelowaniu domeny. I jak powiedziałem, mapowanie algebraicznych typów danych na typowe koncepcje OO nie jest tak skomplikowane: typ danych staje się abstrakcyjną klasą bazową (lub interfejsem lub cechą abstrakcyjną), konstruktory danych stają się konkretnymi podklasami implementacji. To daje ci otwarty typ danych algebraicznych. Ograniczenia dziedziczenia dają ci zamknięty typ danych algebraicznych. Polimorfizm zapewnia dyskryminację przypadków.
Jörg W Mittag,
3
@Euforia, paradygmat, schmaradigm, kogo to obchodzi? ADT są ortogonalne do programowania funkcjonalnego (lub OOP lub cokolwiek innego). Kodowanie AST dowolnego języka jest dość uciążliwe bez przyzwoitej obsługi ADT, a kompilacja tego języka jest uciążliwa bez innej cechy niezależnej od paradygmatu, dopasowania wzorca.
SK-logic

Odpowiedzi:

42

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

James Iry
źródło
2
Jakoś nie jestem zaskoczony widząc twoje imię tutaj wyskakujące! Dzięki, nie znałem tego idiomu.
Jörg W Mittag
4
Kiedy powiedziałeś „bojler ciężki”, byłem przygotowany na coś znacznie gorszego ;-) Czasami Java może być bardzo zła z bojlerem.
Joachim Sauer
ale to nie komponuje: nie ma sposobu na specjalizację typu A bez konieczności zapewniania go przez obsadę (chyba)
nicolas
Niestety nie wydaje się to reprezentować bardziej złożonych typów sum, np Either. Zobacz moje pytanie
Zoey Hewll
20

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.

Petr Pudlák
źródło
13

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);
    }
}
Joey Adams
źródło
Wcześniej widziałem wersję tej techniki Java, ale lambdas i nazwane parametry sprawiają, że jest ona bardzo czytelna. +1!
Doval
1
Myślę, że problem polega na tym, że Right nie jest ogólny w stosunku do rodzaju błędu. Coś w stylu: class Right<R> : Either<Bot,R>gdzie albo zmieniono na interfejs z parametrami typu kowariantnego (wyjściowego), a Bot jest typem dolnym (podtypem każdego innego typu, przeciwnego do Object). Nie sądzę, że C # ma typ dolny.
croyd
5

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.

Jan Hudec
źródło
Problem nullpolega na tym, że jest on zbyt ogólny: reprezentuje brak czegokolwiek , tj. Pustkę w ogóle, ale chcę reprezentować brak elementów listy, tj. W szczególności pustej listy. Pusta lista i puste drzewo powinny mieć różne typy. Ponadto pusta lista musi być wartością rzeczywistą, ponieważ nadal ma własne zachowanie, więc musi mieć własne metody. Aby skonstruować listę [1, 2, 3], chcę powiedzieć Empty.prepend(3).prepend(2).prepend(1)(lub w języku zawierającym operatory asocjacyjne 1 :: 2 :: 3 :: Empty), ale nie mogę powiedzieć null.prepend ….
Jörg W Mittag,
@ JörgWMittag: Wartości null mają różne typy. W tym celu można również łatwo utworzyć stałą maszynową o wartości null. Ale to prawda, że ​​nie można wywoływać metod w tym zakresie. Twoje podejście z metodami i tak nie działa bez specyficznego dla elementu typu Pustego.
Jan Hudec,
niektóre sprytne metody rozszerzenia mogą sfałszować wywołania „metody” na wartości zerowe (oczywiście wszystko jest naprawdę statyczne)
jk.
Można mieć Emptyi Empty<>i nadużyć operatorów konwersji niejawnych w celu umożliwienia dość praktycznych symulacji, jeśli chcesz. Zasadniczo używasz Emptyw kodzie, ale wszystkie podpisy typów itp. Używają tylko wariantów ogólnych.
Eamon Nerbonne
3

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 ...

Stephen C.
źródło
Nie mam prawdziwego problemu, lub opublikowałbym to na StackOverflow, nie tutaj :-) Ważną właściwością Algebraicznych typów danych jest to, że można je zamknąć , co oznacza, że ​​liczba przypadków jest stała: w tym przykładzie , lista jest pusta lub nie jest. Jeśli mogę statycznie upewnić się, że tak jest, to mogę wykonać rzutowania dynamiczne lub intanceofkontrole dynamiczne „bezpieczne dla pseudo-typu” (tj .: wiem, że jest to bezpieczne, nawet jeśli kompilator tego nie robi), po prostu zapewniając, że zawsze sprawdź te dwa przypadki. Jeśli jednak ktoś doda nową podklasę, mogę uzyskać błędy czasu wykonywania, których się nie spodziewałem.
Jörg W Mittag,
@ JörgWMittag - Cóż, Java wyraźnie nie obsługuje tego ... w silnym sensie, że wydaje się, że chcesz. Oczywiście możesz robić różne rzeczy, aby zablokować niechciane subtyping w czasie wykonywania, ale wtedy otrzymujesz „błędy wykonania, których się nie spodziewasz”.
Stephen C
3

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
jameshfisher
źródło
Ciekawe podejście, bardzo fajnie! Widzę połączenie z aktywnymi wzorcami F # i ekstraktorami Scala (i prawdopodobnie jest tam również link do widoków Haskell, o których niestety nie wiem nic). Nie myślałem o przeniesieniu odpowiedzialności za dopasowanie wzorca nad konstruktorami danych do samej instancji ADT.
Jörg W Mittag
2

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.

Peter Taylor
źródło
1
Nie byłoby bardziej skomplikowane w C #:Type type = this.GetType(); if (type != typeof(Empty<T>) && type != typeof(ConsCell<T>)) throw new Exception();
svick
@svick, dobrze obserwowane. Nie brałem pod uwagę, że typ bazy zostanie sparametryzowany.
Peter Taylor,
Znakomity! Sądzę, że jest to wystarczające do „ręcznego sprawdzania statycznego typu”. Bardziej chcę wyeliminować błędy w programowaniu niż złośliwe zamiary.
Jörg W Mittag,