TIPOS ABSTRACTOS DE DATOS & LENGUAJES FUNCIONALES

Jos Burgos Gil Rubn Racero Tllez Mireya Rodrguez SantiagoTIPOS ABSTRACTOS DE DATOS & HASKELL11CONTENIDOTTAADD en Haskell.Comparativa con la POO.Implementacin de montculos en Haskell.Implementacin de colas en Haskell. Cola Simple.Cola Burton.Estudio comparativo.22

TTAADD en HaskellDECLARACIN DE MODULOSEn Haskell, la nica forma de crear TTAADD son los mdulos.Module Tad () where

La lista de exportacin especifica las entidades que se pueden usar desde otros mdulos.Exportacin Implcita.Exportacin selectivaFuncionesOperadoresDefiniciones de tiposClases. Mtodos.

3En el nombre del modulo ha de ir la primera letra en Mayscula. No hay relacin formal entre el modulo y el fichero que lo contiene: pueden tener nombres distintos, definir mas de un mdulo en el mismo fichero o incluso definir el mismo mdulo en distintos ficheros.

En la lista de exportacin declaramos qu entidades queremos exportar a otros mdulos:

3TTAADD en HaskellTres formas de declarar el tipo:Type. Declaramos un sinnimo de tipo. typeString=[Char]type Cola [a] = [a]newTypeDefinimos un tipo cuya representacin es idntica a otro tipo existente pero que tiene identidad propia para el sistema de tipos.newtype Cola [a]= MakeCola [a] todas las instancias que se hagan de la clase Cola dan lugar automticamente a instancias de array.

4NewTipe puede ser una buena idea cuando tenemos que implementar un tipo abstracto cuya estructura interna es una lista.La ventaja sobre Type es que la implementacin del tipo queda encapsulada con el constructor de dato. 4TTAADD en HaskellDataDefinimos constructor de datos : de ellos se obtiene el valor. Tienen lugar en tiempo de ejecucin.Definimos constructor de tipo: con el se obtiene el tipo. Tienen lugar en tiempo de compilacin. Forman parte del proceso de tipificado.

dataTreea=Leafa|Branch(Treea)(Treea)

Branch::Treea->Treea->TreeaLeaf::a->Treea

5Con el tipo data definimos tanto un constructor de tipo, que dar nombre al tipo que estamos definiendo. Ya existe en tiempo de compilacion.Tambin definimos constructores de datos o constructores a secas, que con ellos crearemos las diferentes5TTAADD en HaskelDataDefinimos un constructor de datos : de ellos se obtiene el valor. Tienen lugar en tiempo de ejecucin.Definimos un constructor de tipo: con el se obtiene el tipo. Tienen lugar en tiempo de compilacin. Forman parte del proceso de tipificado.

dataTreea=Leafa|Branch(Treea)(Treea)

Branch::Treea->Treea->TreeaLeaf::a->Treea

CONSTRUCTOR DE TIPO 66TTAADD en HaskellDataDefinimos un constructor de datos : de ellos se obtiene el valor. Tienen lugar en tiempo de ejecucin.Definimos un constructor de tipo: con el se obtiene el tipo. Tienen lugar en tiempo de compilacin. Forman parte del proceso de tipificado.

dataTreea=Leafa|Branch(Treea)(Treea)

Branch ::Treea->Treea->TreeaLeaf::a->Treea

CONSTRUCTORES DE DATOS77TTAADD en HaskellDECLARACIN DE MODULOS

moduleTree(Tree(Leaf,Branch),fringe)where

dataTreea=Leafa|Branch(Treea)(Treea)

fringe::Treea->[a]fringe(Leafx)=[x]fringe(Branchleftright)=fringeleft++fringerightExportamos los constructores de datos8En el ejemplo anterior se introducen en la lista de exportacin los constructores de tipo, para que otro mdulo los pueda usar directamente para crear un tipo Tree8

TTAADD en HaskellDECLARACIN DE MODULOSmodule TadHeap ( heapVacio, -- Construye un Heap vacioraizH, -- :: Heap a -> aesVacio, -- :: Heap a -> BoolesHeap, -- :: Ord a => Heap a -> BoolinsertarH, -- :: Ord a => a -> Heap a -> Heap aeliminarH, -- :: Heap a -> Heap alistaAheap, -- :: [a] -> Heap a -> Heap aheapAlista, -- :: Heap a -> [a]heapSort -- :: [a] -> [a]) where

data Heap a = Null | NodoH (Heap a) a (Heap a)

Ocultamos los constructores de datos9En la lista de exportacin declaramos qu entidades queremos exportar a otros mdulos:

En este ejemplo estamos exportando solamente las funciones relacionadas con el tad, pero no se exportan sus constructores de tipo, Por lo que un modulo que use esta clase deber hacer uso de la funcin hepVacio, que encapsula a los constructores de datos.9TTAADD en HaskellPOLIMORFISMO EN HASKELLPolimorfismo paramtrico: variables de tipo. Polimorfismo Ad-hoc o sobrecarga: Particularidades:Distinto comportamiento para diferentes tipos. Tipos para los cuales no tiene sentido la implementacin.

Mecanismo: clases de tiposPermiten declarar qu tipos soninstanciasde qu clases, y dar definiciones paralasoperacionessobrecargadas asociadas con cada clase.

10El sistema de tipos de Haskell posee una caracterstica que lo distingue de otros lenguajes de programacin. El tipo de polimorfismo del que hemos tratado hasta ahora es denominado polimorfismoparamtrico. Esto lo conseguimos gracias a las variables de tipo, que representan un tipo genrico. En este sentido la declaracin de funciones parametrizadas es mucho mas limpia en Haskell que en otros lenguajes como C, Java.Existe otro tipo de polimorfismo llamadoad hocosobrecarga.En Haskell, lasclases de tipos proporcionan un modo estructurado de controlar el polimorfismo ad hoc o sobrecarga. Un ejemplo de esto es el operador +, aplicable a diferentes tipos de datos, y para cada uno de ellos se comporta de una determinada forma.

10TTAADD en HaskellPOLIMORFISMO EN HASKELL.CLASES DE TIPOS

11En esta figura podemos comprobar la jerarqua de clases de tipos que se encuentran en el prelude de Haskell.

11TTAADD en HaskellOVERLOADING.EJEMPLOS La igualdad.

Funcin est en lista usa la igualdad en su definicin:estaEnLista :: a [a] BoolestaEnLista x elem [] = Falsex elem (y:ys)= x==y || (x elem ys) De ah se infiere que el tipo de la igualdad debe ser: == :: a a BoolProblema: hay que restringir ms el tipo.

12El problema de la igualdad es que no todos los tipos deben hacer uso de ella. Por ejemplo la igualdad de funciones no es computable.

Incluso asumiendo que tuviera sentido para todos los tipos el cmputo realizado para comparar dos listas es distinto al realizado al comparar dos enteros. Por todo ello, es de esperar que==estsobrecargadopara realizar estas tareas distintas. La solucin es restringir mas el tipo de la igualdad, y para ello Haskell nos proporciona las clases de tipos

12TTAADD en HaskellOVERLOADING.EJEMPLOS Clase eqclass Eq a where(==):: (Eq a) => a a Bool

13El objetivo es declarar Eq como una clase, que formar parte de las clases de tipos. En este sentido la clase solo tendr una operacin:(==).En realidad en el prelude estn definidas dos: la igualdad y la desigualdad, pero solo hace falta que se redefina la operacin ==, ya que Haskell calcula la desigualdad como not equal.Este tipo debe ser ledo del siguiente modo: "Para cada tipoaque es una instancia de la claseEq,==tiene como tipoa->a->Bool."

13TTAADD en HaskellOVERLOADING.EJEMPLOS Clase eqclass Eq a where(==):: (Eq a) => a a Bool

CONTEXTO14As,Eq ano es una expresion de tipo, sino que expresa una restriccin sobre un tipo, y se denomina uncontexto

14TTAADD en HaskellOVERLOADING.EJEMPLOS Clase eq

En nuestros TTAADD es necesario hacer una instancia de la clase para nuestrotipo si lo hemos definido con data:instance Eq a => Eq (BCola a) whereq==q' = f==f' where BC f [] = flush q BC f' [] = flush q'class Eq a where(==):: (Eq a) => a a Bool15As estamos indicando que hacemos una instancia de Eq a donde a va a ser en realidad (Bcola a)

Y redefinimos el metodo (==) de la clase conforme a nuestro TTAADD.15TTAADD en HaskellHERENCIA. Inclusiones de clase: Permite reducir el tamao de los contextos.(Eq a, Ord a) (Ord a)Los mtodos de las subclases pueden asumir la existencia de los mtodos de la superclase.x < y = x Ord a where () :: a -> a -> Bool max, min :: a -> a -> a

16Las inclusiones de clase permiten reducir el tamao de los contextos: Una expresin de tipopara una funcin que utiliza operaciones tanto de las clases Eq como Ord podra utilizar elcontexto ( Ord a ) en lugar de ( Eq a , Ord a ) , puesto que Ord implica Eq . Adems, losmtodos de las subclases pueden asumir la existencia de los mtodos de la superclase. Por ejemplo, la funcin aesVacio :: h a -> BoolesHeap :: Ord a => h -> Bool module HeapB (HeapB) whereinsertarH :: Ord a => a -> h a -> h a import HeapeliminarH :: h a -> h a .. instance Heap HeapB where1818TTAADD en HaskellINTERFACES SOBRECARGADOResolveremos las ambigedades con dos mecanismos:Con una declaracin de tipo. usoHeap :: HeapA a -> [a] usoHeap :: HeapB a -> [a] Con cualificaciones de tipo. let hA = insertarH 4 (heapVacio :: HeapA int)

19Ahora cualquier mdulo que lo necesite puede usarlas dos implementaciones de Heap, y las ambigedades se resolvernDe dos formas posibles:O con una declaracin de las distintas funciones con el tipo que programador quiera usarO si dentro de una misma funcin tengo necesidad de usar las dos implementaciones, con una cualificacin del tipo en cada referencia a un elemento (una funcin o constructor) de un modulo determinado.19TTAADD en HaskellINTERFACES SOBRECARGADOResolveremos las ambigedades con dos mecanismos:Con una declaracin de tipo. usoHeap :: HeapA a -> [a] usoHeap :: HeapB a -> [a] Con cualificaciones de tipo. let hA = insertarH 4 (heapVacio :: HeapA int)

20hA :: HeapA int20La POO y HaskellAnalgas.POO HASKELLCLASE --------------- CLASE DE TIPOSOBJETO --------------- TIPOEntonces: Lasclasescapturan conjuntos comunes deoperaciones. Unobjetoconcreto puede ser unainstanciade una clase, y habr unmtodopara cada operacin. Las clases pueden aparecer jerarquizadas, dando lugar a las nociones desuperclaseysubclase, y permitiendo laherenciade operaciones/mtodos. Unmtodo por defectopuede estar asociado con una operacin."2121La POO y HaskellDiferencias.Los tipos no son objetos no tiene sentido la nocin de estado modificable interno de un objeto o tipo.Los mtodos son completamente seguros con respecto a los tipos . Errores en tiempo de compilacin.El sistema de clases de Haskell no contempla el control de acceso a los mtodos (tales como accesos privados o pblicos). Es el mdulo el que filtra lo que se quiere ocultar.El tipo de un objeto Haskell no puede ser promocionado implcitamente; no hay una clase base universal.

22Alcontrarioque en POO, los tipos no son objetos, y en concreto, no tiene sentido la nocin de estado modificable interno de un objeto o tipo. Una ventaja en relacin con algunos lenguajes orientados a objetos es que los mtodos de Haskell son completamente seguros con respecto a los tipos (type-safe): cualquier intento de aplicar un mtodo a un valor cuyo tipo no est en la clase requerida ser detectado en tiempo de compilacin en vez de en tiempo de ejecucin. Es decir, los mtodos no son buscados en tiempo de ejecucin, sino que son simplemente pasados como argumentos a funciones de orden superior.

El tipo de un objeto Haskell no puede ser promocionado implcitamente; no hay una clase base universal tal comoObjectcuyos valores pueden ser projectados a otros objetos.

22Heaps en HaskellPropiedad estructural:Un rbol Binario es Completo si tiene todos sus niveles completos, a excepcin quizs del ltimo, en el cul todas las hojas estn situadas tan a la izquierda como sea posible.2323Heaps en Haskell24Arbol parcialmente ordenado:El valor de cualquier nodo es mayor o igual que el desus hijos. El valor de cualquier nodo es menor o igual que el de sus hijos.24Heaps en HaskellUn heap es un AB completo y parcialmente ordenado.Propiedades:Todas las ramas del rbol son secuencias ordenadasLa raz del rbol es el nodo de valor mnimo (Min-Heap) ,o mximo (Max-Heap)Todo subrbol de un Heap es tambin un Heap.

2525Heaps en HaskellComparativa con otras estructuras

26

26Heaps en HaskellUtilidades principales del Heap:

Ordenacin HeapSort.HeapSort es un algoritmo de ordenacin de la misma eficiencia que el QuickSort ( n*log n).

Colas de prioridadExtraccin rpida.Algoritmos de extraccin e insercin de orden O (log n).2727Heaps en HaskellOrdenacin HeapSort

A continuacin veremos la implementacin del algoritmo de ordenacin HeapSort, de una manera eficiente e intuitiva.

Para ello construiremos un mdulo Heap, y nos ayudaremos de un tipo cola.

2828Heaps en Haskell29Mdulo HeapModule Heap(Heap,emptyHeap,heapEmpty,findHeap,insHeap,delHeap)whereemptyHeap :: (Ord a) =>Heap aHeapEmpty :: (Ord a) =>Heap a ->BoolfindHeap :: (Ord a) =>Heap a -> ainsHeap :: (Ord a) => a ->Heap a ->Heap adelHeap :: (Ord a) =>Heap a ->Heap aHeaps en Haskell30Tipo abstracto de datos Heap.data (Ord a) =>Heap a = EmptyHP | HP a Int (Heap a) (Heap a)deriving show

ImplementacinemptyHeap = EmptyHP

heapEmptyEmptyHP = TrueheapEmpty _ = False

Heaps en Haskell31Implementacin(II)findHeapEmptyHP = error findHeap: emptyheapfindHeap (HP x _ a b) = x

insHeap x h = merge (HP x 1 EmptyHPEmptyHP) h

delHeapEmptyHP = error delHeap:emptyheapdelHeap (HP x _ a b) = merge a bHeaps en Haskell32Funciones auxiliares rank :: (Ord a) =>Heap a ->IntrankEmptyHP = 0rank (HP _ r _ _) = r

makeHP :: (Ord a) => a ->Heap a ->Heap a ->Heap amakeHP x a b | rank a >= rank b = HP x (rank b + 1) a b | otherwise = HP x (rank a + 1) b a

merge :: (Ord a) =>Heap a ->Heap a ->Heap amerge h EmptyHP = hmergeEmptyHP h = hmerge h1@(HP x _ a1 b1) h2@(HP y _ a2 b2)| x [a] ->PQueue a mkPQxs = foldrenPQemptyPQxs

hsort :: (Ord a) => [a] -> [a]hsortxs = hsort' (mkPQxs)wherehsort' pq| (pqEmptypq) = []| otherwise = (frontPQpq):(hsort' (dePQpq))Heaps en Haskell35Libro: Algorithms - A FunctionalProgrammingApproach. F Rabhi - G Lapalme (1999).djvu35Colas en HaskellEstructuras FIFO muy comunes en el mundo real.Tiene los siguientes costes computacionales:La operacin sacaDeCola : O(1)La operacin meteEnCola: O(n)

Mejora que propone Burton: modificar la estructura interna del tipo Cola para que meteEnCola = O(1).

3636Colas en Haskell37COLABCOLATCOLATPRUEBABPRUEBACREARPRUEBAFICH.TXT37Colas en Haskell38COLABCOLATCOLATPRUEBABPRUEBACREARPRUEBAFICH.TXT38Colas en HaskellEstructura de BurtonTendremos dos listas: LS : nos servir para sacar elementos. (Lista ordenada) LM : nos servir para meter elementos.(Lista invertida)

E1 E2 E3 E4 E5 E6E9 E8 E7LSLM3939Colas en Haskell Operacin meter cola:meteEnCola (BC f r) x = check f (x:r)E1 E2 E3 E4 E5 E6E9 E8 E7LSLM4040Colas en Haskell Operacin meter cola: Insertamos al comienzo de LM el elemento. No es necesario recorrer ninguna lista.E1 E2 E3 E4 E5 E6 E10 E9 E8 E7LSLM4141Colas en Haskell Operacin sacar cola: sacaDeCola (BC [] _) = colaVacia sacaDeCola (BC (x:f) r) = check f r

E1 E2 E3 E4 E5 E6 E10 E9 E8 E7LSLM4242Colas en Haskell Operacin sacar cola: Cogemos el primer elemento de LS. No es necesario recorrer ninguna lista. E2 E3 E4 E5 E6 E10 E9 E8 E7LSLM4343Colas en Haskell44Caso especial: Qu ocurre si la lista LS esta Vaca?Funcin Check

check :: [a] -> [a] -> BCola a check [] r = BC (reverse r) [] check f r = BC f r44Colas en Haskell

Peor caso: Tenemos que traspasar la lista LM a LS en orden inverso. Coste computacional : O(n) E10 E9 E8 E7LSLM4545Colas en Haskell Caso especial (continuacin)

E7 E8 E9 E10LSLM4646Colas en Haskell47COLABCOLATCOLATPRUEBABPRUEBACREARPRUEBAFICH.TXT47Colas en Haskell48Implementacin de la semilla.Semilla : dato a partir del cual se genera una lista pseudo-aleatoria.Funciones:Funcin ciclo.Funcin cicloCongruenciaMixtaFuncin transformaEntreIntervalos.Funcin listaAzar.Funcin semillaIO.Main.

Explicar que quiere decir pseudo-aleatoria :Los computadores no disponen de mecanismos reales para obtener una secuencia de nmeros aleatorios, por el contrario simulan su generacin por medio de clculos en general muy simples.48Colas en Haskell49Funcin ciclo: ciclo :: Eq a => (a -> a) -> a -> [a]ciclo f x = cicloAux f x []cicloAux f x xs = if (elem x xs) then [] else x : cicloAux f (f x) (x:xs)

Le aplica una semilla inicial a una funcin devolviendo la lista pseudo-aleatoria sin ciclos.

49Colas en Haskell50Funcin cicloCongruenciaMixtacicloCongruenciaMixta :: Multiplicador -> Modulo -> Incremento -> Semilla -> [Int]cicloCongruenciaMixta mul md inc sem = ciclo (\s -> rem (mul*s+inc) md) sem

Devuelve una lista sin ciclos de nmeros entre 0 y el argumento Modulo.Esta funcin toma uma semilla inicial, la multiplica por un numero mul, luego lo incrementa(inc) para finalmente hacerle el modulo md.Esta secuencia es variable dependiendo de los ciclos

50Colas en Haskell51Funcin transformaEntreIntervalos.

transformaEntreIntervalos :: (Int, Int) -> (Int, Int) -> Int -> InttransformaEntreIntervalos (a,b) (c,d) x = (div ((d+a+1-c)*x) (b+1))+c

Recibe dos intervalos y un valor que estar comprendido dentro del primer intervalo. El numero de valores que encierra el segundo intervalo indicar el numero de particiones de igual tamao que habr en el primer intervalo.

Comentar las ventajas:Esto se hace para que el comportamiento no sea tan malo. 51Colas en Haskell52Ejemplo:

transformaEntreIntervalos (0,1023) (0,1) x0, si 0 x 5111, si 512 x 1023Colas en Haskell53Funcin listaAzar.

listaAzar :: (Int,Int) -> Semilla -> [Int]listaAzar (a,b) sem = map (transformaEntreIntervalos (0,131071) (a,b)) (cicloCongruenciaMixta 77 131072 1 sem)

Devuelve una lista pseudo-aleatoria de nmeros pertenecientes al intervalo que se le pasa como argumento y partiendo de una semilla inicial.

53Colas en Haskell54Funcin semillaIO.

semillaIO :: IO [Int]semillaIO = getStdRandom (randomR(0,131071)) >>= return.listaAzar (0,1)

Devuelve un valor mondico IO, que ser la lista pseudo-aleatoria de 0s y 1s.Ventajas respecto a listaAzar: no tiene argumentos.Ya no depende de la semilla inicial, sino que la funcion getStdRandom devolvera una semilla inicial entre 0 y 13107154Colas en Haskell55Main.

main :: IO () main = do numbers [Int] -> TCola a -> TCola ainsertar [] q = qinsertar (x:xs) q |x==0 = insertar xs (sacaDeCola q) |x==1 = insertar xs (meteEnCola q 3)

Toma la lista pseudo-aleatoria generada y realiza una accin dependiendo de los valores.58Colas en Haskell59Funcin play

play :: [Int] -> IO ()play xs = putStrLn (toString (insertar xs colaVacia))

Recibe la lista pseudo-aleatoria generada por la semilla y se la manda a insertar para que comience a ejecutarse.PutStrLn mostrar por pantalla el resultado de cmo queda la cola.59Colas en Haskell60Main:main :: IO ()main = donumbers