Programación Funcional - Avanzada

Algoritmos y Estructuras de Datos I

Segundo cuatrimestre de 2004

Aclaraciones: Los ejercicios de esta práctica piden la definición de funciones al estilo de los programas fun-
cionales de Haskell. En general, no hay una única manera de definir una función. Sin embargo, nos interesa que
las soluciones elegidas sean claras, comprensibles, compactas (breves, de ser posible), completas (que contemplen
todos los casos de interés) y declarativas (que estén más cerca del qué y no del cómo).
Cuando resulte conveniente, se pueden definir funciones auxiliares para simplificar la definición de la función
principal. También se pueden usar funciones definidas previamente en otros ejercicios.
Dar explı́citamente el tipo de una función (el tipo de su domino y su imagen) permite detectar errores
tempranamente. No hay que olvidar que el valor que devuelve una función depende sólo de sus argumentos.

1 Listas
Al comenzar a trabajar con cualquier lenguaje (de especificación, de desarrollo, etc.) uno trata en principio con
tipos básicos como enteros, booleanos o caracteres. Sin embargo, muchas veces es necesario operar con colecciones
de datos. Existen muchas alternativas para representar estas colecciones. Una de las más simples y comunes es
la lista. Las listas se interpretan como secuencias de elementos contiguos del mismo tipo. Haskell provee el tipo
lista como tipo nativo.
Las listas (en Haskell) poseen los siguientes constructores:

[ ] :: → Lista Genera la lista vacı́a.

(· : ·) :: elem → Lista → Lista Genera una nueva lista agregando un elemento al principio
de la lista original (donde elem es del tipo de los elementos
que componen la lista).

Además, podemos definir las siguientes funciones:

• null, que determina si una lista es la lista vacı́a:

null :: Lista → bool

null [ ] = True
null xs = False

• head, que devuelve el primer elemento de una lista no vacı́a:

head :: Lista → elem

head (x : xs) = x

• tail, que devuelve la lista que resulta de quitarle el primer elemento a la lista original (no vacı́a):

tail :: Lista → Lista

tail (x : xs) = xs

Al ser Lista un tipo algebraico, la recursión resulta ser una herramienta útil para tratar problemas, dado que una
instancia de la misma puede ser expresada como una aplicación de sus constructores sobre otras instancias más
simples.
Ejercicio 1. A partir de los constructores y las funciones anteriores, definir las funciones de los ejercicios 7, 8 y
9 de la Práctica de Tipos Compuestos.

1
Ejercicio 2. Definir las siguientes funciones:

1. ∆ : Z = funcion1(L : ListahCh i)
P ≡ {True}
P|L|−1
Q ≡ {∆ = i=0 β(φi (L) = 0 0 )}

2. ∆ : ListahZi = filtro1(L : ListahZi)

P ≡ {True}
Q ≡ {(∀e : Z)(Par (e) → cantAp(e, L) = cantAp(e, ∆)) ∧ (∀i : Z)(0 ≤ i < |L| ∧ Par (φi (L)) →
φParesAntes(L,i) (∆) = φi (L))} esPar (x : Z) ≡ {x mod 2 = 0}
P|L|−1
ParesAntes(L : ListahZi, n : Z, ) ≡ { i=0 β(i < n ∧ Par (φi (L)))}

3. ∆ : ListahZi = filtro2(L : ListahZi)

P ≡ {True}
Q ≡ {cantDistintos(|∆|, L) ∧ (∀i : Z)(0 ≤ i < |L| → (∃t : Z)(0 ≤ 2 ∗ t < |∆| ∧ φ2∗t (∆) = φi (L)) ∧
(∀i : Z)(0 ≤ 2 ∗ i < |∆| → (φ2∗i+1 (∆) = cantAp(φ2∗i (∆), L)))}
cantDistintos(t : Z, L : ListahZi) ≡ {(∃C : ConjuntohZi)((∀x : Z)(x ∈ C ↔ esta(x, L)) ∧ 2 ∗ |C| = t)}
P|L|−1
cantAp(t : Z, L : ListahZi) ≡ { i=0 β(φi (L) = t)}
4. ∆ : ListahZi = transformacion1(L1 , L2 : ListahZi)
P ≡ {ordenado(L1 ) ∧ ordenado(L2 )}
Q ≡ {(∀i : Z)(cantAp(i, ∆) = cantAp(i, L1 ) + cantAp(i, L2 )) ∧ ordenado(∆)}
ordenado(L : ListahZi) ≡ {(∀i : Z)(0 ≤ i < |L| − 1 → φi (L) ≤ φi+1 (L))}
5. ∆ : ListahCh i = transformacion2(L1 , L2 : ListahCh i)
P ≡ {|L1 | ≤ |L2 |}
Q ≡ {(esSubcadena(L1 , L2 ) ∧ |∆| = |L2 | − |L1 | ∧ (∃i : Z)(0 ≤ i < |L2 | ∧ estaAPartir (L1 , i, L2 ) ∧
minimo(L1 , i, L2 ) ∧ (∀j : Z)((0 ≤ j < i → φj (L2 ) = φj (∆)) ∧ (i + |L1 | ≤ j < |L2 | → φj−|L1 | (∆) =
φj (L2 ))))) ∨ (¬esSubcadena(L1 , L2 ) ∧ ∆ = L2 )}
estaAPartir (L1 : ListahCh i, i : Z, L2 : ListahCh i) ≡ {(∀j : Z)(0 ≤ j < |L1 | → φj (L1 ) = φj+i (L2 ))}
minimo(L1 : ListahCh i, i : Z, L2 : ListahCh i) ≡ {¬(∃k : Z)(k < i ∧ estaAPartir (L1 , k, L2 ))}
esSubcadena(L1 , L2 : ListahCh i) ≡ {(∃j : Z)(0 ≤ j < |L2 | − |L1 | ∧ estaAPartir (L1 , j, L2 ))}

6. ∆ : ListahCh i = filtro3(L : ListahCh i)

P ≡ {True}
Q ≡ {|∆| = |L| − cantBlancos(∆) ∧ (∀i : Z)(0 ≤ i < |L| ∧ φi (L) 6= 0 0 → φNoBlancosAntes(L,i) (∆) = φi (L))}
P |L|−1
NoBlancosAntes(L : ListahCh i, n : Z) ≡ { )i=0 β(i < n ∧ φi (L) 6= 0 0 )}
P |L|−1
cantBlancos(L : ListahCh i) ≡ { )i=0 β(φi (L) = 0 0 )}

7. ∆ : ListahCh i = transformacion3(L : ListahCh i)

P ≡ {|L| =6 cantBlancos(L)}
Q ≡ {(∃i, j : Z)(inicioPrimeraPalabra(i, L) ∧ finPalabra(j, i, L) ∧ |∆| = j − i + 1 ∧ (∀k : Z)(i ≤ k ≤ j →
φk (L) = φk−i (∆)))}
inicioPalabra(i : Z, L : ListahCh i) ≡ {0 ≤ i < |L| ∧ (∀j : Z)(0 ≤ j < i → φj (L) = 0 0 ) ∧ φi (L) 6= 0 0 }
finPalabra(j, i : Z, L : ListahCh i) ≡ {i ≤ j ∧ 0 ≤ j < |L| ∧ (∀k : Z)(i ≤ k ≤ j → φk (L) 6= 0 0 ) ∧ (j + 1 =
|L| ∨ φj+1 (L) = 0 0 )}

Ejercicio 3. Definir las siguientes funciones:

1. sacarTodos :: [Char] → [Char] → [Char], que elimina todas las apariciones de la primer lista en la segunda.
Por ejemplo sacarTodos [c, a] [a, c, a, d, c, a] es [a, d].
2. sacarBlancosRepetidos :: [Char] → [Char], que reemplaza cada subsecuencia de blancos contiguos del primer
parámetro por un solo blanco en el segundo parámetro.
3. contarPalabras :: [Char] → Integer, que devuelve la cantidad de palabras del parámetro.

2
 4. palabraMasLarga :: [Char] → [Char], que devuelve la palabra más larga del parámetro.
5. palabras :: [Char] → [[Char]], que arma una nueva lista con las palabras del parámetro.
6. aplanar :: [[Char]] → [Char], que a partir de una lista de palabras arma una lista de caracteres con-
catenándolas.
7. aplanarConBlancos :: [[Char]] → [Char], que a partir de una lista de palabras, arma una lista de caracteres
concatenándolas e insertando un blanco entre cada par.
8. aplanarConNBlancos :: [[Char]] → Integer → [Char], que a partir de una lista de palabras, arma una lista
de caracteres concatenándolas e insertando n blancos entre cada par (n debe ser no negativo).
9. nat2bin :: Integer → [Integer], que recibe un número no negativo y lo transforma en una lista de bits
correspondiente a su representación binaria. Por ejemplo nat2bin 8 devuelve [1, 0, 0, 0].
10. bin2nat :: [Integer] → Integer, que recibe una lista de bits y la transforma en el número entero no negativo
representado por dicha lista. Por ejemplo bin2nat [1, 0, 0, 0, 1] devuelve 17.
11. nat2hex :: Integer → [Char], que recibe un número no negativo y lo transforma en una lista de caracteres
correspondiente a su representación hexadecimal. Por ejemplo nat2hex 45 devuelve [0 20 ,0 D0 ].

Ejercicio 4. Definir en programación funcional las funciones de los ejercicios 10 y 11 de la Práctica de Tipos
Compuestos.

Ejercicio 5. Diremos que un entero no negativo a reduce en b (notamos a b) sii b es el doble de la multiplicación
de todos los dı́gitos de a. Por ejemplo 99 162, 71 14, 237 84. Supongamos que reducimos sucesivamente
un número n
n n1 n2 n3 ...
Sea ni = nj , con i < j la primera repetición de esta cadena de reducciones. Definir una función que dado n
devuelva i, el número de reducción correspondiente a la primera repetición (en caso de que exista). Por ejemplo,
si reducimos sucesivamente el 99 obtenemos

99 162 24 16 12 4 8 16 12 ...

En este caso, la función deberá devolver 3. Si reducimos sucesivamente el 59, obtenemos

59 90 0 0 ...

y aquı́, debe devolver 2. Para el 237 obtenemos la reducción

237 84 64 48 64 ...

y la función debe devolver 2.

Ejercicio 6. Dada una lista de enteros L no vacı́a, especificar y definir una función que devuelva la sublista
de L que más sume (en caso de que haya más de una, devolver cualquiera de ellas). Por ejemplo, si L =
[−1, 3, −5, 7, 9, 2, −3, 6, −10, 2], la función debe devolver [7, 9, 2, −3, 6], que suma 21. Si L = [2, −3, −1, 0, 1],
debe devolver [2], que suma 2.

Ejercicio 7. Definir funciones para las siguientes especificaciones:

• ∆ :Lista< Z >= sumarAcumulado (l :Lista< Z >)
P ≡ {T rue}
Pi
Q ≡ {|∆| = |l| ∧ (∀i : Z)(0 ≤ i < |∆| → φi (∆) = j=0 φj (l))}
• ∆ :Lista< Ch >= permutar (l :Lista< Z >, m :Lista< Ch >)
P ≡ {|l| = |m| ∧ (∀i : Z)(0 ≤ i < |l| → 0 ≤ φi (l) < |l|) ∧ ¬(∃i, j : Z)(0 ≤ i < |l| ∧ 0 ≤ j < |l| ∧ i 6= j ∧ φi (l) =
φj (l))}
Q ≡ {|∆| = |m| ∧ (∀i : Z)(0 ≤ i < |∆| → φi (∆) = φφi (l) (m))}

3
2 Otros Tipos Algebraicos
Ejercicio 8. Se tiene el tipo enumerado Dı́a, formado por las constantes lunes, martes, miércoles, jueves, viernes,
sábado y domingo. Enriquecerlo, definiendo las siguientes operaciones:

1. siguiente :: Dı́a → Dı́a

2. esLaborable :: Dı́a → Bool (lunes a viernes)
3. esFinDeSemana :: Dı́a → Bool (sábado o domingo)

Ejercicio 9. Se tiene definido el tipo Nat con los siguientes elementos constructores:

• 0 (cero)
• Suc(Nat) (el sucesor del número pasado como parámetro)

Empleando solamente 0 y Suc, definir las siguientes funciones:

1. igual :: Nat → Nat → Bool

2. suma :: Nat → Nat → Nat
3. producto :: Nat → Nat → Nat
4. potencia :: Nat → Nat → Nat
5. menor :: Nat → Nat → Bool
6. resta :: Nat → Nat → Nat (es 0 si el minuendo es menor que el sustraendo)
7. división :: Nat → Nat → Nat (división entera; por ejemplo, división 7 3 = 2)
8. resto :: Nat → Nat → Nat
9. mcd :: Nat → Nat → Nat (máximo común divisor)
10. factorial :: Nat → Nat
11. nFibonacci :: Nat → Nat (n-ésimo término de la sucesión de Fibonacci)

Ejercicio 10. 1. Sea A :: (Nat, Nat) → Nat (notar que esta función no está currificada), donde Nat es el tipo
usado en el ejercicio anterior.

A(Suc(i), Suc(x)) = A(i, A(Suc(i), x))

A(i, 0) = 1
A(0, x) = x + 1 si x = 0, 1
A(0, x) = x + 2 si x > 1

Calcular A(1, 1), A(2, 2) y A(3, 2).

2. Sea A :: (Nat, Nat) → Nat

A(Suc(i), Suc(x)) = A(i, A(Suc(i), x))

A(i, 0) = 1
A(0, x) = x + 1 si x = 0, 1
A(0, x) = x + 2 si x = 2

¿Qué ocurre si se quiere evaluar la expresión A(A(2, 0) − 1, A(2, 2) − 1)?

4
Ejercicio 11. Se Define el tipo Expresión como

Data Expresión = Valex Integer | Sum Expresión Expresión | Mult Expresión Expresión

1. Definir la función Evaluar que dada una expresión devuelve el valor de la misma. Ejemplos:

Evaluar (Valex 5) = 5
Evaluar (Sum(Mult(Valex 5)(Valex 7))(Valex 9)) = 44 pues 5 · 7 + 9 = 44
Evaluar(Mult(Valex 2)(Sum(Valex 3)(Valex 4))) = 1 pues 2 · (3 + 4) = 14

2. Definir una función iguales :: Expresión → Expresión → Bool, que indica si las expresiones pasadas como
parámetro son iguales. Ejemplos:

iguales (Sum(Valex 2)(Valex 3)) (Sum(Valex 2)(Valex 3)) = True

iguales (Sum(Valex 3)(Valex 2)) (Sum(Valex 2)(Valex 3)) = False
iguales (Mult(Valex 2)(Valex 2)) (Sum(Valex 2)(Valex 2)) = False

3. Definir una función Subexpresión :: Expresión → Expresión → Bool, que dice si la primera Expresión pasada
como parámetro es una subexpresión de la segunda. Ejemplos:

Subexpresión (Mult(Valex 8)(Valex 2))(Sum(Valex 5)(Sum(Mult(Valex 8)(Valex 2))(Valex 4))) = True

Subexpresión (Sum(Valex 7)(Valex 9))(Sum(Mult(Valex 5)(Valex 7))(Sum(Valex 9)(Valex 3))) = False

3 Tipos Compuestos
Ejercicio 12. Implementar las funciones del tipo Vector dadas en el ejercicio 13 de la Práctica de Tipos Com-
puestos.

Ejercicio 13. Se tiene definido el tipo MatrizCuadrada (de enteros no negativos), que consta de las siguientes
operaciones:

• dimensión :: MatrizCuadrada → Integer, que devuelve el tamaũo de la matriz.

• valor :: MatrizCuadrada → Fila → Columna → Integer, que devuelve el valor de la casilla indicada. Esta
función está indefinida cuando Fila y Columna están fuera del rango válido. Los tipos Fila y Columna son
sinónimos de Integer.

Por ejemplo, si m es la matriz cuadrada  

3 1 6
 2 5 3 
5 4 1
entonces dimension m es 3, valor m 1 2 es 1 y valor m 3 2 es 4.

1. Especificar y definir las siguientes operaciones:

(a) todasIguales :: MatrizCuadrada → Bool, que indica si todos los elementos de la matriz cuadrada tienen
el mismo valor.
(b) identidad :: MatrizCuadrada → Bool, que indica si la matriz es una matriz identidad. La matriz
identidad tiene 0 en todas las posiciones, excepto en las posiciones de la diagonal, que tienen 1.
(c) máximo :: MatrizCuadrada → Integer, que devuelve el valor máximo de la matriz.
(d) mı́nimo :: MatrizCuadrada → Integer, que devuelve el valor mı́nimo de la matriz.
2. Redefinir la función del item (1a), ahora usando solamente los items (1c) y (1d).
3. Una matriz cuadrada es degradé si tiene las siguientes propiedades :

• Todas las celdas que pertenecen a una misma diagonal de la matriz contiene el mismo número natural.

5
 • El número que contiene una diagonal es mayor que los números que contienen todas las diagonales
que están más a la izquierda. Es decir, las diagonales están ordenadas descendentemente.

Un ejemplo de matriz cuadrada degradé es:

 
4 6 25 75 99

 3 4 6 25 75 


 2 3 4 6 25 

 1 2 3 4 6 
0 1 2 3 4

Las siguientes matrices no son degradé:

 
4 6 25 75    
 3 99 8 7 7 11 13
4 6 25   8

 8
 7 3   2 8 11 
3 4 6 
7 3 1 1 2 9
1 8 3 4

Se pide definir la función esDegradé que dada una matriz cuadrada devuelva True si es degradé y False en
caso contrario.

Ejercicio 14. Se cuenta con el tipo compuesto Polinomio (de coeficientes enteros), definido de la siguiente
manera:

Tipo Polinomio .
grado : P olinomio → Z
Permite saber el grado del polinomio.
coeficiente(P, n) : P olinomio × Z → Z
permite saber el coeficiente del término de grado n del polinomio.

Asumiendo que existen los algoritmos para grado y coeficiente, por ejemplo:

grado (2x3 + 8) = 3
coeficiente (2x3 + 8) 0 = 8
coeficiente (2x3 + 1) 1 = 0
coeficiente (2x3 + 1) 3 = 2

Especificar y definir la función evaluar :: Polinomio → Integer → Integer, que devuelve el valor del polinomio en
el punto dado.

Ejercicio 15. Definir las operaciones del tipo Pirámide especificadas en el ejercicio 16 de la Práctica de Tipos
Compuestos.

Ejercicio 16. Se define el tipo compuesto Tablero como:

Tipo Tablero .
cantFilas : T ablero → Z
devuelve la cantidad de filas.
cantColumnas : T ablero → Z
devuelve la cantidad de columnas.
colorCasilla(T, f, c) : T ablero × Z × Z → Color 0 ≤ f < cantF ilas(T ) ∧ 0 ≤ c <
cantColumnas(T )
devuelve el color de una casilla de un tablero (blanco o negro).

6
Suponiendo que se cuenta con el siguiente algoritmo, especificar y definir las siguientes funciones:
pintarNegro :: Tablero → Fila → Columna → Tablero, que devuelve un tablero igual al original salvo por la
casilla parámetro, que ahora es negra. Si no es una casilla válida, devuelve un tablero igual al original.

1. cantidadBloquesNegros :: Tablero → Integer. Esta función devuelve la cantidad de bloques negros que hay
en el tablero, donde un bloque es un cuadrado de dos por dos casillas, todas negras. No importa que los
bloques estén superpuestos. Ejemplos:

Tab1 Tab2 Tab3

cantidadBloquesNegros Tab1 = 1
cantidadBloquesNegros Tab2 = 2
cantidadBloquesNegros Tab3 = 4

2. cantidadCrucesNegras :: Tablero → Integer. Esta función devuelve la cantidad de cruces negras que hay en
el tablero, donde una cruz tiene tres casillas negras de largo por tres de ancho. No importa que las cruces
estén superpuestas. Ejemplos:

Tab4 Tab5 Tab6

cantidadCrucesNegras Tab4 = 1
cantidadCrucesNegras Tab5 = 2
cantidadCrucesNegras Tab6 = 4

3. esDamero :: Tablero → Bool. Esta función verifica si el tablero alterna casillas blancas con negras en todas
las posiciones (como un tablero de damas o de ajedrez). Ejemplo:

Tab7

esDamero Tab7 = T rue

4. (Opcional) tamMayorSectorBlanco :: Tablero → Integer. Esta función devuelve el tamaño del sector blanco
más grande, donde un sector blanco es un conjunto de casillas blancas adyacentes, delimitadas por casillas
negras o por el fin del tablero. Ejemplo:

7
 Tab8

tamMayorSectorBlanco Tab8 = 10 (el sector blanco más grande es el que está sombreado)
Nota: Cuidado con las indefiniciones.

Ejercicio 17. Implementar las funciones especificadas en los ejercicios 17, 18 y 19 de la Práctica de Tipos
Compuestos.

Ejercicio 18. En un proyecto de desarrollo de un sistema de gestión para videoclubs, se te pide, como parte
del staff de programadores, que especifiques y definas ciertas funciones del sistema. Se cuenta con los tipos
compuestos: VideoClub, Cliente y Pelı́cula, y las siguientes funciones:

• Clientes :: VideoClub → [Cliente], que devuelve una lista con los clientes registrados en el videoclub.
• Pelı́culas :: VideoClub → [Pelı́cula], que devuelve una lista con las pelı́culas que están en el catálogo del
videoclub, independientemente de si está disponible o no.
• CantidadDeCopias :: VideoClub → Pelı́cula → Integer, que devuelve cuántas copias de la pelı́cula tiene el
videoclub (esta función se indefine, o sea da error, si la pelı́cula no pertenece al catálogo del videoclub).
• Pelı́culasAlquiladas :: Videoclub → Cliente → [Pelı́cula], que devuelve una lista de pelı́culas que el cliente
tiene alquiladas en el videoclub (esta función se indefine si el cliente no esta registrado en el videoclub). El
cliente puede alquilar más de una copia de la misma pelı́cula.

Se pide:

1. Especificar y definir la función alquiló :: VideoClub → Cliente → Pelı́cula → Bool, que indica si el cliente
alquiló la pelı́cula.
2. Especificar y definir la función copiasAlquiladas :: VideoClub → Pelı́cula → Integer, que devuelve la cantidad
de copias de la pelı́cula dada que están alquiladas en el videoclub.

3. Especificar y definir la función disponibleParaAlquilar :: Videoclub → Pelı́cula → Bool, que indica si una
pelı́cula esta disponible para ser alquilada en el videoclub (por ejemplo, una pelı́cula puede estar en un
videoclub pero no estar disponible porque todas sus copias están alquiladas, o no estar disponible porque
no está en el catálogo).

Dada la crisis económica los videoclubs más pequeũos han decidido unirse en una red para brindar servicios
adicionales al cliente como, por ejemplo, distribución a domicilio y compartir el conjunto de pelı́culas que disponen.
Debido a esto se pide:

1. Especificar y definir la función disponibleEnLaRed :: [Videoclub] → Pelı́cula → Bool, que dice si la pelı́cula
esta disponible en al menos alguno de los videoclubs de la red.
2. Especificar y definir la función másAlquiladaEnLaRed :: [Videoclub] → Pelı́cula, que devuelve la pelı́cula
más alquilada en todos los videoclubs de la red.
3. Especificar y definir la función ClientesRaros :: [Videoclub] → [Cliente], que devuelve la lista de clientes que
tienen alquilada la misma pelı́cula en distintos videoclubs.