Algebraïsch datatype
Uit Wikipedia, de vrije encyclopedie
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 pattern matching. Algebraïsche datatypen worden voornamelijk gebruikt in functionele programmeertalen.
Inhoud |
[bewerk] Voorbeelden
[bewerk] Lijsten
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.
[bewerk] Boomstructuren
Een ander voorbeeld zijn boomstructuren; in Haskell kunnen we bijvoorbeeld de volgende boomstructuur definiëren:
data Boom = Leeg | Blad Int | Tak Boom Boom
Leeg
, 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.
Operaties op dit datatype gebeuren met behulp van pattern matching. Men kan bijvoorbeeld de diepte van de boom berekenen met de volgende functie:
diepte :: Boom -> Int diepte Leeg = 0 diepte (Blad n) = 1 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.
[bewerk] Overige
Enumeraties zijn een speciaal geval van een algebraïsch datatype (veel constructoren zonder argumenten, bijvoorbeeld data Richting = Noord | Oost | Zuid | West
).