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?
Odpowiedzi:
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.
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
źródło
Either
. Zobacz moje pytanieMożesz to osiągnąć za pomocą wzorca odwiedzającego , który uzupełni dopasowanie wzorca. Na przykład
może być napisany w Javie jako
Visitor
Klasa 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ćaccept
i wywołać jedną zvisit...
metod, więc albo musiałoby się zachowywać tak jakCons
lub takNil
.źródło
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ć:
Oto implementacja
Either
klasy:źródło
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.W języku C # nie możesz mieć tego
Empty
typu, 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 : ConsList
powodu 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 gonull
jako „Pustego”, aby uniknąć konieczności określania, co wyprowadza.źródło
null
polega 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 asocjacyjne1 :: 2 :: 3 :: Empty
), ale nie mogę powiedziećnull.prepend …
.Empty
iEmpty<>
i nadużyć operatorów konwersji niejawnych w celu umożliwienia dość praktycznych symulacji, jeśli chcesz. Zasadniczo używaszEmpty
w kodzie, ale wszystkie podpisy typów itp. Używają tylko wariantów ogólnych.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 ...
źródło
intanceof
kontrole 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.Typ danych
ConsList<A>
może być reprezentowany jako interfejs. Interfejs udostępnia pojedyncządeconstruct
metodę, która pozwala „zdekonstruować” wartość tego typu - to znaczy obsługi każdego z możliwych konstruktorów. Wywołaniadeconstruct
metody są analogiczne docase of
formularza w Haskell lub ML.deconstruct
Metoda 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ą
Tuple
klas lub curry. W tym przykładzie wybrałem prostąPair
klasę.Interfejs jest implementowany raz dla każdego konstruktora. Po pierwsze, mamy implementację „pustej listy”.
deconstruct
Realizacja po prostu wywołujeemptyCase
funkcję zwrotną.Następnie podobnie wdrażamy przypadek „komórki przeciwnej”. Tym razem klasa ma właściwości: głowę i ogon niepustej listy. W
deconstruct
implementacji te właściwości są przekazywane doconsCase
funkcji zwrotnej.Oto przykład użycia tego kodowania ADT: możemy napisać
reduce
funkcję, która jest zwykle składaną listą.Jest to analogiczne do tej implementacji w Haskell:
źródło
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
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
.źródło
Type type = this.GetType(); if (type != typeof(Empty<T>) && type != typeof(ConsCell<T>)) throw new Exception();