Abstract data type
From HaskellWiki
(→Using a type class) 

(2 intermediate revisions by one user not shown) 
Revision as of 14:24, 6 April 2011
Contents 
1 Definition
An abstract data type is a type with associated operations, but whose representation is hidden. Common examples of abstract data types are the builtin 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.
2 Example
2.1 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)
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.
2.2 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.
3 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. Objectoriented 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 coalgebras. 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.
3.1 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.