Dlaczego potrzebujemy "algebraicznych typów danych"?

Question

Czytałem niektóre wyjaśnienia rodzajów algebraiczne danych:

• The Algebra of Algebraic Data types I
• The Algebra of Algebraic Data types II
• The Algebra of Algebraic Data types III
• The Algebra of Data, and Calculus of Mutation

Te artykuły dają bardzo szczegółowy opis i kod próbek.

Początkowo myślałem, że Algebraic Data Type służy do łatwego definiowania niektórych typów i możemy je dopasować do dopasowania wzorców. Ale po przeczytaniu tych artykułów okazało się, że "dopasowanie do wzorca" nawet tam nie jest wymieniane, a zawartość wygląda interesująco, ale o wiele bardziej złożona, niż się spodziewałem.

Więc mam kilka pytań (które odpowiedzi nie ma w tych artykułach):

• Dlaczego potrzebujemy go, powiedzmy, w Haskell lub Scala?
• Co możemy zrobić, jeśli ją mamy i czego nie możemy zrobić, jeśli jej nie mamy?

Answer 1

Powinniśmy zacząć od wiki artykule Haskell Algebraic Data Types

i tu, na krótko, tylko moją wizję:

• musimy je modelować logikę biznesową w starym obiektowego sposób (a właściwie w sposób oparty na starych kategoriach) i sprawić, że będzie on bardziej odporny na uszkodzenia, ponieważ kompilator może sprawdzić, czy dopasował wszystkie możliwe opcje. Lub, innymi słowy, że twoja funkcja to total, a nie częściowa. Ostatecznie daje kompilatorowi możliwość sprawdzenia poprawności kodu (dlatego zalecane są zapieczętowane cechy). Tak więc, im więcej typów masz, tym lepiej - ogólne programowanie pomaga ci tutaj, ponieważ produkuje więcej typów.
• cechy standardowe: możemy przedstawić typ jako "zestaw" obiektów, możemy dopasować obiekt do typu (używając dopasowywania wzorca), a nawet zdekonstruować (przeanalizować) go za pomocą dopasowań. Możemy również dynamicznie dodawać zachowania (w czasie kompilacji) do tego typu z klasami typów. Jest to również możliwe dla zwykłej klasy, ale tutaj daje nam możliwość oddzielenia algebraicznego modelu (typy) od zachowania (funkcje)
• możemy konstruować typy jako products/coproducts różnych obiektów/typów. Możesz myśleć o systemie algebraicznym jako zestawie (lub bardziej ogólnie - jako kategorii zamkniętej kartezjańsko). type Boolean = True | False oznacza, że ​​Boolean jest związkiem (współproduktem) z True i False. Cat(height: Height, weight: Weight) to "krotka" (ogólniej - produkt) z Height i Weight. Produkt (mniej więcej) reprezentuje relację "części" z OOP, coproduct - "is" (ale w odwrotny sposób).

To również daje nam sposób wysłać powierzony zachowania w czasie wykonywania w multimethod stylu (jak to było w CLOS):

sealed trait Animal 
    case class Cat extends Animal 
    case class Dog extends Animal 

def move(c: Animal) = c match { 
    case Cat(...) => ... 
    case Dog(...) => 
    case a: Animal => ...//if you need default implementation 
} 

Haskell, takich jak:

data Animal = Dog | Cat //coproduct 

let move Dog d = ... 
let move Cat c = ... 

Zamiast:

trait Animal { 
    ... 
    def move = ... 
} 

class Cat(val ...) extends Animal { 
    override def move = ... 
} 

class Dog(val ...) extends Animal { 
    override def move = ... 
} 

PS Teoretycznie, jeśli modelujesz świat w sposób algebraiczny, a twoje funkcje są kompletne i czyste - możesz udowodnić, że twoja aplikacja jest poprawna. Jeśli się kompiluje - działa :).

P.S.2. Powinienem też wspomnieć, że hierarchia typu Scala, która ma Any, nie jest tak dobra dla typesafety (ale dobra dla współpracy z Javą i IO), ponieważ łamie ładną strukturę zdefiniowaną przez GADTs. Więcej niż to case class może być zarówno GADT (algebraiczne) i ADT (streszczenie), a także zmniejsza gwarancje.

Answer 2

Wpis na blogu, o którym wspomniałeś, dotyczy bardziej matematycznych aspektów typów danych algebraicznych, dotyczących ich praktycznego zastosowania w programowaniu. Myślę, że większość funkcjonalnych programistów nauczyła się najpierw o typach danych algebraicznych, używając ich w pewnym języku programowania, a dopiero później badała ich właściwości algebraiczne.

Rzeczywiście, intencją blogu jest jasne od samego początku:

w tej serii postów Wytłumaczę dlaczego typy danych Haskell są nazwie algebraicznych - bez wymieniania teorii kategorii lub zaawansowanych matematyka.

W każdym razie praktyczna użyteczność typów algebraicznych jest najlepiej doceniana podczas zabawy z nimi.

Załóżmy na przykład, że chcesz napisać funkcję przecinającą dwa segmenty na płaszczyźnie.

def intersect(s1: Segment, s2: Segment): ??? 

Jaki powinien być wynik? To kuszące, aby napisać:

def intersect(s1: Segment, s2: Segment): Point 

, ale co, jeśli nie ma skrzyżowania? Można próbować załatać tę skrzynkę narożną zwracając null lub rzucając wyjątek NoIntersection. Jednak dwa segmenty mogą również nakładać się na więcej niż jeden punkt, gdy leżą na tej samej linii prostej. Co powinniśmy robić w takich przypadkach? Zgłaszanie innego wyjątku?

Podejście algebraiczne typy jest zaprojektowanie rodzaj obejmujący wszystkie przypadki:

sealed trait Intersection 
case object NoIntersection extends Intersection 
case class SinglePoint(p: Point) extends Intersection 
case class SegmentPortion(s: Segment) extends Intersection 

def intersect(s1: Segment, s2: Segment): Intersection 

Istnieje wiele praktycznych przypadków, gdy takie podejście czuje się zupełnie naturalne. W niektórych innych językach bez typów algebraicznych należy odwoływać się do wyjątków, do null s (zobacz także the billion-dollar mistake), do klas niezamkniętych (uniemożliwiając kompilatorowi sprawdzenie kompletności dopasowywania wzorca) lub do innych funkcji przez język. Prawdopodobnie "najlepszą" opcją w OOP jest użycie Visitor pattern do kodowania typów algebraicznych i dopasowywania wzorców w językach, które nie mają takich funkcji.Mimo to posiadanie tego bezpośrednio wspieranego w języku, tak jak w scala, jest znacznie wygodniejsze.