# Abstract data type

### From HaskellWiki

BrettGiles (Talk | contribs) (Revising to ensure examples of parametrized data type are included) |
|||

Line 1: | Line 1: | ||

==Definition== |
==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. |
+ | 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, Int 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== |
==Example== |
||

===Tree=== |
===Tree=== |
||

− | Here's an example of an abstract data type: |
+ | Here's an example of a '''parameterized data type'''. |

<haskell> |
<haskell> |
||

Line 13: | Line 13: | ||

</haskell> |
</haskell> |
||

− | 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'''. |
+ | 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: |
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: |
||

Line 27: | Line 27: | ||

===Stack=== |
===Stack=== |
||

[[User:VolkerStolz]] |
[[User:VolkerStolz]] |
||

+ | The above example uses parametrization to achieve abstraction, while |
||

+ | still exposing the structure of the data to its users. 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 [[polymorphism | polymorphic]] stack using a list without actually telling the consumer anything about its inner workings. |
We can implement a simple [[polymorphism | 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 |
The module only exports the type constructor (but not the data constructor) and the |
||

Line 51: | Line 57: | ||

that the user cannot modify "your" data structures inside the abstract data type. |
that the user cannot modify "your" data structures inside the abstract data type. |
||

==Discussion== |
==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. |
+ | 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 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. |
+ | 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=== |
===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: |
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: |

## Revision as of 14:18, 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 built-in primitive types in Haskell, Int 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.

### 2.2 Stack

User:VolkerStolz The above example uses parametrization to achieve abstraction, while still exposing the structure of the data to its users. 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. 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.

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