Abstrakter Datentyp

Ein abstrakter Datentyp besteht aus der Definition der Typen der enthaltenen Funktionen oder Operationen (siehe Signatur) und einer formalen Beschreibung der Wirkungsweise dieser Funktionen oder Operationen.

Die formale Beschreibung kann auf verschiedene Weisen erfolgen, unter anderem durch algebraische Spezifikation.

Beispielsweise hat der abstrakte Datentyp Queue<α> die folgenden Operationen:

emptyQueue: → Queue<α>
isEmpty?: Queue<α> → Boolean
enQueue: α ✕ Queue<α> → Queue<α>
deQueue: Queue<α> → α ✕ Queue<α>

Die Wirkungsweise der Operationen kann durch einige Gleichungen beschrieben werden:

isEmpty?(emptyQueue()) = true
isEmpty?(enQueue(A, Q)) = false
deQueue(enQueue(A, Q)) = A, Q