module Control2 where

-- -----------------------------------------------------------------------------------
-- -------------- SOLUCIONES CONTROL 2 PROGR. FUNCIONAL (24.5.2001) ------------------
-- -----------------------------------------------------------------------------------

-- 1 Dado el programa Haskell:

data Conex a = Sucesores a [a]
type Grafo a = [ Conex a ]

g :: Int -> (Int -> Int) -> Int
g n h = (h n) * (h (n-1))
		
h :: Int -> Int -> Int
h x y = 2*x - y


-- (a) Indicar el tipo de f en la siguiente expresión. Justificar brevemente la respuesta.
--
--	(f (g 5) ) ++ "fin"
--
--      f  ::   ( (Int -> Int) -> Int )  ->  String
--               \___________________/       \____/
--                
--                Tipo de (g 5)              Tipo de los argumentos de ++
--
--


-- (b) Indicar a qué se reduce la siguiente expresión. Justificar brevemente la respuesta.
--
--	(g 5) (h 1)       -- reescribimos con la regla de g: n<-5, h<-(h 1) 
--  
--      ------->  ((h 1) 5) * ((h 1) 4)
--              = (h 1 5) * (h 1 4)            -- ... y con las reglas de h
--      ------->  (2*1 - 5) * (2*1 - 4)
--      ------->  (-3) * (-2)
--      ------->  6 
--

-- (c) Implementar una función Haskell que renombra los nodos de un grafo, dando el grafo 
--     según el tipo anterior. Por ejemplo, dado el grafo 
--    
--         [Sucesores 1 [2, 3], Sucesores 2 [3], Sucesores 3 [3,4], Sucesores 4 [] ]
--
--     y la función  (\x -> x + 1) , quedaría el grafo  
--
--        [Sucesores 0 [1, 2], Sucesores 1 [2], Sucesores 2 [2,3], Sucesores 3 [] ]. 
--     
--     La función debe servir para cualquier grafo y cualquier función de renombramiento.
		

renombra :: (a -> b) -> Grafo a -> Grafo b

renombra _ [] =  []

renombra f ((Sucesores x l):t) = (Sucesores (f x) (map f l)) : renombra f t 




-- 2 Un grupo de n espías, numerados del 1 al n, han recogido un trozo de mensaje (un 
--   string). Para descifrar el mensaje, se usa un algoritmo (una función) que obtiene 
--   un string a partir de otro, y su manual de instrucciones dice: Si mi es el mensaje 
--   del espía nº i:
--
--   . Descifra el mensaje mn y produce dn,
--   . Une mi a di+1 (midi+1) y produce con el resultado di, para 1 £ i  £ n-1,
--   . El mensaje descifrado será d1.
--
--  a) Hacer un programa Haskell que descifre mensajes. Deberá servir para distintos 
--     mensajes y distintos descifradores cuyo uso se ajuste a las instrucciones dadas.
--

descifra :: (String -> String) -> [String] -> String
descifra _ []    = []
descifra f (h:t) = f (h++(descifra f t))


--  b) Poner un ejemplo de llamada para el descifrar con el agoritmo "quita primer 
--     carácter e invierte". Es decir, con los strings "tai" , "er" y "psu"  saldría  
--     "rusia".	  
--
--         descifra (\ (h:t) -> reverse t ) ["tai", "er", "psu"]
--
--     O bien, si tenemos implemetada aux como
--  

aux :: String -> String
aux (h:t) = reverse t

--
--         descifra aux ["tai", "er", "psu"]


--  c) ¿Cómo se puede conseguir el mismo efecto de la función pedida con una llamada a 
--     la función foldr?. 	
--
--     La llamada anterior con foldr en vez de descifra sería:
--
--         foldr (\s r -> aux (s++r)) [] ["tai", "er", "psu"]   
--
--
--     O bién la implementación de descifra con foldr
--
descif :: (String -> String) -> [String] -> String
descif f l  = foldr (\s r -> f (s++r) [] l



{-
Opcional: puede hacer en lugar del ejercicio 1(c): 
          Implementar en Lisp (Common Lisp) la función inversa de una lista

; version normal, usando append:

(defun inversa (l)
       (if (null l)
           nil
           (append (inversa (cdr l))  (list (car l)))
       )
)

; version eficiente, usando un parametro acumulador

(defun reverse (l) (aux l nil))

defun aux (l v)
      (if (null l)
          v
          (aux (cdr l) (cons (car l) v))
      )
)


-}