Práctica 1 (pre 2010, Paradigmas)

Definicion de Tipos y Currificacion

Ejercicio 1

Dado el siguiente programa:

xs = [1,2,3]::[Float]
ys = map (+) xs

¿Cual es el tipo de ys? (la idea aca es que lo calculen “a ojo”)

Respuesta: [Integer -> Integer]

(En realidad es [Float -> Float] porque xs está definido como [Float], si xs estuviese definido como xs = [1,2,3] sí sería [Integer -> Integer] porque Haskell asume que xs::[Integer]).

Ejercicio 2

Item I

Reescribir la expresion map f (map g xs) para que se utilice un solo llamado a la funcion map (se necesitara la funcion de composicion, (.)).

map (f . g) xs

Item II

Redifinir la siguiente funcion f xs = map (\x -> (x+1)/2) xs de modo que utilice composicion de operadores de manera similar al item anterior.

f xs = map ((/2) . (+1)) xs

Ejercicio 3

Item I

Definir la funcion curry, que dada una funcion de dos argumentos, devuelve su equivalente currificada.

curry ::(a -> b -> c) -> ((a, b) -> c)
curry f = \(x, y) -> f x y

Item II

Definir la funcion uncurry, que dada una funcion currificada de dos argumentos, devuelve su version no currificada equivalente. Es la inversa de la anterior.

uncurry :: ((a, b) -> c) -> (a -> b -> c)
uncurry f = \x y -> f(x,y)

Item III

¿Se podria definir una funcion curryN, que tome una funcion de un numero arbitrario de argumentos y devuelva su version currificada?

No se puede pues las tuplas no se pueden modificar dinamicamente.

Listas por Comprension

Ejercicio 4

¿Cual es el valor de esta expresion? [ x | x <- [1..4], y <- [x..5], (x+y) ‘mod‘ 2 == 0 ]

[1, 1, 1, 2, 2, 3, 3, 4]

Ejercicio 5

Una tripla pitagorica es una tripla (a,b,c) de enteros positivos tal que a2 + b2 = c2. La siguiente es una definicion de una lista (infinita) de triplas pitagoricas:

pitagorica :: [(Integer,Integer,Integer)]
pitagorica = [(a,b,c) | a <- [1..], b <-[1..], c <- [1..], a^2 + b^2 == c^2]

Explicar porque esta definicion no es muy util. Dar una definicion mejor.

Respuesta:

generar_n_3 = [(x, y, suma - x - y) | suma <- [0..], x <- [0..suma], y <- [0..suma - x]]

pitagorica :: [(Integer, Integer, Integer)]
pitagorica = [(x, y, z) | suma <- [1..], x <- [1..suma], y <- [1..suma - x], z <- [suma - x - y], x*x + y*y == z*z]

Ejercicio 6

Redefinir la siguiente funcion g, sin utilizar listas por comprension ni recursion explicita, y usando un subconjunto de las siguientes funciones: map, filter y foldr. Ademas, pueden utilizarse las funciones even, odd, length , reverse y (++).

g xs = [ y ++ reverse x | x <- xs, odd (length x), y <- xs, even (length y)]

Respuesta:

evens xs = filter (even.length) xs
odds xs = filter (odd.length) xs
revodds xs = map reverse (odds xs)
axb xs x = foldr ((:).(flip (++)) x) [] xs
g xs = foldr ((++).(axb (evens xs))) [] (revodds xs)

Modos de Evaluacion

Ejercicio 8

Generar la lista de los primeros mil numeros perfectos. Un numero natural n es perfecto sii la suma de sus divisores menores estrictos que el es igual a n. Ver de que forma se puede implementar usando evaluacion lazy y funciones de orden superior.

Respuesta:

divisores n = filter ((==0).(mod n)) [1..n-1]
perfectos n = take n ( filter f [1..] )
 where f x = x==sum (divisores x)

Lo mismo, pero hecho con listas por comprensión:

perfectos n = take n [x | x <- [1..], sum([y | y <- [1..x-1], x `mod` y == 0]) == x]

Alto Orden y Esquemas de recursion

Ejercicio 9

Item I

Definir la funcion genLista, que genera una lista de una cantidad dada de elementos, a partir de un elemento inicial y de una funcion de incremento entre los elementos de la lista. Dicha funcion de incremento, dado un elemento de la lista, devuelve el elemento siguiente.

genLista f a n = foldr (\x y -> if null y then [a] else y++[f (last y)]) [] [1..n]

Item II

Usando genLista, definir la funcion dh, que dado un par de numeros (el primero menor que el segundo), devuelve una lista de numeros consecutivos desde el primero hasta el segundo.

dh :: Int -> Int -> [Int]
dh a b = genLista (+1) a (b-a+1)

Ejercicio 10

i. Definir y dar el tipo del esquema de recursion foldNat sobre los naturales. Utilizar el tipo Integer de Haskell.
ii. Utilizando foldNat, definir la funcion potencia.

Respuesta
i.

foldNat :: (Integer -> b -> b) -> b -> Integer -> b
foldNat _ z 0 = z
foldNat f z n = f n (foldNat f z (n - 1))

ii.

potencia :: Integer -> Integer -> Integer
potencia b e = foldNat (\_ p -> b * p) 1 e

Ejercicio 11

i. Definir la función paraCada, que recibe dos números (un numero inicial i y otro final f), un valor v y una funcion g que dado un valor y un numero devuelve un valor. Dados esos parametros, paraCada devuelve la aplicacion sucesiva de g desde el numero final hasta el inicial: en cada paso, g se aplica al resultado de la evaluacion anterior y al predecesor del numero anterior. Esto se realiza hasta llegar a i. Inicialmente, g se aplica a v y a f.

Ejemplo:

paraCada 1 3 [] (flip (:)) devuelve [1, 2, 3] 

ii. Definir la funcion todos, que recibe una lista de elementos y una condicion sobre los elementos, y determina si todos los elementos de la lista cumplen con dicha condicion. Usar paraCada, length y (!!).

iii. Definir la funcion ninguno, que recibe una lista de elementos y una condicion sobre los elementos, y determina si ninguno de los elementos de la lista cumple con dicha condicion. Usar todos.

Respuesta:

i.

paraCada :: Int -> Int -> v -> (v -> Int -> v) -> v
paraCada i f v g = foldr (\x y -> g y x) v ([i..f])

ii.

todos :: [a] -> (a -> Bool) -> Bool
todos xs f = paraCada 0 ((length xs) - 1) True (\x y -> x && (f (xs !! y)))

iii.

ninguno :: [a] -> (a -> Bool) -> Bool
ninguno xs f = todos xs (not.f)

Ejercicio 12

i. Definir la funcion mapo, una version de map que toma una funcion de dos argumentos y una lista de pares de valores, y devuelve la lista de aplicaciones de la función a cada par.

ii. Definir la funcion mapo2, una version de mapo que toma una funcion currificada de dos argumentos y dos listas (de igual longitud), y devuelve una lista de aplicaciones de la funcion a cada elemento correspondiente a las dos listas. Esta función en Haskell se llama zipWith.

iii. Utilizando la función mapo2, definir la funcion sumaMat (suma de matrices). Asumir que las dos matrices de entrada tienen la misma cantidad de filas y de columnas, y que una matriz es una lista de listas (cada lista representa una fila, y las longitudes de las filas son iguales entre sı).

Respuesta:

i.

mapo :: (a -> b -> (c, d)) -> [(a, b)] -> [(c, d)]
mapo f xs = map (uncurry f) xs

ii

mapo2 :: (a->b->c) -> [a] -> [b] -> [c]
mapo2	   f	  []	 []	= 	[]
mapo2 	   f	(x:xs) (y:ys)	= 	(f x y): mapo2 f xs ys

iii

sumaMat :: Int->Int->Int
sumaMat = mapo2 (mapo2 (+))

Ejercicio 13

i. Definir la funcion paresConsec, que dada una lista de elementos devuelve una lista de pares de elementos, formada por todos los elementos de la lista original junto a su inmediato sucesor. Ejemplo: paresConsec [7,3,2,5] -> [(7,3),(3,2),(2,5)]

ii. Definir la funcion pascal, que devuelve en forma de listas el triangulo de Pascal hasta la altura pedida. No se permite el uso de numeros combinatorios. Usar last, paresConsec y map. Ejemplo: pascal 4 -> [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]

Respuesta
i

paresConsec l = if (length l) < 2 then [] else foldr (\x y -> (x,fst (head y)) : y) [(last(init l ),last l)] (init (init l))

ii

alternativa 1
(No usé map y no usé last y ademas usé reverse, y head, estoy seguro que hay mejores soluciones, pero la idea de resolución debe ser muy similar)

pascal :: Int -> [[Int]]
pascal     n = reverse (funcPascal n)

funcPascal ::  Int  ->  [[Int]] 
funcPascal     n   | n == 0 = [[1]] 
                   | n > 0  = (1:nextRow (head(funcPascal (n-1)))) : (funcPascal (n-1))

nextRow ::  [Int] -> [Int] 
nextRow    (x:xs)  | length(xs) == 0 = [1]
                   | otherwise       = (x + head(xs)):(nextRow xs)

alternativa 2

Yo contribuyo con esta:

pascal n		= [rowpascal i|i<-[0..n]]
rowpascal 0		= [1]
rowpascal n		= 1: map (\x->fst x+snd x) (paresConsec (rowpascal(n-1))) ++ [1]

alternativa 3

pascal n = foldr (\x ls -> if length ls == 1 then ls ++ [[1,1]] else ls ++ 
          [ [1] ++ (map (\(x,y) -> x +y) (paresConsec (last (ls))))++[1]])      
          [[1]] [0..n-1]

Ejercicio 14

i. Usando map y la funcion p x y = y x, definir una funcion ap que cumpla con lo siguiente, e indicar su tipo: ap [f1, f2, ..., fn] x -> [f1 x, f2 x, ..., fn x]

ii. Definir una funcion apl que cumpla con lo siguiente, e indicar su tipo: apl [f1, f2, ..., fn] [x1, x2, ..., xm] -> [[f1 x1, f2 x1, ..., fn x1], ..., [f1 xm, f2 xm, ..., fn xm]]

Respuesta

i. Alternativa 1: Sin usar map ni p

ap :: [(a->b)] -> a -> [b]
ap 	 []    x   = []
ap     (f:fs)  x   = f x : ap (fs) x

Alternativa 2: Usando map pero sin p

ap :: [(a -> b)] -> a -> [b]
ap fs a = map (\f -> f a) fs

Alternativa 3: Usando map y p

p x y = y x 
ap :: [(a -> b)] -> a -> [b]
ap fs a = map (p a) fs

ii. Alternativa 1: Sin usar alto map

apl :: [(a->b)] -> [a] -> b
apl	  f	   []	 = []
apl	  f	 (x:xs)  = (ap f x) : (apl f xs)

Alternativa 2: Usando map

apl :: [(a->b)] -> [a] -> b
apl fs = map (ap fs)

Ejercicio 15

i. Definir usando foldr las funciones suma, elem, append, filter y map.

suma = foldr (+) 0
elem = \x -> foldr ((||).(==x)) False
append = foldr ((.).(:)) id
filter = \p -> foldr (\x xs -> if p x then x:xs else xs) []
map = \f -> foldr ((:).f) []

ii. Definir la funcion sumaAlt, que realiza la suma alternada de los elementos de una lista. Es decir, da como resultado: el primer elemento, menos el segundo, mas el tercero, menos el cuarto, etc. Usar foldl.

Alternativa 1: Usando foldl

sumaAlt :: [Int] -> Int
sumaAlt = foldl (flip (-)) 0

Alternativa 2: Usando foldr en lugar de foldl

sumaAlt :: [Int] -> Int
sumaAlt = foldr (-) 0

Ejercicio 17

i. Definir la funcion partes, que recibe una lista L y devuelve la lista de todas las listas formadas por los mismos elementos de L, en su mismo orden de aparicion. Ejemplo: partes [5,1,2] -> [[], [5], [1], [2], [5,1], [5,2], [1,2], [5,1,2]] (no necesariamente en ese orden).

ii. Definir la funcion prefijos, que dada una lista, devuelve todos sus prefijos. Ejemplo: prefijos [5,1,2] -> [[], [5], [5,1], [5,1,2]]

iii. Definir la funcion sublistas, que dada una lista, devuelve todas sus sublistas (listas de elementos consecutivos que conforman la lista original). Ejemplo: sublistas [5,1,2] -> [[], [5], [1], [2], [5,1], [1,2], [5,1,2]] (no necesariamente en ese orden)

Respuesta
i.
Alternativa 1: Sin usar foldr

partes :: [a] -> [[a]]
partes    []    = [[]]
partes   (x:xs) =  (unir x (partes xs)) ++ (partes xs)

unir :: a -> [[a]] -> [[a]]
unir  e []     = []
unir  e (x:xs) = (e:x):(unir e xs)

Alternativa 2: Con foldr

partes :: [a] -> [[a]]
partes = foldr f [[]]
	where f x r = r ++ map (x:) r

ii.
Alternativa 1: Sin usar foldr

prefijos :: [a] -> [[a]]
prefijos  []  = []
prefijos  (x:xs)   = [x]:(unir x (prefijos xs))

Alternativa 2: Usando foldr

prefijos :: [a] -> [[a]]
prefijos x = reverse (foldr (agregar) [[]] x)

agregar :: a -> [[a]] -> [[a]]
agregar    a      x = foldr (\xs ys -> [[a]++xs]++ys) [[]] x

Alternativa 3: Otra con foldr

prefijos :: [a] -> [[a]]
prefijos = foldr (\actual acum -> []:agregarATodas actual acum) [[]]

agregarATodas :: a -> [[a]]
agregarATodas x = foldr (\actual acum -> (x:actual):acum) []

iii.
Alternativa 1: Si alguno tiene una version menos rebuscada se la agradezco

subListas :: [a] -> [[a]]
subListas x = []:foldr (agregarS)  [] x

agregarS :: a -> [[a]] -> [[a]]
agregarS  e x = foldr(\xs yss -> [[e]++xs]++([xs]++yss)) [[e]] x

Alternativa 2:

sufijos :: [a] -> [[a]]
sufijos xs = map reverse (prefijos (reverse xs))

sublistas :: (Eq a) => [a] -> [[a]]
sublistas xs = nub (planchar [sufijos ps | ps <- (prefijos xs)])

planchar :: [[a]] -> [a]
planchar xs = [x | g <- xs, x <- g]

Alternativa 3:

sublista :: [a] -> Int -> Int -> [a]
sublista xs from count = [xs !! i | i <- [from..(from+count)]]

sublistas xs = []:[(sublista xs f c) | f <- [0..n-1], c <- [0..n-f-1]]
	where n = length xs

Alternativa 4:

(agregarATodas definida en Alternativa 3 de "prefijos")

sublistas [] = [[]]
sublistas (x:xs) = agregarATodas x (prefijos xs) ++ sublistas xs

Alternativa 5:

sublistas :: [a] -> [[a]]
sublistas = foldr (\x r -> (map (x:) r ++ r)) [[]] 

Ejercicio 18

Utilizar listas por comprension para definir la funcion perms, que dada una lista, devuelve todas sus permutaciones.

Alternativa 1: Usando indexacion

perms :: [a] -> [[a]]
perms [] = [[]]
perms xs = [(xs !! i) : ys | i <- [0..((length xs) -1)], ys <- (perms (remv i xs))]

-- Remv: dado un indice y una lista, quita el elemento en ese indice de la lista
remv :: Int -> [a] -> [a]
remv i xs = [xs !! j | j <- [0..((length xs) -1)], not (i == j)]

Alternativa 2: Usando delete

perm :: Eq a => [a] -> [[a]]
perm [] = [[]]
perm xs = nub [x : ys | x <- xs, ys <- (perm (delete x xs))]

El nub adelante es opcional (y lo que obliga a agregar el Eq a), permite borrar todas las permutaciones duplicadas que resulten de elementos duplicados en la lista original.

Ejercicio 19

Definir el tipo de datos ArbolNV de arboles no vacıos, donde cada nodo tiene una cantidad indeterminadade hijos, las hojas contienen rotulos de un tipo y los nodos intermedios contienen rotulos de eventualmente otro tipo.

data ArbolNV h n = Hoja h | Nodo n [ArbolNV h n]
sampleArbolNV = Nodo 0 [Nodo 1 [Hoja "Pepe", Hoja "Toto"], Nodo 2 [Hoja "Lolo"], Hoja "Cacho"]

Ejercicio 20

Item I

Definir la funcion:

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

Esta funcion es una version modificada de foldr, que realiza un fold sobre la lista de entrada pero aplicando una funcion f a los elementos en posiciones pares y una funcion g a los elementos en posiciones impares. Considerar que la primera posicion de la lista es la numero 1.

foldalt :: (a -> b -> b) -> (a -> b -> b) -> b -> [a] -> b
foldalt f g b [] = b
foldalt f g b (x:xs) = g x (foldalt g f b xs)

Item II

Usando foldalt, escriba la funcion sumaaltdoble :: [Int] -> Int , que calcula la suma de los numeros de las posiciones impares y el doble de los numeros de las posiciones pares.

Ejemplo: sumaaltdoble [2,5,3,7,7,3] = 2+10+3+14+7+6 = 42

sumaaltdoble :: [Int] -> Int
sumaaltdoble = foldalt (\a b -> 2*a+b) (+) 0

testsumaaltdoble = sumaaltdoble [2,5,3,7,7,3]

Item III

Usando foldalt, escriba la funcion numsalt :: Int -> Int que calcula el producto de la longitud de las listas de las posiciones pares y la suma de los elementos de las listas de las posiciones impares.

Ejemplo: numsalt [ [1,2], [1,2], [2,3], [2,3] ] = 2*(3*(2*5)) = 60

numsalt :: Int -> Int
numsalt = foldalt (\xs b -> length(xs) * b) (\xs b -> sum(xs) * b) 1

testnumsalt = numsalt [ [1,2], [1,2], [2,3], [2,3] ]

Ejercicio 21

Definimos el siguiente tipo:

data Agenda p t = Vacia | Telefonos p [t] (Agenda p t)

Este tipo modela una agenda de telefonos. A una agenda se le puede agregar una nueva entrada, donde se registra para una persona una lista de telefonos. Una misma persona puede aparecer en varias entradas. La lista de telefonos de una entrada puede contener repetidos.

Ejemplo:

miAgenda = Telefonos "Letincho" [42079999,43834567]
(Telefonos "Javi" [47779830] (Telefonos "Letincho" [42079999] Vacia))

Sea foldrAgenda el siguiente esquema de recursion generico para agendas:

foldrAgenda f b Vacia = b
foldrAgenda f b (Telefonos p ts ag) = f p ts (foldrAgenda f b ag)

En la resolucion de este ejercicio, no usar recursion explıcita.

Item I

Decir cual es el tipo de la funcion foldrAgenda.

foldrAgenda :: (p -> [t] -> b -> b) -> b -> Agenda p t -> b

Item II

Definir una funcion dameTelefonosDe::Eq p =>p ->Agenda p t ->[t] , que devuelva todos los telefonos que aparecen en la agenda para una misma persona.

dameTelefonosDe :: Eq p => p -> Agenda p t -> [t]
dameTelefonosDe pe = foldrAgenda f []
	where f act tel res = (if act == pe then tel else []) ++ res

Item III

Definir el esquema de recursion: foldrPersona::Eq p =>(p ->c ->c) ->c ->Agenda p t ->c que funcione de manera similar a foldrAgenda pero solo aplique la funcion pasada como parametro a las personas de la agenda. Si la agenda tiene personas repetidas, solo debe aplicar la funcion a la aparicion correspondiente al redex mas interno de la persona en la agenda.

Ejemplo: foldrPersona f b miAgenda debe aplicar la funcion f primero a ”Letincho” con el caso base pasado como parametro y luego aplicarla a ”Javi” con el valor obtenido en el paso anterior.

personaIncl :: Eq p => p -> Agenda p t -> Bool
personaIncl p = foldrAgenda (\x _ r -> (x == p) || r) False	

foldrPersona :: Eq p => (p -> c -> c) -> c -> Agenda p t -> c
foldrPersona f c Vacia = c
foldrPersona f c (Telefonos p ts ag) = if (personaIncl p ag) then res else (f p res)
	where res = (foldrPersona f c ag)

Item IV

Definir una funcion personasSinRepeticiones:: Eq p => Agenda p t -> [p] que devuelva la lista de personas que aparecen en la agenda, sin repeticiones.

personasSinRepeticiones:: Eq p => Agenda p t -> [p]
personasSinRepeticiones = foldrPersona (\p r -> p:r) []

Item V

Definir una funcion compactar::Eq p => Agenda p t -> Agenda p t que a partir de una agenda, devuelva otra donde aparecen todas las personas de la primer agenda, pero sin repeticiones. Cada entrada de la agenda resultado, debe contener todos los telefonos que la persona tenıa en la agenda original.

compactar :: Eq p => Agenda p t -> Agenda p t
compactar a = foldrPersona (\p ag -> Telefonos p (dameTelefonosDe p a) ag) Vacia a