Primer Parcial 2do Cuat 2008 (Paradigmas)

Ejercicio 1

En todo este ejercicio no se puede usar recursión explícita ni se pueden usar listas por comprensión. Sí se permite usar sucesiones aritméticas de la forma [m..n]. Para resolver un ítem pueden utilizarse como existentes las soluciones a todos los anteriores, más allá de si fueron resueltos correctamente o no. En este ejercicio vamos a ver extensiones y usos de la función zipWith del Prelude de Haskell. Dicha función se comporta como un map binario: toma como parámetro una función binaria f :: a -> b -> c y dos listas [a1, ..., an] y [b1, ..., bn], y devuelve la lista resultante de aplicar la función a los elementos correspondientes [f a1 b1, ..., f an bn]. Si las listas tienen distinta longitud, el resultado tiene la longitud de la más corta.

a) (9 puntos) Escribir map en términos de zipWith. Tener en cuenta que este map se tiene que comportar correctamente sobre listas infinitas.

b) (9 puntos) Escribir la función sumaMat, que representa la suma de matrices. Representaremos una matriz como la lista de sus filas. Esto quiere decir que cada matriz será una lista finita de listas finitas, todas de la misma longitud, con elementos enteros. Recordamos que la suma de matrices se define como la suma celda a celda. Asumir que las dos matrices a sumar tienen las mismas dimensiones.

sumaMat :: [[Int]] -> [[Int]] -> [[Int]]

c) (12 puntos) Escribir la función zipWithList, que dada una lista de listas, un caso base y una función combinadora, hace un zipWith de los elementos correspondientes de todas las listas. Es decir:

zipWithList :: (a -> b -> b) -> b -> [[a]] -> [b] 
zipWithList func base [[a1,...,an],[b1,...,bn],...,[z1,...,zn]] 

reduce a [foldr func base [a1,...,z1], foldr func base [a2,...,z2], ..., foldr func base [an,...,zn]] Se puede asumir que ninguna de las listas es infinita.

d) (10 puntos) Escribir la función trasponer, que dada una matriz como las del ítem b, devuelve su traspuesta; es decir, devuelve en la posición i, j del resultado el contenido de la posición j, i de la matriz original. Notar que si la entrada es una lista de N listas, todas de longitud M, entonces el resultado debe tener M listas, todas de longitud N.

trasponer :: [[Int]] -> [[Int]]

Respuesta

a)

map :: (a->b) -> [a] -> [b]
map f xs = zipWith(\y _ -> f y) xs xs

b)

sumaMat:: [[Int]] -> [[Int]] -> [[Int]]
sumaMat a b = zipWith sumarFilas a b
    where sumarFilas = zipWith (\x y -> x + y)

c)

zipWithList :: (a->b->b) -> b -> [[a]] -> [b]
zipWithList func base xs =  map (\x -> foldr func base x) (trasponer xs)

d)

trasponer :: [[Int]] -> [[Int]]
trasponer as = foldr func (nvacias as) as
   where func xs rs = zipWith (\x r -> x:r) xs rs
         nvacias [] = []
         nvacias (y:ys) = map (\ _ -> []) (y:ys)

Ejercicio 3

En este ejercicio enxtenderemos el algoritmo de inferencia visto en clase para soportar el tipado de la construcción Maybe, análoga a la de Haskell, junto con un observador universal para ésta. La extensión de la sixntaxis y el sistema de tipos para esto son los siguientes:

$M::=...|Nothing_{\sigma }|JustM|case_{\sigma }M:Nothing\to N;Justx\to O$ $\sigma ::=...|Maybe\sigma$

donde O puede tener libre a x, que se asociará al contenido de M si éste reduce a un Just. Y las reglas de tipado son las siguientes

${\frac {}{\Gamma \triangleright Nothing_{\sigma }:Maybe\sigma }}$

${\frac {\Gamma \triangleright M:\sigma }{\Gamma \triangleright JustM:Maybe\sigma }}$

${\frac {\Gamma \triangleright M:Maybe\sigma \Gamma \triangleright N:\tau \;\;\;\Gamma \cup x:\sigma \triangleright O:\tau }{\Gamma \triangleright case\sigma M:Nothing\to N;Justx\to O:\tau }}$

Recordar que el subíndice $\sigma deNothing_{\sigma }$ y $case_{\sigma }...$, al igual que todas las anotaciones de tipos, no aparece en la entrada del algoritmo.

a) (22 puntos) Dar la extensión al algoritmo necesaria para soportar el tipado de la nueva estructura.

b) (8 puntos) Aplicar el algoritmo extendido con el método del árbol para tipar

$\lambda x\;\lambda y\;if\;x\;then\;Nothing\;else\;Just\;y$.

En cada nodo del árbol mostrar cómo queda el contexto, y siempre que se realice una unificación mostrar el conjunto de ecuaciones a unificar y la sustitución resultante.