module Ctrol2 where

----------------------------------------------------------------
-- PROGRAMACIÓN DECLARATIVA P. Funcional - Control2  29 . 5 . 2k
----------------------------------------------------------------


-- 1. Dado el programa Haskell:

data MArbol a =  Vacio | Nodo a [MArbol a] 

k :: Int -> Int -> Int
k n m = if n<m then 0 else 1 + k (n-1) m 

mapmap :: [(a -> b)] -> [a] -> [[b]] 

mapmap [] _ = []
mapmap (f:lf) l  =  (map f l) : mapmap lf l
 

-- (a) Indicar el tipo de f en la siguiente expresión. Justificar
--     brevemente la respuesta.	
--
--	f ( Nodo 5 (f Vacio (\n -> n) ) ) (+2)
--
--      f :: MArbol Int   ->   (Int -> Int)   ->   [MArbol Int]
--           
--           ----------       ------------         ----------
--         tipo de Nodo_ _     tipo de (+2)         salida: tipo
--                                                   del segundo 
--                                                   argumento de
--                                                   Nodo
--
--      Nota: También vale MArbol a en vez de MArbol Int
--
--
-- (b) Indicar a qué se reduce la siguiente expresión. Justificar
--     brevemente la respuesta.
--
--	mapmap [k 2] [x | x <- [2..], x<6]
--
--      ---> (map (k 2) [x | x <- [2..], x<6]):[]  // 2da regla de mapmap
--
--      ---> [ map (k 2) [2,3,4,5] ]               // significado de [x|x<-...]
--
--      ---> [ [k 2 2, k 2 3, k 2 4, k 2 5] ]      // significado de map
--
--      ---> [ [if 2<2..., if 2<3..., ... ] ]      // regla de k
--
--      ---> [ [1+k 1 2, 0, 0, 0] ]                // "then" y "else" del "if"
--
--      ---> [ [1+if 1<2..., 0, 0, 0] ]            // regla de k
--
--      ---> [ [1+0, 0, 0, 0] ]
--
--      ---> [ [1, 0, 0, 0] ]
--



-- (c) Implementar la función mapMA que funiona como map, pero sobre
--     datos de tipo MArbol. Es decir, debe aplicar una función a
--     cada uno de los elementos de un dato Marbol.
		
mapMA :: (a -> b) -> MArbol a -> MArbol b

mapMA _ Vacio = Vacio
mapMA f (Nodo x l) = Nodo (f x) (map (mapMA f) l) 

-- Sin usar map:
--
-- mapMA f (Nodo x l) = Nodo (f x) [ mapMA f a | a <- l ]



-- 2. Implementar en Haskell la función menorStr para comparar dos
--    strings según un carácter dado como argumento,  de forma que
--    un string es menor que otro si contiene menos veces al carácter.
--    Por ejemplo, "casa" es menor que "casos" con respecto al
--    carácter 's', y mayor con respecto al carácter 'a'. Poner un
--    ejemplo de llamada a una función de ordenación de orden
--    superior, en la que se use menorStr para ordenar una lista de
--    strings. 


menorStr :: Char -> String -> String -> Bool
menorStr c s1 s2 = (veces c s1) <= (veces c s2)

veces :: Char -> String -> Int
veces _ [] = 0
veces c (h:t) = veces c t + (if c == h then 1 else 0)

-- ordOS :: (a -> a -> Bool) -> [a] -> [a]
--
-- Ejemplo de llamada, para ordenar ["casa", "casos", "maraca", "loro"]
-- según el número de a's de los estrings:
--
--   > ordOS (menorStr 'a') ["casa", "casos", "maraca", "loro"]
--
-- Salida: ["loro", "casos", "casa", "maraca", ]
--

-- 3. Representamos como Cm,n el número combinatorio "m sobre n",
--    con 0 <= m <= n. Se llama fila m-ésima, o m-fila, a la lista
--    formada por los valores Cm,0 , Cm,1 , ..., Cm,m , y se llama
--    triángulo de Pascal al conjunto de todas las filas, ordenadas
--    según m. En las filas se cumple que Cm,0  =  1, Cm,n = 1 si
--    m = n, y Cm,n  = Cm-1,n + Cm-1,n-1  en otros casos. 
--
-- (a) Implementar una función Haskell que obtiene el triángulo de
--     Pascal.  

fila :: Integer -> [Integer]

fila 0 = [1]
fila m = 1 : sumas (fila (m-1))

sumas :: [Integer] -> [Integer]           -- Calculo de una fila
sumas (x:y:t) = x+y : sumas (y:t)         -- a partir de la anterior
sumas _ = [1]

triPas1,triPas2 :: [[Integer]]            -- Veamos dos versiones:

triPas1 = [fila i | i <- [0..] ]             -- no tiene en cuenta las
                                             -- filas calculadas

triPas2 = [1] : [1:sumas f | f <- triPas2]   -- sí las tiene en cuenta
                                             -- (mas eficiente, y sin "fila")

--
-- Nota: todo puede implementarse si usar notación especial de listas:
--
-- triPas1 = tp 0 where tp n = fila n : tp (n+1)
--
-- triPas2 = tp [1] where tp f =  f : tp ( 1: sumas f)  
-- 
                      
-- (b) Usando el triángulo de Pascal, implementar una función Haskell
--     que obtiene la fila no trivial en la que se encuentra un valor
--     dado c > 1 (la fila trivial es la fila c-ésima, cuyo segundo
--     elemento es c). Se supone que tal fila existe.
--

filaDe :: Integer -> [Integer]

filaDe c =  busca c colaPas
  where  
    _ : colaPas         = triPas2
    busca c ((1:m:f):t) = if (c /= m) && (elem c f)  
                             then (1:m:f)
                             else busca c t


--
-- Opcional (solo cuenta si se aprueba)
--	
--    Implementar en Lisp (Common Lisp) la función filter.	
--
-- (defun filter (p l)
--               (if (null l)
--                   nil
--                   (if (funcall p (car l)) 
--                       (cons (car l) (filter p (cdr l)))
--                       (filter p (cdr l))
--                   )
--               )
-- )
--