Jakie są zastosowania algebraicznych typów danych?

Czytam o Algebraicznych Typach Danych (dzięki Richardowi Minerichowi znalazłem to doskonałe wyjaśnienie pojęcia). Chociaż myślę, że rozumiem pojęcie rodzajów sum i typów produktów itp., Nie do końca rozumiem, w jaki sposób Algebraiczne typy danych są przydatne poza określaniem dopasowania wzorca. Co jeszcze można zrobić z ADT poza dopasowaniem wzorca?

EDYCJA: Nie pytam, co programista może zrobić z ADT, czego nie można zrobić z obiektami. Pytam, czy są inne operacje, na które pozwalają ADT; na przykład, czy można zrobić dodatkowe uzasadnienie dotyczące typów zaangażowanych, jeśli zastosowane są ADT? Czy narzędzia ADT ułatwiają analizę typów, która bez nich nie byłaby możliwa?

functional-programming data-types

— Onorio Catenacci
źródło

Co możesz zrobić z obiektami oprócz metod wywoływania?

ADT faktycznie odnosi się do „abstrakcyjnego typu danych”, a nie algebraicznych typów danych.

— Rein Henrichs

@ Rein: Może odnosić się do jednego lub drugiego w zależności od kontekstu.

— sepp2k

@ Rein: Rzeczywiście (co wydaje mi się dość zaskakujące, jeśli mam być szczery): Jednak artykuł w Wikipedii dla ADT wymienia zarówno Typ danych abstrakcyjnych, jak i Typ danych algebraicznych jako możliwe znaczenia. A ADT jest bardzo często używany jako skrót dla algebraicznych typów danych na przykład na liście mailingowej Haskell i kanale IRC.

— sepp2k

@Rein, wiem - właśnie zmęczyło mnie pisanie „Algebraic Data Type” w kółko i pomyślałem, że ludzie będą w stanie zrozumieć, o czym mówię, biorąc pod uwagę kontekst.

— Onorio Catenacci

Odpowiedzi:

Algebraiczne typy danych różnią się tym, że można je zbudować z kilku rodzajów „rzeczy”. Na przykład Drzewo może nie zawierać niczego (Puste), Liścia lub Węzła.

data Tree = Empty
          | Leaf Int
          | Node Tree Tree

Ponieważ Węzeł składa się z dwóch Drzew, algebraiczne typy danych mogą być rekurencyjne.

Dopasowanie wzorca pozwala na dekonstruację typów danych algebraicznych w sposób zapewniający bezpieczeństwo typu. Rozważ następującą implementację głębokości i jej ekwiwalentu pseudokodu:

depth :: Tree -> Int
depth Empty = 0
depth (Leaf n) = 1
depth (Node l r) = 1 + max (depth l) (depth r)

w porównaniu do:

switch on (data.constructor)
  case Empty:
    return 0
  case Leaf:
    return 1
  case Node:
    let l = data.field1
    let r = data.field2
    return 1 + max (depth l) (depth r)

Ma to tę wadę, że programiści muszą pamiętać o opróżnieniu przed Leaf, aby pole1 nie było dostępne w pustym drzewie. Podobnie sprawa Liścia musi zostać zadeklarowana przed sprawą Węzła, aby pole 2 nie było dostępne w Liściu. W związku z tym język nie zapewnia bezpieczeństwa typu, ale raczej nakłada dodatkowe obciążenie poznawcze na programistę. Nawiasem mówiąc, pobieram te przykłady bezpośrednio ze stron wikipedii.

Oczywiście język kaczątkowy mógłby zrobić coś takiego:

class Empty
  def depth
    0
  end
end

class Leaf
  def depth
    1
  end
end

class Node
  attr_accessor :field1, :field2

  def depth
    1 + [field1.depth, field2.depth].max
  end
end

Algebraiczne typy danych mogą nie być ściśle lepsze niż ich odpowiedniki OOP, ale zapewniają inny zestaw napięć do pracy przy tworzeniu oprogramowania.

— Rein Henrichs
źródło

Nie jestem pewien, czy to wyjaśnienie jest tak doskonałe.

Algebraiczne typy danych są używane do tworzenia struktur danych, takich jak listy i drzewa.

Na przykład drzewa analizy są łatwo reprezentowane przez algebraiczne struktury danych.

data BinOperator = Add
                 | Subtr
                 | Div
                 | Mult
                 | Mod
                 | Eq
                 | NotEq
                 | GreaterThan
                 | LogicAnd
                 | LogicOr
                 | BitAnd
                 | BitOr
                 | ...

data UnOperator = Negate
                | Not
                | Increment
                | Decrement
                | Complement
                | Ref
                | DeRef


data Expression = Empty
                | IntConst Int
                | FloatConst Float
                | StringConst String
                | Ident String
                | BinOp BinOperator Expression Expression
                | UnOp UnOperator Expression Bool //prefix or not
                | If Expression Expression Expression
                | While Expression Expression Bool //while vs. do while
                | Block List<Expression>
                | Call Expression List<Expression>
                | ...

Reprezentacja języka C. nie wymagałaby aż tak dużo więcej.

Ale tak naprawdę możesz zrobić WSZYSTKO z algebraicznymi typami danych. Lisp udowadnia, że możesz zrobić wszystko za pomocą par, a narzędzia ADT po prostu zapewniają bardziej szczegółowy i bezpieczny sposób na to podejście.

Oczywiście, jeśli zapytasz: „Co możesz zrobić z ADT, czego nie możesz zrobić z przedmiotami?”, Odpowiedź brzmi „nic”. Tylko czasami (głównie) okaże się, że rozwiązania ADT są znacznie mniej szczegółowe, a te oparte na obiektach są prawdopodobnie bardziej elastyczne. Aby umieścić go w drzewie analizy reprezentowanym przez narzędzia ADT:

If(Call(Ident('likes_ADTs'),[Ident('you')]),
   Call(Ident('use_ADTs'),[Ident('you')]),
   Call(Ident('use_no_ADTs'),[Ident('you')]))

— back2dos
źródło