Tema 20: El tipo abstracto de los montículos

Índice

1. Especificación del TAD de los montículos
- 1.1. Signatura del TAD de los montículos
- 1.2. Propiedades del TAD de los montículos
2. Implementación del TAD de los montículos
- 2.1. Los montículos como tipo de dato algebraico
3. Comprobación de la implementación con QuickCheck
4. Implementación de las colas de prioridad mediante montículos
- 4.1. Las colas de prioridad como montículos
- 4.2. Comprobación de las propiedades
5. Material complementario
6. Bibliografía

1. Especificación del TAD de los montículos

1.1. Signatura del TAD de los montículos

1.1.1. Descripción de los montículos

Un montículo es un árbol binario en el que los valores de cada nodo es menor o igual que los valores de sus hijos. Por ejemplo,

     1              1
    / \            / \
   /   \          /   \
  2     6        3     6
 / \   / \      / \   / \
3   8 9   7    4   2 9   7

el de la izquierda es un montículo, pero el de la derecha no lo es.

1.1.2. Signatura del TAD de los montículos

Signatura

vacio   :: Ord a => Monticulo a
inserta :: Ord a => a -> Monticulo a -> Monticulo a
menor   :: Ord a => Monticulo a -> a
resto   :: Ord a => Monticulo a -> Monticulo a
esVacio :: Ord a => Monticulo a -> Bool
valido  :: Ord a => Monticulo a -> Bool

Descripción de las operaciones:
vacio es el montículo vacío.
(inserta x m) es el montículo obtenido añadiendo el elemento x al montículo m.
(menor m) es el menor elemento del montículo m.
(resto m) es el montículo obtenido eliminando el menor elemento del montículo m.
(esVacio m) se verifica si m es el montículo vacío.
(valido m) se verifica si m es un montículo; es decir, es un árbol binario en el que los valores de cada nodo es menor o igual que los valores de sus hijos.

1.2. Propiedades del TAD de los montículos

esVacio vacio
valido (inserta x m)
not (esVacio (inserta x m))
not (esVacio m) ==> valido (resto m)
resto (inserta x vacio) == vacio
x <= menor m ==> resto (inserta x m) == m
Si m es no vacío y x > menor m, entonces resto (inserta x m) == inserta x (resto m)
esVacio m || esVacio (resto m) || menor m <= menor (resto m)

2. Implementación del TAD de los montículos

2.1. Los montículos como tipo de dato algebraico

Cabecera del módulo:

module Tema_20.Monticulo
  ( Monticulo,
    vacio,   -- Ord a => Monticulo a
    inserta, -- Ord a => a -> Monticulo a -> Monticulo a
    menor,   -- Ord a => Monticulo a -> a
    resto,   -- Ord a => Monticulo a -> Monticulo a
    esVacio, -- Ord a => Monticulo a -> Bool
    valido   -- Ord a => Monticulo a -> Bool
  ) where

Librería auxiliar:
```
import Data.List (sort)
```

Los montículos como tipo de dato algebraico

data Monticulo a = Vacio
                 | M a Int (Monticulo a) (Monticulo a)
  deriving Show

La forma de los montículos no vacío es (M v r i d) donde
- v es el valor de la raíz del montículo.
- r es el rango del montículo; es decir, la menor distancia de la raíz a un montículo vacío.
- i es el submontículo izquierdo y
- d es el submontículo derecho.

Ejemplos de montículos: Los siguientes montículos

    ejM1         |    ejM2     |       ejM3
-----------------+-------------+----------------------
                 |             |          (1,2)
       (1,2)     |      (5,1)  |         /     \
      /     \    |     /       |        /       \
   (4,1)   (6,1) |   7,1)      |     (5,2)       (4,1)
   /             |             |    /     \      /
(8,1)            |             | (7,1)   (6,1)  (8,1)

Se definen por

ejM1, ejM1', ejM2, ejM3 :: Monticulo Int
ejM1  = foldr inserta vacio [6,1,4,8]
ejM1' = foldr inserta vacio [6,8,4,1]
ejM2  = foldr inserta vacio [7,5]
ejM3  = mezcla ejM1 ejM2

vacio es el montículo vacío.

vacio :: Ord a => Monticulo a
vacio = Vacio

(rango m) es el rango del montículo m; es decir, la menor distancia a un montículo vacío. Por ejemplo,

rango ejM1  ==  2
rango ejM2  ==  1

Su definición es

rango :: Ord a => Monticulo a -> Int
rango Vacio       = 0
rango (M _ r _ _) = r

(creaM x a b) es el montículo creado a partir del elemento x y los montículos a y b. Se supone que x es menor o igual que el mínimo de a y de b. Por ejemplo,

λ> ejM1
M 1 2 (M 4 1 (M 8 1 Vacio Vacio) Vacio) (M 6 1 Vacio Vacio)
λ> ejM2
M 5 1 (M 7 1 Vacio Vacio) Vacio
λ> creaM 0 ejM1 ejM2
M 0 2 (M 1 2 (M 4 1 (M 8 1 Vacio Vacio) Vacio) (M 6 1 Vacio Vacio))
      (M 5 1 (M 7 1 Vacio Vacio) Vacio)

Su definición es

creaM :: Ord a => a -> Monticulo a -> Monticulo a -> Monticulo a
creaM x a b | rango a >= rango b = M x (rango b + 1) a b
            | otherwise          = M x (rango a + 1) b a

(mezcla m1 m2) es el montículo obtenido mezclando los montículos m1 y m2. Por ejemplo,

λ> mezcla ejM1 ejM2
M 1 2 (M 5 2 (M 7 1 Vacio Vacio) (M 6 1 Vacio Vacio))
      (M 4 1 (M 8 1 Vacio Vacio) Vacio)

Su definición es

mezcla :: Ord a =>  Monticulo a -> Monticulo a -> Monticulo a
mezcla m Vacio = m
mezcla Vacio m = m
mezcla m1@(M x _ a1 b1) m2@(M y _ a2 b2)
  | x <= y    = creaM x a1 (mezcla b1 m2)
  | otherwise = creaM y a2 (mezcla m1 b2)

(inserta x m) es el montículo obtenido añadiendo el elemento x al montículo m. Por ejemplo,

λ> ejM1
M 1 2 (M 4 1 (M 8 1 Vacio Vacio) Vacio)
      (M 6 1 Vacio Vacio)
λ> inserta 3 ejM1
M 1 2
  (M 4 1 (M 8 1 Vacio Vacio) Vacio)
  (M 3 1 (M 6 1 Vacio Vacio) Vacio)

Su definición es

inserta :: Ord a => a -> Monticulo a -> Monticulo a
inserta x m = mezcla (M x 1 Vacio Vacio) m

(menor m) es el menor elemento del montículo m. Por ejemplo,

menor ejM1  ==  1
menor ejM2  ==  5

Su definición es

menor  :: Ord a => Monticulo a -> a
menor (M x _ _ _) = x
menor Vacio       = error "menor: monticulo vacio"

(resto m) es el montículo obtenido eliminando el menor elemento del montículo m. Por ejemplo,

λ> resto ejM1
M 4 2 (M 8 1 Vacio Vacio) (M 6 1 Vacio Vacio)

Su definición es

resto :: Ord a => Monticulo a -> Monticulo a
resto Vacio       = error "resto: monticulo vacio"
resto (M x _ a b) = mezcla a b

(esVacio m) se verifica si m es el montículo vacío.

esVacio :: Ord a => Monticulo a -> Bool
esVacio Vacio = True
esVacio _     = False

(valido m) se verifica si m es un montículo; es decir, es un árbol binario en el que los valores de cada nodo es menor o igual que los valores de sus hijos. Por ejemplo,

valido ejM1  ==  True
valido ejM2  ==  True
valido ejM3  ==  True
valido (M 3 5 (M 2 1 Vacio Vacio) Vacio)  ==  False

Su definición es

valido :: Ord a => Monticulo a -> Bool
valido Vacio = True
valido (M x _ Vacio Vacio) = True
valido (M x _ m1@(M x1 n1 a1 b1) Vacio) =
    x <= x1 && valido m1
valido (M x _ Vacio m2@(M x2 n2 a2 b2)) =
    x <= x2 && valido m2
valido (M x _ m1@(M x1 n1 a1 b1) m2@(M x2 n2 a2 b2)) =
    x <= x1 && valido m1 &&
    x <= x2 && valido m2

(elementos m) es la lista de los elementos del montículo m. Por ejemplo,

elementos ejM1  ==  [1,4,8,6]

Su definición es

elementos :: Ord a => Monticulo a -> [a]
elementos Vacio       = []
elementos (M x _ a b) = x : elementos a ++ elementos b

(equivMonticulos m1 m2) se verifica si los montículos m1 y m2 tienen los mismos elementos. Por ejemplo,

λ> ejM1
M 1 2 (M 4 1 (M 8 1 Vacio Vacio) Vacio)
      (M 6 1 Vacio Vacio)
λ> ejM1'
M 1 2 (M 4 1 Vacio Vacio)
      (M 6 1 (M 8 1 Vacio Vacio) Vacio)
λ> equivMonticulos ejM1 ejM1'
True

Su definición es

equivMonticulos :: Ord a => Monticulo a -> Monticulo a -> Bool
equivMonticulos m1 m2 =
  sort (elementos m1) == sort (elementos m2)

Los montículos son comparables por igualdad.

instance Ord a => Eq (Monticulo a) where
  (==) = equivMonticulos

3. Comprobación de la implementación con QuickCheck

3.1. Pragma y librerías auxiliares

Al principio del fichero se añade

{-# LANGUAGE TemplateHaskell #-}
{-# LANGUAGE FlexibleInstances #-}
{-# OPTIONS_GHC -fno-warn-orphans #-}

Importación de la implementación a verificar.

import Tema_20.Monticulo
-- import I1M.Monticulo

Importación de librerías auxiliares.
```
import Test.QuickCheck
```

3.2. Generador de montículos

(creaMonticulo xs) es el montículo correspondiente a la lista xs. Por ejemplo,

λ> creaMonticulo [6,1,4,8]
M 1 2 (M 4 1 (M 8 1 Vacio Vacio) Vacio)
      (M 6 1 Vacio Vacio)
λ> creaMonticulo [6,8,4,1]
M 1 2 (M 4 1 Vacio Vacio)
      (M 6 1 (M 8 1 Vacio Vacio) Vacio)

Su definición es

creaMonticulo :: [Int] -> Monticulo Int
creaMonticulo = foldr inserta vacio

genMonticulo es un generador de montículos. Por ejemplo,

λ> sample genMonticulo
Vacio
M (-1) 1 (M 1 1 Vacio Vacio) Vacio
...

Su definición es

genMonticulo :: Gen (Monticulo Int)
genMonticulo = do
  xs <- listOf arbitrary
  return (creaMonticulo xs)

instance Arbitrary (Monticulo Int) where
  arbitrary = genMonticulo

3.2.1. Corrección del generador de montículos

Propiedad: genMonticulo genera montículos válidos.

prop_genMonticulo :: Monticulo Int -> Bool
prop_genMonticulo m = valido m

Comprobación:

λ> quickCheck prop_genMonticulo
+++ OK, passed 100 tests.

3.2.2. Generador de montículos no vacíos

monticuloNV es un generador de montículos no vacío. Por ejemplo,

λ> sample monticuloNV
M 0 1 Vacio Vacio
M 1 1 (M 1 1 (M 1 1 Vacio Vacio) Vacio) Vacio
...

Su definición es

monticuloNV :: Gen (Monticulo Int)
monticuloNV = do xs <- listOf arbitrary
                 x <- arbitrary
                 return (creaMonticulo (x:xs))

3.2.3. Corrección del generador de montículos no vacíos

Propiedad: monticuloNV genera montículos no vacío.

prop_monticuloNV :: Monticulo Int -> Property
prop_monticuloNV m =
  forAll monticuloNV
         (\m -> (valido m) && not (esVacio m))

Comprobación:

λ> quickCheck prop_monticuloNV
+++ OK, passed 100 tests.

3.3. Especificación de las propiedades de los montículos

vacio es un montículo.

prop_vacio_es_monticulo :: Bool
prop_vacio_es_monticulo =
    esVacio (vacio :: Monticulo Int)

inserta produce montículos válidos.

prop_inserta_es_valida :: Int -> Monticulo Int -> Bool
prop_inserta_es_valida x m =
  valido (inserta x m)

Los montículos creados con inserta son no vacío.

prop_inserta_no_vacio :: Int -> Monticulo Int -> Bool
prop_inserta_no_vacio x m =
  not (esVacio (inserta x m))

Al borrar el menor elemento de un montículo no vacío se obtiene un montículo válido.

prop_resto_es_valida :: Monticulo Int -> Property
prop_resto_es_valida m =
  forAll monticuloNV  (\m -> valido (resto m))

El resto de (inserta x m) es m si m es el montículo vacío o x es menor o igual que el menor elemento de m y es (inserta x (resto m)), en caso contrario.

prop_resto_inserta :: Int -> Monticulo Int -> Bool
prop_resto_inserta x m =
  resto (inserta x m)
  == if esVacio m || x <= menor m
then m
     else inserta x (resto m)

(menor m) es el menor elemento del montículo m.

prop_menor_es_minimo :: Monticulo Int -> Bool
prop_menor_es_minimo m =
  esVacio m || esVacio (resto m) ||
  menor m <= menor (resto m)

3.4. Comprobación de las propiedades

Para verificar todas las propiedades se escribe

return []

verificaMonticulo :: IO Bool
verificaMonticulo = $quickCheckAll

Comprobación de las propiedades de los montículos

λ> verificaMonticulo
=== prop_genMonticulo from MonticuloPropiedades.hs:46 ===
+++ OK, passed 100 tests.

=== prop_monticuloNV from MonticuloPropiedades.hs:68 ===
+++ OK, passed 100 tests.

=== prop_vacio_es_monticulo from MonticuloPropiedades.hs:84 ===
+++ OK, passed 1 test.

=== prop_inserta_es_valida from MonticuloPropiedades.hs:96 ===
+++ OK, passed 100 tests.

=== prop_inserta_no_vacio from MonticuloPropiedades.hs:105 ===
+++ OK, passed 100 tests.

=== prop_resto_es_valida from MonticuloPropiedades.hs:118 ===
+++ OK, passed 100 tests.

=== prop_resto_inserta from MonticuloPropiedades.hs:129 ===
+++ OK, passed 100 tests.

=== prop_menor_es_minimo from MonticuloPropiedades.hs:144 ===
+++ OK, passed 100 tests.

True

4. Implementación de las colas de prioridad mediante montículos

4.1. Las colas de prioridad como montículos

Cabecera del módulo:

module ColaDePrioridadConMonticulos
  ( CPrioridad,
    vacia,   -- Ord a => CPrioridad a
    inserta, -- Ord a => a -> CPrioridad a -> CPrioridad a
    primero, -- Ord a => CPrioridad a -> a
    resto,   -- Ord a => CPrioridad a -> CPrioridad a
    esVacia, -- Ord a => CPrioridad a -> Bool
    valida   -- Ord a => CPrioridad a -> Bool
  ) where

Importación cualificada:
```
import qualified Monticulo as M
```
Descripción de las operaciones:
- vacia es la cola de prioridad vacía.
- (inserta x c) añade el elemento x a la cola de prioridad c.
- (primero c) es el primer elemento de la cola de prioridad c.
- (resto c) es el resto de la cola de prioridad c.
- (esVacia c) se verifica si la cola de prioridad c es vacía.
- (valida c) se verifica si c es una cola de prioridad válida.

Las colas de prioridad como montículos.

newtype CPrioridad a = CP (M.Monticulo a)
  deriving (Eq, Show)

Ejemplo de cola de prioridad:

λ> foldr inserta vacia [3,1,7,2,9]
CP (M 1 2
      (M 2 2
         (M 9 1 Vacio Vacio)
         (M 7 1 Vacio Vacio))
      (M 3 1 Vacio Vacio))

vacia es la cola de prioridad vacía. Por ejemplo,

vacia  == CP Vacio

Su definición es

vacia :: Ord a => CPrioridad a
vacia = CP M.vacio

(inserta x c) añade el elemento x a la cola de prioridad c. Por ejemplo,

λ> inserta 5 (foldr inserta vacia [3,1,7,2,9])
CP (M 1 2
      (M 2 2
         (M 9 1 Vacio Vacio)
         (M 7 1 Vacio Vacio))
      (M 3 1
         (M 5 1 Vacio Vacio) Vacio))

Su definición es

inserta :: Ord a => a -> CPrioridad a -> CPrioridad a
inserta v (CP c) = CP (M.inserta v c)

(primero c) es la cabeza de la cola de prioridad c. Por ejemplo,

primero (foldr inserta vacia [3,1,7,2,9])  ==  1

Su definición es

primero :: Ord a => CPrioridad a -> a
primero (CP c) = M.menor c

(resto c) elimina la cabeza de la cola de prioridad c. Por ejemplo,

λ> resto (foldr inserta vacia [3,1,7,2,9])
CP (M 2 2
      (M 9 1 Vacio Vacio)
      (M 3 1
         (M 7 1 Vacio Vacio) Vacio))

Su definición es

resto :: Ord a => CPrioridad a -> CPrioridad a
resto (CP c) = CP (M.resto c)

(esVacia c) se verifica si la cola de prioridad c es vacía. Por ejemplo,

esVacia (foldr inserta vacia [3,1,7,2,9]) ==  False
esVacia vacia                             ==  True

Su definición es

esVacia :: Ord a => CPrioridad a -> Bool
esVacia (CP c) = M.esVacio c

(valida c) se verifica si c es una cola de prioridad válida. En la representación mediante montículo todas las colas de prioridad son válidas. Su definición es
```
valida :: Ord a => CPrioridad a -> Bool
valida _ = True
```

4.2. Comprobación de las propiedades

Para verificar todas las propiedades se escribe

return []

verificaMonticulo :: IO Bool
verificaMonticulo = $quickCheckAll

Comprobación de las propiedades de los Monticulo

λ> verificaMonticulo
=== prop_genMonticulo from MonticuloPropiedades.hs:46 ===
+++ OK, passed 100 tests.

=== prop_monticuloNV from MonticuloPropiedades.hs:68 ===
+++ OK, passed 100 tests.

=== prop_vacio_es_monticulo from MonticuloPropiedades.hs:84 ===
+++ OK, passed 1 test.

=== prop_inserta_es_valida from MonticuloPropiedades.hs:96 ===
+++ OK, passed 100 tests.

=== prop_inserta_no_vacio from MonticuloPropiedades.hs:105 ===
+++ OK, passed 100 tests.

=== prop_resto_es_valida from MonticuloPropiedades.hs:118 ===
+++ OK, passed 100 tests.

=== prop_resto_inserta from MonticuloPropiedades.hs:129 ===
+++ OK, passed 100 tests.

=== prop_menor_es_minimo from MonticuloPropiedades.hs:144 ===
+++ OK, passed 100 tests.

True

5. Material complementario

El código del tema se encuentra en los siguientes enlaces

Este tema también se encuentra en los siguientes formatos:

Como transparencias en PDF.
Como libro interactivo en IHaskell sobre Jupyter.
Como vídeo de clase.

6. Bibliografía

F. Rabhi y G. Lapalme. Algorithms: A functional programming approach.
- Cap. 5.8: Heaps
Functional heap - Leftist tree.