Abstract data type

Definition

An abstract data type is a description of a common representation of data. It's a building block for data structures. Abstract data types are one of the most important concepts in all programming, because they allow building representations for complex data from simpler parts.

Example

Tree

Here's an example of an abstract data type:

data Tree a = Nil 
            | Node { left  :: Tree a,
                     value :: a,
                     right :: Tree a }

This type is called abstract because it leaves some aspects of its own structure undefined, to be provided by the user of the data type. This is also often referred to as a parameterized data type.

In this example, the type of elements contained in the tree is left open. For example, a user of this data type might use it like this:

three_number_tree :: Tree Integer
three_number_tree = Node (Node Nil 1 Nil) 2 (Node Nil 3 Nil)

The user here fills in the type of elements of the tree (Integer). A different user might specify a different type for that parameter. This flexibility is what allows this type to be used in many different contexts. Different abstract data types leave different parts of the data abstract.

In contrast, a Concrete data type is one which does not provide such flexibility.

Stack

User:VolkerStolz We can implement a simple polymorphic stack using a list without actually telling the consumer anything about its inner workings. The module only exports the type constructor (but not the data constructor) and the functions:

module Stack (Stack, empty, isEmpty, push, top, pop) where

empty :: Stack a
isEmpty :: Stack a -> Bool
push :: a -> Stack a -> Stack a
top :: Stack a -> a
pop :: Stack a -> (a,Stack a)

newtype Stack a = StackImpl [a] -- opaque!
empty = StackImpl []
isEmpty (StackImpl s) = null s
push x (StackImpl s) = StackImpl (x:s)
top (StackImpl s) = head s
pop (StackImpl (s:ss)) = (s,StackImpl ss)

If you later decide to change the stack implementation, the API doesn't change. Also you can be sure that the user cannot modify "your" data structures inside the abstract data type.

Discussion

Note that there are many different ways of implementing abstract data types. For the purpose of distinguishing between abstract and concrete data types, it is not important which one is used. For example, OO languages commonly use subtyping and encapsulation for building abstract data types.

The central concept related to abstract data types is the "interface" to an abstract data type. This is the set of operations that the abstract data type provides that can be used to manipulate values of the data type. In the above example, the interface contains the following operations: Nil (constructor), Node (constructor), left (projection), value (projection) and right (projection). The set of operations in the interface does not contain any operations for manipulating the part of the data type that was left abstract.

The above data type is not "fully" abstract though. In particular, the implementation of the operations in the interface was not made abstract. This means that the implementation cannot be changed without changes to all code that uses the type.

Using a type class

In Haskell, it is also possible to describe an interface to a data type using the Type class concept. This provides a mechanism for making the implementation of operations for a data type abstract as well. For example, the above interface for the abstract Tree data type might be described as:

class Tree t where
    nil   :: t a
    node  :: t a -> a -> t a -> t a
    left  :: (MonadPlus m) => t a -> m (t a)
    right :: (MonadPlus m) => t a -> m (t a)
    value :: (MonadPlus m) => t a -> m a

Note that this description is even more abstract than the description of the Tree abstract data type above. This interface will also make the implementation of the tree abstract (not just the element type). This interface allows the user to change the implementation of the tree data type later easily.

Syntax

Haskell syntax support this in that names of abstract types start with a lowercase letter (like 't' above), and names of concrete types start with an uppercase letter (like Tree above).