Abstract data type

Definition

An abstract data type is a type with associated operations, but whose representation is hidden. Common examples of abstract data types are the built-in primitive types in Haskell, Integer and Float. Haskell supports the definition of abstract data types via the module system. In many cases it is not necessary to completely hide the representation of data, so a normal data type definition is sufficient. In addition, parametrized types can be viewed as a kind of abstract type, because they leave some parts of the data type undefined, or abstract.

Example

Tree

Here's an example of a parameterized data type.

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

This type is abstract because it leaves some aspects of its structure undefined, to be provided by the user of the data type. This is a weak form of abstract 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.

The above example uses parametrization to achieve abstraction, while still exposing the structure of the data to its users.

Stack

User:VolkerStolz A more traditional abstract data type completely hides the internal structure, or representation, of data. The following example illustrates this more traditional form of abstract data type.

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

Abstract data types are just one form of data abstraction. Abstract data types are modeled on abstract algebras, which consist of a set of values and an collection of operations on those values. Object-oriented data abstraction is fundamentally different: objects are implemented as collections of observations (methods) that can be performed upon them. The focus on observations, rather than construction, means that objects are best understood as co-algebras. In this sense, objects and abstract data types are duals of each other.

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 "stack" example is fully abstract, but the "Tree" example is not. In particular, the implementation of the Tree 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. However, the type class does not prevent access to the underlying data representation, hence type classes provide a weaker form of abstraction than the Stack example given above.

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).