Personal tools

Abstract data type

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(Adding extra stuff from HaWiki)
(Using a type class)
 
(5 intermediate revisions by 3 users not shown)
Line 1: Line 1:
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.
+
==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.
   
Here's an example of an abstract data type:
+
==Example==
  +
===Tree===
  +
Here's an example of a '''parameterized data type'''.
   
 
<haskell>
 
<haskell>
Line 10: Line 10:
 
</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. 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:
+
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:
   
 
<haskell>
 
<haskell>
Line 17: Line 17:
 
</haskell>
 
</haskell>
   
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.
+
The user here fills in the type of elements of the tree (<hask>Integer</hask>). 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.
 
In contrast, a [[Concrete data type]] is one which does not provide such flexibility.
   
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 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.
   
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.
+
We can implement a simple [[polymorphism | polymorphic]] stack using a list without actually telling the consumer anything about its inner workings.
 
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.
 
 
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:
 
 
<haskell>
 
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
 
</haskell>
 
 
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.
 
 
 
==Other examples==
 
[[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
 
The module only exports the type constructor (but not the data constructor) and the
 
functions:
 
functions:
Line 46: Line 46:
 
If you later decide to change the stack implementation, the API doesn't change. Also you can be sure
 
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.
 
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:
  +
  +
<haskell>
  +
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
  +
</haskell>
  +
  +
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==
 
==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 <hask>Tree</hask> above).
   
Haskell syntax support this in that names of abstract things start with a lowercase letter (like 't' above), and names of concrete things start an uppercase letter (like Tree above).
+
[[Category:Language]]

Latest revision as of 14:24, 6 April 2011

Contents

[edit] 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, 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.

[edit] 2 Example

[edit] 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)
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.

[edit] 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.

[edit] 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.

[edit] 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.

[edit] 4 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).