module EjemplosTemas where

---------------------------------
-- Tema 5
---------------------------------



fact :: Integer -> Integer

fact 0 = 1
fact n = n * fact (n-1)


member :: (Eq a) => a -> [a] -> Bool    -- predef. como elem

member x []    = False
member x (h:t) = x == h || member x t


append :: [a] -> [a] -> [a]             -- predef. como ++

append [] l    = l
append (h:t) l = h : (append t l)


ifthenelse :: Bool -> a -> a -> a 

ifthenelse True  x _ = x
ifthenelse False _ y = y

ultimo :: [a] -> a
ultimo [x] = x
ultimo (_:h) = ultimo h


data Nat = Cero | Succ Nat deriving Show

suma :: Nat -> Nat -> Nat 
suma Cero x     = x
suma (Succ x) y = Succ (suma x y)



inc,doble :: Integer -> Integer 
-- inc n = n + 1
-- doble x = x + x

estaCero :: [Integer] -> Bool
-- estaCero l = elem 0 l    -- elem = member

inc = (1+)         
doble = (2*)

estaCero = elem 0



data Persona a b = Clave a | Nombre b | Desconocida

informa x = case x of 	
	    Clave c  -> "No hay nombre"
            Nombre n -> n
  	    _        -> "Desconocida"



selecc :: [Int] -> ([Int], [Int], [Int])

selecc [] = ([],[],[])  
selecc (h:t)    | h `mod` 2 == 0  = (h:l1, l2, l3) 
          	| h `mod` 3 == 0  = (l1, h:l2, l3) 
         	| h `mod` 5 == 0  = (l1, l2, h:l3) 
          	| otherwise       = (l1, l2, l3)
       		where (l1,l2,l3) = selecc t 





qs :: (Ord a)=>[a] -> [a]
qs [] = []
qs (h:t) = qs s1 ++ (h: (qs s2))
		where (s1, s2) = partir h t

partir :: (Ord a) => a -> [a] -> ([a], [a])
partir _ [] = ([], [])
partir x (h:t) = let (l1,l2) = partir x t in
				if h <= x then (h:l1, l2)						
                                          else (l1, h:l2)


treesort :: (Ord a) => [a] -> [a]

treesort l = aLista (aArbol l)

data Arbol a = Vacio | Nodo (Arbol a) a (Arbol a) deriving Show

aArbol :: (Ord a) => [a] -> Arbol a
aArbol [] = Vacio
aArbol (h:t) = inserta h (aArbol t)

aLista :: Arbol a -> [a] 
aLista Vacio = []
aLista (Nodo i x d) = aLista i ++ x: aLista d

inserta :: (Ord a) => a -> Arbol a -> Arbol a
inserta x Vacio                  = Nodo Vacio x Vacio
inserta x (Nodo i r d)	| x <= r = Nodo (inserta x i) r d	
                	| x > r  = Nodo i r (inserta x d)




-----------
-- Tema 6
-----------

-- map, filter, foldr y foldl son predefinidas


---------------------------------------------------------------
-- Ordenación por inserción de O. S.


ordInsOS :: (a -> a -> Bool) -> [a] -> [a]
ordInsOS _ [] = []
ordInsOS p (h:t) = insOS p (ordInsOS p t) h

insOS :: (a -> a -> Bool) -> [a] -> a -> [a]
insOS _ []    x = [x]
insOS p (h:t) x = if  (x `p` h) then x:h:t 
				else h:(insOS p t x)

--------------------------------------------------------------
-- Una función que fabrica una lista de funciones (rara)

listfun :: Int -> [Int ->Int]

listfun 0 = []
listfun n = (\x -> abs (n-x)) : listfun (n-1) 


-------------------------------------------------------------
-- nsimo y cuadrados

nsimo:: Integer -> [a] -> a
nsimo 1 (h:_) = h
nsimo n (_:t) = nsimo (n-1) t

cuadrados :: Integer -> [Integer]

cuadrados n = n*n : cuadrados (n+1)


------------------------------------------------------------
-- vacio? (para árboles)

vacio :: Arbol a -> Bool

vacio Vacio = True
vacio (Nodo _ _ _) = False


------------------------------------------------------------
-- Cribar

criba :: [Integer] -> [Integer]

criba (h:t) = h : criba (filter (\x->x`mod`h > 0) t)
criba [] = []


------------------------------------------------------------
-- Descomponer en primos

desc :: Integer -> [Integer] -> [(Integer,Integer)]

desc n l = cambia (des n l)  -- cambia: pone en forma de pares

des :: Integer -> [Integer] -> [Integer]
des 1 _     = []
des _ []    = error "Faltan primos"
des n (h:t) = if n `mod` h == 0 
              then h: (des (n `div` h) (h:t) )
              else des n t      

cambia :: [Integer] -> [(Integer,Integer)]
cambia [n] = [(n,1)]
cambia (h:t) = let (m,k):r = cambia t
               in  if h == m then (m,k+1):r
                             else (h,1):(m,k):r

descTodos :: Integer -> [(Integer,Integer)]

descTodos n = desc n (criba (desde 2))
		where desde n = n:desde(n+1)



-- qs de O.S.

qsort :: (a-> a -> Bool) -> [a] -> [a]

qsort _ []    = []
qsort m (h:t) = qsort m [x | x<-t, x `m` h] 	
		++ 
		h:qsort m [x | x<-t, not (x `m` h)]