Algebraïsch datatype

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In de informatica is een algebraïsch datatype een datatype waarin de waarden van andere datatypen verpakt zijn met constructoren. De constructor wordt niet uitgevoerd maar deze wordt gebruikt om de data uit het datatype te halen met patroonherkenning. Algebraïsche datatypen worden voornamelijk gebruikt in functionele programmeertalen.

Voorbeelden[bewerken]

Lijsten[bewerken]

Een voorbeeld van een algebraïsch datatype is een lijst met twee constructoren: een voor een lege lijst en een voor het samenvoegen van een element en een lijst. In bijvoorbeeld Haskell worden deze genoteerd met respectievelijk [] en : en in Lisp met nil en cons (een afkorting voor constructor). Een lijst met de getallen 1, 2 en 3 ([1, 2, 3]) kan in Haskell als volgt geconstrueerd worden: 1 : (2 : (3 : [])). De lijst bevat elementen van een ander datatype (Integers) en deze worden samengevoegd met behulp van de constructoren.

Boomstructuren[bewerken]

Een ander voorbeeld zijn boomstructuren; in Haskell kunnen we bijvoorbeeld de volgende boomstructuur definiëren:

data Boom = Blad Int | Tak Boom Boom

Blad en Tak zijn hier de constructoren van het datatype. Door constructoren toe te passen op argumenten met het juiste type kan een boomstructuur geconstrueerd worden. Deze constructoren zijn te vergelijken met functies met nul of meer argumenten die een boomstructuur opleveren. Zo kan men de constructor Blad zien als een functie met het type Int -> Boom aangezien men door de constructor toe te passen op een Int een Boom verkrijgt. De Tak-constructor neemt twee bomen als argumenten waardoor het een recursief datatype is. Deze constructorfuncties kunnen gebruikt worden zoals gewone functies, bijvoorbeeld:

-- Het volgende geeft een lijst met vier Bomen, elk bestaande uit 1 Blad:
map Blad [1..4]

Operaties op dit datatype gebeuren met behulp van patroonherkenning. Men kan bijvoorbeeld de diepte van de boom berekenen met de volgende functie:

diepte :: Boom -> Int
diepte (Blad n)  = 0
diepte (Tak l r) = 1 + max (diepte l) (diepte r)

De constructoren worden gebruikt om te herkennen op wat voor soort Boom de functie wordt toegepast.

Foldfuncties voor boomstructuren[bewerken]

De hogere-orde functie fold kan ook geschreven worden voor boomstructuren. Voor de bovenstaande boomstructuur kunnen we de volgende foldfunctie schrijven:

foldBoom :: (Int -> Int, Int -> Int -> Int) -> Boom -> Int
foldBoom     (f, _) (Blad n) = f n
foldBoom alg@(_, g) (Tak l r) = g (foldBoom alg l) (foldBoom alg r)

Er wordt een Boom meegegeven en een tupel met functies, namelijk een functie voor elke constructor van Boom. Dit tupel met functies wordt ook wel een algebra genoemd. Het is nu mogelijk om allerlei operaties op een Boom uit te voeren, afhankelijk van de algebra die men meegeeft. Enkele voorbeelden:

voorbeeldBoom :: Boom
voorbeeldBoom = Tak (Blad 3) (Tak (Blad 5) (Blad 2))

sumBoom :: Boom -> Int 
sumBoom = foldBoom (id, (+))

multBoom :: Boom -> Int
multBoom = foldBoom (id, (*))

Hierin is id een functie die het meegegeven argument weer oplevert (dus: id x = x). De waarde van sumBoom voorbeeldBoom is 10 (alle elementen in de boom bij elkaar opgeteld) en de waarde van multBoom voorbeeldBoom is 30 (alle elementen in de boom met elkaar vermenigvuldigd). Ook de functie diepte kan geschreven worden met foldBoom:

diepteBoom :: Boom -> Int
diepteBoom = foldBoom (\n -> 0, \l r -> 1 + max l r)

Overige[bewerken]

Enumeraties zijn een speciaal geval van een algebraïsch datatype (veel constructoren zonder argumenten, bijvoorbeeld data Richting = Noord | Oost | Zuid | West).