Algebraiczne typy danych Haskella

Algebraiczne typy danych Haskella są nazwane takimi, ponieważ odpowiadają algebrze początkowej W teorii kategorii, dając nam pewne prawa, pewne operacje i niektóre symbole do manipulowania. Możemy nawet użyć notacji algebraicznej do opisu regularnych struktur danych, gdzie:

• + reprezentuje typy sum( związki rozłączne, np. Either).
• • reprezentuje typy produktów (np. struktury lub krotki)
• X dla typu singleton (np. data X a = X a)
• 1 dla typu jednostki ()
• i μ Dla najmniej ustalonego punktu (np. typów rekurencyjnych), Zwykle implicite.

Z dodatkowym zapisem:

• X² dla X•X

W rzeczywistości można powiedzieć (po Brent Yorgey), że typ danych Haskell jest regularny, jeśli można go wyrazić w kategoriach 1, X, +, •, i najmniej stały punkt.

Dzięki tej notacji możemy zwięźle opisać wiele regularne struktury danych:

• Jednostki: data () = ()

  1

• Opcje: data Maybe a = Nothing | Just a

  1 + X

• Listy: data [a] = [] | a : [a]

  L = 1+X•L

• Drzewa binarne: data BTree a = Empty | Node a (BTree a) (BTree a)

  B = 1 + X•B²

Inne operacje (zaczerpnięte z referatu Brenta Yorgey ' a, wymienione w referencjach):

• Expansion: rozwinięcie punktu fix może być pomocne w myśleniu o listach. L = 1 + X + X² + X³ + ... (czyli, listy są albo puste, albo mają jeden element, albo dwa elementy, albo trzy lub ...)

• Skład, ◦, biorąc pod uwagę typy F i G, skład F ◦ G jest typem budującym "F-struktury zbudowane ze struktur G" (np. R = X • (L ◦ R), gdzie L jest listą, jest drzewem różanym.

• Różnicowanie, pochodna typu danych D (podana jako D') jest typem struktur D z pojedynczym "otworem", czyli wyodrębnionym miejscem nie zawierającym żadnych data. To zadziwiająco spełnia te same zasady co dla różnicowania w rachunku różniczkowym:

  1′ = 0

  X′ = 1

  (F + G)′ = F' + G′

  (F • G)′ = F • G′ + F′ • G

  (F ◦ G)′ = (F′ ◦ G) • G′

Referencje:

• gatunki, funktory i rodzaje , O mój!, Brent A. Yorgey, Haskell ' 10, 30 września 2010, Baltimore, Maryland, USA
• Clowns na lewo ode mnie, jokers na prawo (Dissecting Data Structures), Conor McBride POPL 2008

In algebra Uniwersalna algebra składa się z pewnych zbiorów elementów (pomyśl o każdym zbiorze jako o zbiorze wartości typu) i niektóre operacje, które mapują elementy do elementów.

Na przykład, załóżmy, że masz typ "elementów listy" i rodzaj "list". Jako operacje masz "pustą listę", która jest 0-argumentem funkcja zwracająca" listę "oraz funkcję" cons", która przyjmuje dwa argumenty, "element listy" i "lista", i produkować "listę".

At w tym punkcie istnieje wiele algebr pasujących do opisu, ponieważ mogą się zdarzyć dwie niepożądane rzeczy:

• W Zestawie "list" mogą znajdować się elementy, których nie można zbudować z "pustej listy" i "operacji cons", tzw. "śmieci". Może to być lista zaczynająca się od jakiegoś elementu, który spadł z nieba, lub pętle bez początku lub nieskończone listy.

• Wyniki "minusów" zastosowanych do różnych argumentów mogą być równe, np. złożenie elementu do niepuste listy może być równa pustej liście. Jest to czasami nazywane "zamieszaniem".

Algebra, która nie ma żadnej z tych własności nazywa się initial , i jest to zamierzone znaczenie abstrakcyjnego typu danych.

Nazwa inicjału wywodzi się od własności, która jest dokładnie jeden homomorfizm z algebry początkowej do dowolnej danej algebry. Zasadniczo można ocenić wartość listy, stosując operacje w drugiej algebrze, a wynik jest dobrze zdefiniowany.

Staje się bardziej skomplikowane dla typów polimorficznych ...

Jest to prosty powód, dla którego nazywa się je algebraicznymi; istnieją zarówno typy sum (logiczny dysjunkcja), jak i iloczyn (logiczna koniunkcja). Typ sumy jest związkiem dyskryminującym, np.:

data Bool = False | True

Typ produktu to typ o wielu parametrach:

data Pair a b = Pair a b

W O ' Caml "produkt" jest bardziej wyrazisty:

type 'a 'b pair = Pair of 'a * 'b

Typy danych Haskella są nazywane "algebraicznymi" ze względu na ich związek z kategorycznymi początkowymi algebrami . Ale w ten sposób to szaleństwo.

@ olliej: ADT to tak naprawdę typy "sumowe". Krotki to produkty.

@ Timbo:

Masz zasadniczo rację co do tego, że jest to coś w rodzaju abstrakcyjnej klasy drzewa z trzema pochodnymi klasami (Empty, Leaf i Node), ale musisz również wymusić gwarancję, że ktoś korzystający z twojej klasy drzewa nigdy nie będzie mógł dodać żadnych nowych pochodnych klas, ponieważ strategią używania typu Datat drzewa jest pisanie kodu, który przełącza się w czasie wykonywania w oparciu o Typ każdego elementu w drzewie (a dodawanie nowych typów pochodnych złamie istniejący kod). Można sobie wyobrazić jest to coraz nieprzyjemniejsze w C # lub C++, ale w Haskell, ML i OCaml, jest to kluczowe dla konstrukcji języka i składni, więc styl kodowania obsługuje go w znacznie wygodniejszy sposób, poprzez dopasowanie wzorców.

Typy ADT (sum) są również rodzajami tagged unions lub variant types W C lub c++.

Stare pytanie, ale nikt nie wspomniał o zerowości, która jest ważnym aspektem algebraicznych typów danych, być może najważniejszym aspektem. Ponieważ każda wartość jest jedną z alternatyw, możliwe jest wyczerpujące dopasowywanie wzorców na podstawie wielkości liter.

Dla mnie pojęcie algebraicznych typów danych Haskella zawsze wyglądało jak polimorfizm w językach OO, takich jak C#.

Spójrz na przykład z http://en.wikipedia.org/wiki/Algebraic_data_types :

data Tree = Empty 
          | Leaf Int 
          | Node Tree Tree

To może być zaimplementowane w C# jako klasa bazowa TreeNode, z pochodną klasą Leaf i pochodną klasą TreeNodeWithChildren, a jeśli chcesz nawet pochodną klasę EmptyNode.

(OK wiem, nikt nigdy by tego nie zrobił, ale przynajmniej ty mógłbyś to zrobić.)