I1M 0.1.0 → 0.2.0
raw patch · 3 files changed
+47/−46 lines, 3 filesdep ~QuickCheckdep ~arraydep ~tastyPVP ok
version bump matches the API change (PVP)
Dependency ranges changed: QuickCheck, array, tasty, tasty-hunit, tasty-quickcheck
API changes (from Hackage documentation)
Files
- I1M.cabal +8/−8
- README.org +1/−1
- src/I1M/ArbolBin.hs +38/−37
I1M.cabal view
@@ -1,13 +1,13 @@ cabal-version: 1.12 --- This file has been generated from package.yaml by hpack version 0.34.4.+-- This file has been generated from package.yaml by hpack version 0.37.0. -- -- see: https://github.com/sol/hpack ----- hash: 4fd28f1a2eef1321ab46d1954bebafddee5c13953a15ccd3e136f9d9b55a714c+-- hash: 9e8c919932f4f453f24e73fc45df5ec84ed851e907d393cf4a159c7c03f88028 name: I1M-version: 0.1.0+version: 0.2.0 synopsis: Code for the Haskell course taught at the University of Seville. description: En este paquete se encuentra los códigos de las librerías desarrolladas en el curso de@@ -57,8 +57,8 @@ src ghc-options: -Wall build-depends:- QuickCheck >=2.9.2 && <2.14.3- , array >=0.5.0 && <0.5.5+ QuickCheck >=2.9.2 && <2.15.1+ , array >=0.5.0 && <0.5.8 , base >=4.7 && <5 default-language: Haskell2010 @@ -81,7 +81,7 @@ build-depends: I1M , base >=4.7 && <5- , tasty >=0.11 && <1.3- , tasty-hunit >=0.9 && <0.10.1- , tasty-quickcheck >=0.8 && <0.10.2+ , tasty >=0.11 && <1.5.1+ , tasty-hunit >=0.9 && <0.10.3+ , tasty-quickcheck >=0.8 && <0.11 default-language: Haskell2010
README.org view
@@ -1,7 +1,7 @@ En este repositorio se encuentra el código en Haskell de las librerías desarrolladas y usadas en el curso de [[https://jaalonso.github.io/cursos/i1m/][Informática de 1º del Grado en Matemáticas]] de la Universidad de Sevilla.-+ La documentación se puede consultar [[http://jaalonso.github.io/I1M/][aquí]]. Las librerías incluidas son:
src/I1M/ArbolBin.hs view
@@ -3,19 +3,19 @@ -- Description : TAD de los árboles binarios de búsqueda. -- License : Creative Commons -- Maintainer : José A. Alonso--- +-- -- == TAD (tipo abstracto de datos) de los árboles binarios de búsqueda. -- -- Este módulo contiene el código del TAD de los árboles binarios -- estudiado en el <http://bit.ly/1F5RFgF tema 19> del curso.--- +-- -- Un árbol binario de búsqueda (ABB) es un árbol binario tal que el -- valor de cada nodo es mayor que los valores de su subárbol izquierdo -- y es menor que los valores de su subárbol derecho y, además, ambos -- subárboles son árboles binarios de búsqueda. Por ejemplo, al -- almacenar los valores de [2,3,4,5,6,8,9] en un ABB se puede obtener--- los siguientes ABB: --- +-- los siguientes ABB:+-- -- > 5 5 -- > / \ / \ -- > / \ / \@@ -24,19 +24,21 @@ -- > 4 8 2 4 6 9 -- > / \ -- > 3 9--- +-- -- El objetivo principal de los ABB es reducir el tiempo de acceso a los--- valores. +-- valores. -- -- En los ejemplos se usarán los siguientes ABB:--- +-- -- > abb1, abb2 :: ABB Int -- > abb1 = crea (reverse [5,2,6,4,8,3,9]) -- > abb2 = foldr inserta vacio (reverse [5,2,4,3,8,6,7,10,9,11]) +{-# OPTIONS_GHC -fno-warn-incomplete-uni-patterns #-}+ module I1M.ArbolBin (ABB,- vacio, -- ABB + vacio, -- ABB inserta, -- (Ord a,Show a) => a -> ABB a -> ABB a elimina, -- (Ord a,Show a) => a -> ABB a -> ABB a crea, -- (Ord a,Show a) => [a] -> ABB a@@ -67,51 +69,51 @@ -- abb2 = foldr inserta vacio (reverse [5,2,4,3,8,6,7,10,9,11]) -- | vacio es el ABB vacío. Por ejemplo,--- +-- -- > ghci> vacio -- > - vacio :: ABB a vacio = Vacio -- | (pertenece v' a) se verifica si v' es el valor de algún nodo del ABB--- a. Por ejemplo, --- +-- a. Por ejemplo,+-- -- > pertenece 3 abb1 == True -- > pertenece 7 abb1 == False pertenece :: (Ord a,Show a) => a -> ABB a -> Bool pertenece _ Vacio = False pertenece v' (Nodo v i d)- | v == v' = True + | v == v' = True | v' < v = pertenece v' i | otherwise = pertenece v' d -- pertenece requiere O(n) paso en el peor caso O(n) y O(log n) en el mejor,--- donde n es el número de nodos del ABB. +-- donde n es el número de nodos del ABB. -- | (inserta v a) es el árbol obtenido añadiendo el valor v al ABB a, si--- no es uno de sus valores. Por ejemplo, --- +-- no es uno de sus valores. Por ejemplo,+-- -- > ghci> inserta 7 abb1 -- > (5 (2 - (4 (3 - -) -)) (6 - (8 (7 - -) (9 - -)))) inserta :: (Ord a,Show a) => a -> ABB a -> ABB a inserta v' Vacio = Nodo v' Vacio Vacio-inserta v' (Nodo v i d) +inserta v' (Nodo v i d) | v' == v = Nodo v i d | v' < v = Nodo v (inserta v' i) d | otherwise = Nodo v i (inserta v' d) -- inserta requiere O(n) pasos en el peor caso y O(log n) en el mejor.- + -- | (crea vs) es el ABB cuyos valores son vs. Por ejemplo,--- +-- -- > ghci> crea [3,7,2] -- > (2 - (7 (3 - -) -)) crea :: (Ord a,Show a) => [a] -> ABB a crea = foldr inserta Vacio -- | (crea' vs) es el ABB de menor profundidad cuyos valores son los de--- la lista ordenada vs. Por ejemplo, --- +-- la lista ordenada vs. Por ejemplo,+-- -- > ghci> crea' [2,3,7] -- > (3 (2 - -) (7 - -)) crea' :: (Ord a,Show a) => [a] -> ABB a@@ -119,11 +121,11 @@ crea' vs = Nodo x (crea' l1) (crea' l2) where n = length vs `div` 2 l1 = take n vs- (x:l2) = drop n vs + (x:l2) = drop n vs -- | (elementos a) es la lista de los valores de los nodos del ABB en el--- recorrido inorden. Por ejemplo, --- +-- recorrido inorden. Por ejemplo,+-- -- > elementos abb1 == [2,3,4,5,6,8,9] -- > elementos abb2 == [2,3,4,5,6,7,8,9,10,11] elementos :: (Ord a,Show a) => ABB a -> [a]@@ -131,8 +133,8 @@ elementos (Nodo v i d) = elementos i ++ [v] ++ elementos d -- | (elimina v a) es el ABB obtenido borrando el valor v del ABB a. Por--- ejemplo, --- +-- ejemplo,+-- -- > ghci> abb1 -- > (5 (2 - (4 (3 - -) -)) (6 - (8 - (9 - -)))) -- > ghci> elimina 3 abb1@@ -144,43 +146,42 @@ -- > ghci> elimina 7 abb1 -- > (5 (2 - (4 (3 - -) -)) (6 - (8 - (9 - -)))) elimina :: (Ord a,Show a) => a -> ABB a -> ABB a-elimina _ Vacio = Vacio -elimina v' (Nodo v i Vacio) | v'==v = i +elimina _ Vacio = Vacio+elimina v' (Nodo v i Vacio) | v'==v = i elimina v' (Nodo v Vacio d) | v'==v = d elimina v' (Nodo v i d)- | v' < v = Nodo v (elimina v' i) d - | v' > v = Nodo v i (elimina v' d) + | v' < v = Nodo v (elimina v' i) d+ | v' > v = Nodo v i (elimina v' d) | otherwise = Nodo k i (elimina k d)- where k = menor d + where k = menor d -- | (menor a) es el mínimo valor del ABB a. Por ejemplo,--- +-- -- > menor abb1 == 2 menor :: Ord a => ABB a -> a menor (Nodo v Vacio _) = v-menor (Nodo _ i _) = menor i +menor (Nodo _ i _) = menor i menor Vacio = error "No tiene" -- | (menorTodos v a) se verifica si v es menor que todos los elementos -- del ABB a. menorTodos :: (Ord a, Show a) => a -> ABB a -> Bool-menorTodos _ Vacio = True +menorTodos _ Vacio = True menorTodos v a = v < minimum (elementos a) -- | (mayorTodos v a) se verifica si v es mayor que todos los elementos -- del ABB a. mayorTodos :: (Ord a, Show a) => a -> ABB a -> Bool-mayorTodos _ Vacio = True +mayorTodos _ Vacio = True mayorTodos v a = v > maximum (elementos a) -- | (valido a) se verifica si a es un ABB correcto. Por ejemplo,--- +-- -- > valido abb1 == True valido :: (Ord a, Show a) => ABB a -> Bool valido Vacio = True valido (Nodo v a b) = mayorTodos v a &&- menorTodos v b && + menorTodos v b && valido a && valido b-