-- |
-- Module      : Conjunto
-- Description : TAD de los conjuntos.
-- License     : Creative Commons
-- Maintainer  : José A. Alonso
-- 
-- TAD (tipo abstracto de datos) de los conjuntos.
--
-- Este módulo contiene el código del TAD de los conjuntos
-- estudiado en el <http://bit.ly/1WYZzmW tema 17> del curso.

module I1M.Conjunto
  (Conj,
   vacio,     -- Conj a                       
   esVacio,   -- Conj a -> Bool               
   pertenece, -- Ord a => a -> Conj a -> Bool  
   inserta,   -- Ord a => a -> Conj a -> Conj a
   elimina    -- Ord a => a -> Conj a -> Conj a
  ) where

-- | Tipo de dato de los conjuntos.
newtype Conj a = Cj [a]
  deriving Eq

-- Procedimiento de escritura de los conjuntos.
instance (Show a) => Show (Conj a) where
  showsPrec _ (Cj s) = showConj s 

showConj :: Show a => [a] -> String -> String
showConj []     cad = showString "{}" cad
showConj (x:xs) cad = showChar '{' (shows x (showl xs cad))
  where showl []     cs = showChar '}' cs
        showl (y:ys) cs = showChar ',' (shows y (showl ys cs))

-- En los ejemplos se usará el siguiente conjunto.
-- 
-- > ghci> c1
-- > {0,1,2,3,5,7,9}
-- c1 :: Conj Int
-- c1 = foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0]

-- | vacio es el conjunto vacío. Por ejemplo,
-- 
-- > ghci> vacio
-- > {}
vacio :: Conj a                         
vacio = Cj []

-- | (esVacio c) se verifica si c es el conjunto vacío. Por ejemplo, 
-- 
-- > λ> esVacio (foldr inserta vacio [2,5])
-- > False
-- > λ> esVacio vacio
-- > True
esVacio :: Conj a -> Bool                
esVacio (Cj xs) = null xs

-- | (pertenece x c) se verifica si x pertenece al conjunto c. Por ejemplo, 
-- 
-- > λ> let c1 = foldr inserta vacio [2,5,3,2]
-- > λ> pertenece 3 c1
-- > True
-- > λ> pertenece 4 c1
-- > False
pertenece :: Ord a => a -> Conj a -> Bool 
pertenece x (Cj s) = x `elem` takeWhile (<= x) s

-- | (inserta x c) es el conjunto obtenido añadiendo el elemento x al
-- conjunto c. Por ejemplo,
-- 
-- > λ> let c1 = foldr inserta vacio [2,5,3,2]
-- > λ> c1
-- > {2,3,5}
-- > λ> inserta 3 c1
-- > {2,3,5}
-- > λ> inserta 4 c1
-- > {2,3,4,5}
inserta :: Ord a => a -> Conj a -> Conj a
inserta x (Cj s) = Cj (agrega x s)
  where agrega x' []                    = [x']                
        agrega x' s'@(y:ys) | x' > y    = y : agrega x' ys
                            | x' < y    = x' : s'
                            | otherwise = s'

-- | (elimina x c) es el conjunto obtenido eliminando el elemento x
-- del conjunto c. Por ejemplo,
-- 
-- > λ> let c1 = foldr inserta vacio [2,5,3,2]
-- > λ> c1
-- > {2,3,5}
-- > λ> elimina 3 c1
-- > {2,5}
-- > λ> elimina 7 c1
-- > {2,3,5}
elimina :: Ord a => a -> Conj a -> Conj a
elimina x (Cj s) = Cj (elimina' x s)
  where elimina' _ []                    = []
        elimina' x' s'@(y:ys') | x' > y    = y : elimina' x' ys'
                               | x' < y    = s'
                               | otherwise = ys'