Elsdomgon en 16:47 26 dic 2021

2021-12-26T16:47:20Z

Mdelamor: Página creada con « -- I1M 2021-22: Relación 12 (7 de enero de 2022) -- Tipos de datos algebraicos: Árboles binarios. -- Departamento de Ciencias de la Computación…»

2021-12-19T18:16:45Z

Página creada con «<source lang='haskell'> -- I1M 2021-22: Relación 12 (7 de enero de 2022) -- Tipos de datos algebraicos: Árboles binarios. -- Departamento de Ciencias de la Computación…»

Página nueva

<source lang='haskell'>

-- I1M 2021-22: Relación 12 (7 de enero de 2022)
-- Tipos de datos algebraicos: Árboles binarios.
-- Departamento de Ciencias de la Computación e I.A.
-- Universidad de Sevilla
-- =====================================================================

-- ---------------------------------------------------------------------
-- Introducción --
-- ---------------------------------------------------------------------

-- En esta relación se presenta ejercicios sobre árboles binarios
-- definidos como tipos de datos algebraicos.
--
-- Los ejercicios corresponden al tema 9 que se encuentra en
-- http://www.cs.us.es/cursos/i1m/temas/tema-9.html

-- ---------------------------------------------------------------------
-- § Librerías auxiliares --
-- ---------------------------------------------------------------------

import Test.QuickCheck
import Control.Monad

-- ---------------------------------------------------------------------
-- Nota. En los siguientes ejercicios se trabajará con los árboles
-- binarios definidos como sigue
-- data Arbol a = H a
-- | N a (Arbol a) (Arbol a)
-- deriving (Show, Eq)
-- Por ejemplo, el árbol
-- 9
-- / \
-- / \
-- 3 7
-- / \
-- 2 4
-- se representa por
-- N 9 (N 3 (H 2) (H 4)) (H 7)
-- ---------------------------------------------------------------------

data Arbol a = H a
| N a (Arbol a) (Arbol a)
deriving (Show, Eq)

-- ---------------------------------------------------------------------
-- Ejercicio 1.1. Definir la función
-- nHojas :: Arbol a -> Int
-- tal que (nHojas x) es el número de hojas del árbol x. Por ejemplo,
-- nHojas (N 9 (N 3 (H 2) (H 4)) (H 7)) == 3
-- ---------------------------------------------------------------------

nHojas :: Arbol a -> Int
nHojas = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 1.2. Definir la función
-- nNodos :: Arbol a -> Int
-- tal que (nNodos x) es el número de nodos del árbol x. Por ejemplo,
-- nNodos (N 9 (N 3 (H 2) (H 4)) (H 7)) == 2
-- ---------------------------------------------------------------------

nNodos :: Arbol a -> Int
nNodos = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 1.3. Comprobar con QuickCheck que en todo árbol binario el
-- número de sus hojas es igual al número de sus nodos más uno.
-- ---------------------------------------------------------------------

-- La propiedad es
prop_nHojas :: Arbol Int -> Bool
prop_nHojas x = undefined

-- La comprobación es

-- ---------------------------------------------------------------------
-- Ejercicio 2.1. Definir la función
-- profundidad :: Arbol a -> Int
-- tal que (profundidad x) es la profundidad del árbol x. Por ejemplo,
-- profundidad (N 9 (N 3 (H 2) (H 4)) (H 7)) == 2
-- profundidad (N 9 (N 3 (H 2) (N 1 (H 4) (H 5))) (H 7)) == 3
-- profundidad (N 4 (N 5 (H 4) (H 2)) (N 3 (H 7) (H 4))) == 2
-- ---------------------------------------------------------------------

profundidad :: Arbol a -> Int
profundidad = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 2.2. Comprobar con QuickCheck que para todo árbol biario
-- x, se tiene que
-- nNodos x <= 2^(profundidad x) - 1
-- ---------------------------------------------------------------------

-- La propiedad es
prop_nNodosProfundidad :: Arbol Int -> Bool
prop_nNodosProfundidad x = undefined

-- La comprobación es

-- ---------------------------------------------------------------------
-- Ejercicio 3.1. Definir la función
-- preorden :: Arbol a -> [a]
-- tal que (preorden x) es la lista correspondiente al recorrido
-- preorden del árbol x; es decir, primero visita la raíz del árbol, a
-- continuación recorre el subárbol izquierdo y, finalmente, recorre el
-- subárbol derecho. Por ejemplo,
-- preorden (N 9 (N 3 (H 2) (H 4)) (H 7)) == [9,3,2,4,7]
-- ---------------------------------------------------------------------

preorden :: Arbol a -> [a]
preorden = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 3.2. Comprobar con QuickCheck que la longitud de la lista
-- obtenida recorriendo un árbol en sentido preorden es igual al número
-- de nodos del árbol más el número de hojas.
-- ---------------------------------------------------------------------

-- La propiedad es
prop_length_preorden :: Arbol Int -> Bool
prop_length_preorden x = undefined

-- La comprobación es

-- ---------------------------------------------------------------------
-- Ejercicio 3.3. Definir la función
-- postorden :: Arbol a -> [a]
-- tal que (postorden x) es la lista correspondiente al recorrido
-- postorden del árbol x; es decir, primero recorre el subárbol
-- izquierdo, a continuación el subárbol derecho y, finalmente, la raíz
-- del árbol. Por ejemplo,
-- postorden (N 9 (N 3 (H 2) (H 4)) (H 7)) == [2,4,3,7,9]
-- ---------------------------------------------------------------------

postorden :: Arbol a -> [a]
postorden = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 3.4. Definir, usando un acumulador, la función
-- preordenIt :: Arbol a -> [a]
-- tal que (preordenIt x) es la lista correspondiente al recorrido
-- preorden del árbol x; es decir, primero visita la raíz del árbol, a
-- continuación recorre el subárbol izquierdo y, finalmente, recorre el
-- subárbol derecho. Por ejemplo,
-- preordenIt (N 9 (N 3 (H 2) (H 4)) (H 7)) == [9,3,2,4,7]
--
-- Nota: No usar (++) en la definición
-- ---------------------------------------------------------------------

preordenIt :: Arbol a -> [a]
preordenIt x = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 3.5. Comprobar con QuickCheck que preordenIt es equivalente
-- a preorden.
-- ---------------------------------------------------------------------

-- La propiedad es
prop_preordenIt :: Arbol Int -> Bool
prop_preordenIt x = undefined

-- La comprobación es

-- ---------------------------------------------------------------------
-- Ejercicio 4.1. Definir la función
-- espejo :: Arbol a -> Arbol a
-- tal que (espejo x) es la imagen especular del árbol x. Por ejemplo,
-- espejo (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 7) (N 3 (H 4) (H 2))
-- ---------------------------------------------------------------------

espejo :: Arbol a -> Arbol a
espejo = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 4.2. Comprobar con QuickCheck que para todo árbol x,
-- espejo (espejo x) = x
-- ---------------------------------------------------------------------

-- La propiedad es
prop_espejo :: Arbol Int -> Bool
prop_espejo x = undefined

-- La comprobación es

-- ---------------------------------------------------------------------
-- Ejercicio 4.3. Comprobar con QuickCheck que para todo árbol binario
-- x, se tiene que
-- reverse (preorden (espejo x)) = postorden x
-- ---------------------------------------------------------------------

-- La propiedad es
prop_reverse_preorden_espejo :: Arbol Int -> Bool
prop_reverse_preorden_espejo x = undefined

-- La comprobación es

-- ---------------------------------------------------------------------
-- Ejercicio 4.4. Comprobar con QuickCheck que para todo árbol x,
-- postorden (espejo x) = reverse (preorden x)
-- ---------------------------------------------------------------------

-- La propiedad es
prop_recorrido :: Arbol Int -> Bool
prop_recorrido x = undefined

-- La comprobación es

-- ---------------------------------------------------------------------
-- Ejercicio 5.1. La función take está definida por
-- take :: Int -> [a] -> [a]
-- take 0 = []
-- take (n+1) [] = []
-- take (n+1) (x:xs) = x : take n xs
--
-- Definir la función
-- takeArbol :: Int -> Arbol a -> Arbol a
-- tal que (takeArbol n t) es el subárbol de t de profundidad n. Por
-- ejemplo,
-- takeArbol 0 (N 9 (N 3 (H 2) (H 4)) (H 7)) == H 9
-- takeArbol 1 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 3) (H 7)
-- takeArbol 2 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)
-- takeArbol 3 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)
-- ---------------------------------------------------------------------

takeArbol :: Int -> Arbol a -> Arbol a
takeArbol = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 5.2. Comprobar con QuickCheck que la profundidad de
-- (takeArbol n x) es menor o igual que n, para todo número natural n y
-- todo árbol x.
-- ---------------------------------------------------------------------

-- La propiedad es
prop_takeArbol:: Int -> Arbol Int -> Property
prop_takeArbol n x = undefined

-- La comprobación es

-- ---------------------------------------------------------------------
-- Ejercicio 6.1. La función
-- repeat :: a -> [a]
-- está definida de forma que (repeat x) es la lista formada por
-- infinitos elementos x. Por ejemplo,
-- repeat 3 == [3,3,3,3,3,3,3,3,3,3,3,3,3,...
-- La definición de repeat es
-- repeat x = xs where xs = x:xs
--
-- Definir la función
-- repeatArbol :: a -> Arbol a
-- tal que (repeatArbol x) es es árbol con infinitos nodos x. Por
-- ejemplo,
-- takeArbol 0 (repeatArbol 3) == H 3
-- takeArbol 1 (repeatArbol 3) == N 3 (H 3) (H 3)
-- takeArbol 2 (repeatArbol 3) == N 3 (N 3 (H 3) (H 3)) (N 3 (H 3) (H 3))
-- ---------------------------------------------------------------------

repeatArbol :: a -> Arbol a
repeatArbol x = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 6.2. La función
-- replicate :: Int -> a -> [a]
-- está definida por
-- replicate n = take n . repeat
-- es tal que (replicate n x) es la lista de longitud n cuyos elementos
-- son x. Por ejemplo,
-- replicate 3 5 == [5,5,5]
--
-- Definir la función
-- replicateArbol :: Int -> a -> Arbol a
-- tal que (replicate n x) es el árbol de profundidad n cuyos nodos son
-- x. Por ejemplo,
-- replicateArbol 0 5 == H 5
-- replicateArbol 1 5 == N 5 (H 5) (H 5)
-- replicateArbol 2 5 == N 5 (N 5 (H 5) (H 5)) (N 5 (H 5) (H 5))
-- ---------------------------------------------------------------------

replicateArbol :: Int -> a -> Arbol a
replicateArbol n = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 6.3. Comprobar con QuickCheck que el número de hojas de
-- (replicateArbol n x) es 2^n, para todo número natural n
--
-- Nota. Al hacer la comprobación limitar el tamańo de las pruebas como
-- se indica a continuación
-- quickCheckWith (stdArgs {maxSize=7}) prop_replicateArbol
-- ---------------------------------------------------------------------

-- La propiedad es
prop_replicateArbol :: Int -> Int -> Property
prop_replicateArbol n x = undefined

-- La comprobación es

-- ---------------------------------------------------------------------
-- Ejercicio 7.1. Definir la función
-- mapArbol :: (a -> a) -> Arbol a -> Arbol a
-- tal que (mapArbol f x) es el árbol obtenido aplicándole a cada nodo de
-- x la función f. Por ejemplo,
-- ghci> mapArbol (*2) (N 9 (N 3 (H 2) (H 4)) (H 7))
-- N 18 (N 6 (H 4) (H 8)) (H 14)
-- ---------------------------------------------------------------------

mapArbol :: (a -> a) -> Arbol a -> Arbol a
mapArbol = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 7.2. Comprobar con QuickCheck que
-- (mapArbol (1+)) . espejo = espejo . (mapArbol (1+))
-- ---------------------------------------------------------------------

-- La propiedad es
prop_mapArbol_espejo :: Arbol Int -> Bool
prop_mapArbol_espejo x = undefined

-- La comprobación es

-- ---------------------------------------------------------------------
-- Ejercicio 7.3. Comprobar con QuickCheck que
-- (map (1+)) . preorden = preorden . (mapArbol (1+))
-- ---------------------------------------------------------------------

-- La propiedad es
prop_map_preorden :: Arbol Int -> Bool
prop_map_preorden x = undefined

-- La comprobación es

-- ---------------------------------------------------------------------
-- Nota. Para comprobar propiedades de árboles con QuickCheck se
-- utilizará el siguiente generador.
-- ---------------------------------------------------------------------

instance Arbitrary a => Arbitrary (Arbol a) where
arbitrary = sized arbol
where
arbol 0 = liftM H arbitrary
arbol n | n>0 = oneof [liftM H arbitrary,
liftM3 N arbitrary subarbol subarbol]
where subarbol = arbol (div n 2)
arbol _ = error "Imposible"

</source>

Relación 12 - Historial de revisiones

Elsdomgon en 16:47 26 dic 2021

Mdelamor: Página creada con « -- I1M 2021-22: Relación 12 (7 de enero de 2022) -- Tipos de datos algebraicos: Árboles binarios. -- Departamento de Ciencias de la Computación…»