I1M-0.1.0: Code for the Haskell course taught at the University of Seville.
LicenseCreative Commons
MaintainerJosé A. Alonso
Safe HaskellSafe-Inferred
LanguageHaskell2010

I1M.Monticulo

Description

TAD (tipo abstracto de datos) de los montículos.

Este módulo contiene el código del TAD de los montículos estudiado en el tema 20 del curso.

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 / / 2 6 3 8 9 7 es un montículo, pero 1 / / 3 6 4 2 9 7 no lo es.

Synopsis

Documentation

data Monticulo a Source #

El tipo de dato de los montículos.

Instances

Instances details
Ord a => Eq (Monticulo a) Source # 
Instance details

Defined in I1M.Monticulo

Methods

(==) :: Monticulo a -> Monticulo a -> Bool #

(/=) :: Monticulo a -> Monticulo a -> Bool #

Show a => Show (Monticulo a) Source # 
Instance details

Defined in I1M.Monticulo

vacio :: Ord a => Monticulo a Source #

vacio es el montículo vacío.

inserta :: Ord a => a -> Monticulo a -> Monticulo a Source #

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

ghci> inserta 3 (foldr inserta vacio [6,1,4,8])
M 1 2 
  (M 4 1 (M 8 1 Vacio Vacio) Vacio) 
  (M 3 1 (M 6 1 Vacio Vacio) Vacio)

menor :: Ord a => Monticulo a -> a Source #

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

menor (foldr inserta vacio [6,1,4,8])  ==  1
menor (foldr inserta vacio [7,5])      ==  5

resto :: Ord a => Monticulo a -> Monticulo a Source #

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

ghci> resto (foldr inserta vacio [6,1,4,8])
M 4 2 (M 8 1 Vacio Vacio) (M 6 1 Vacio Vacio)

esVacio :: Ord a => Monticulo a -> Bool Source #

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

valido :: Ord a => Monticulo a -> Bool Source #

(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 (foldr inserta vacio [6,1,4,8])    ==  True
valido (foldr inserta vacio [7,5])        ==  True
valido (M 3 5 (M 2 1 Vacio Vacio) Vacio)  ==  False