As an example to better understand the definition above have a look at a
possible specification of a list ADT:
First the signature of the ADT is defined. For that we
need some sets and functions on these sets:
E = Possible list elements (e.g. int, String,
...)
L = Merge_from_i=0_to_infinity(Ei) =
Set of all possible n-tuples with elements from
E.
BOOL = { true, false }
new: -> L
add: L x E -> L
remove: L x E ->
L
head: L -> E
tail: L -> L
isIn: L x E -> BOOL
So new is the operation which transforms nothing into a list, remove transforms a list and an element into a list, ... .
Second the semantics of the functions needs to be
defined. This can be done e.g. by specifying some
relationships between the functions: (in the following l element
of L, e and f element of E)
new() = λ
head(add(l,e)) = e
tail(add(l,e)) =
l
remove(λ,e) = error
remove(add(l,e),e) =
l
remove(add(l,f),e) = add(remove(l,e),f) (if
f != e )
isIn(add(l,e),e) = true
isIn(λ,e) =
false
isIn(add(l,f),e) = isIn(l,e)
(if f != e)
So new is creating the empty list (represented by the λ sign here). remove executed on an empty list causes an error, executed on a list onto which the to be removed element was added returns the list without that element, and executed on a list to which a different element was added iterates further through that list.
This completely determines what the ADT will do if its functions
are used but not how it will be achieved (i.e. how it is
implemented). If a little bit more about implementation
is known, one can give the bounds on time and
space mentioned in the WU above. In this example, time bounds could be (if implemented as linked list):
add: O(1)
remove: O(n) (with n = number
of elements in the list)
isIn: O(n)
head: O(1)
tail: O(1)