lunes, 19 de septiembre de 2016

Que es Abstract Data Types?

Abstract Data Types o ADT es un tipo de dato con operaciones asociadas, pero cuya representación está oculto o es abstracta. Los ejemplos más comunes de tipos de datos abstractos son los tipos primitivos en Haskell como Integer y Float.

Haskell apoya la definición de tipos de datos abstractos a través del sistema de módulos. Los tipos paramentados se pueden ver como una especie de tipo abstracto, porque dejan algunas partes del tipo de datos no definido, o abstracto.

Veamos un ejemplo:

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

Este tipo es abstracto, ya que deja algunos aspectos de su estructura indefinida, que será asumida por el usuario del tipo de datos. Esta es una forma débil de tipo abstracto de datos.

Un usuario puede utilizar esta estructura con enteros:

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

Otro usuario diferente podría especificar un tipo diferente para ese parámetro. Esta flexibilidad es lo que permite este tipo que se utiliza en muchos contextos diferentes. 

Por el contrario, un tipo de datos concreto es uno que no proporciona tal flexibilidad.

Un tipo abstracto de datos más tradicional oculta completamente la estructura interna, o representación, de los datos. El siguiente ejemplo ilustra esta forma más tradicional de tipo abstracto de datos.

Podemos implementar una pila polimórfico simple usando una lista sin tener que decir algo a los consumidores acerca de su funcionamiento interno. El módulo sólo exporta el constructor de tipos (pero no el constructor de datos) y las funciones:

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)

Si más tarde decide cambiar la pila de ejecución, la API no cambia. También puede estar seguro de que el usuario no puede modificar "sus" estructuras de datos dentro del tipo de datos abstracto.