Expresiones aritmética normalizadas
El siguiente tipo de dato representa expresiones construidas con variables, sumas y productos
data Expr = Var String | S Expr Expr | P Expr Expre
Por ejemplo, x.(y+z) se representa por (P (V "x") (S (V "y") (V "z")))
Una expresión es un término si es un producto de variables. Por ejemplo, x.(y.z) es un término pero x+(y.z) ni x.(y+z) lo son.
Una expresión está en forma normal si es una suma de términos. Por ejemplo, x.(y,z) y x+(y.z) está en forma normal; pero x.(y+z) y (x+y).(x+z) no lo están.
Definir las funciones
esTermino, esNormal :: Expr -> Bool
tales que
- (esTermino a) se verifica si a es un término. Por ejemplo,
esTermino (V "x") == True esTermino (P (V "x") (P (V "y") (V "z"))) == True esTermino (P (V "x") (S (V "y") (V "z"))) == False esTermino (S (V "x") (P (V "y") (V "z"))) == False
- (esNormal a) se verifica si a está en forma normal. Por ejemplo,
esNormal (V "x") == True esNormal (P (V "x") (P (V "y") (V "z"))) == True esNormal (S (V "x") (P (V "y") (V "z"))) == True esNormal (P (V "x") (S (V "y") (V "z"))) == False esNormal (P (S (V "x") (V "y")) (S (V "y") (V "z"))) == False
Acrónimos
A partir de una palabra de puede formar un acrónimo uniendo un prefijo de la primera con un sufijo de la segunda. Por ejemplo,
- "ofimática" es un acrónimo de "oficina" e "informática"
- "informática" es un acrónimo de "información" y "automática"
- "teleñeco" es un acrónimo de "televisión" y "muñeco"
Definir la función
esAcronimo :: String -> String -> String -> Bool
tal que (esAcronimo xs ys zs) se verifica si xs es un acrónimo de ys y zs. Por ejemplo,
esAcronimo "ofimatica" "oficina" "informatica" == True esAcronimo "informatica" "informacion" "automatica" == True
Particiones de longitud fija
Definir la función
particionesFijas :: Int -> Int -> [[Int]]
tal que (particionesFijas n k) es la lista de listas de k números naturales no crecientes cuya suma es n. Por ejemplo,
λ> particionesFijas 8 2 [[4,4],[5,3],[6,2],[7,1]] λ> particionesFijas 8 3 [[3,3,2],[4,2,2],[4,3,1],[5,2,1],[6,1,1]] λ> particionesFijas 9 3 [[3,3,3],[4,3,2],[4,4,1],[5,2,2],[5,3,1],[6,2,1],[7,1,1]] λ> length (particionesFijas 67 5) 8056
Evaluación de árboles de expresiones aritméticas
Las expresiones aritméticas se pueden representar como árboles con números en las hojas y operaciones en los nodos. Por ejemplo, la expresión "9-2*4" se puede representar por el árbol
-
/ \
9 *
/ \
2 4
Definiendo el tipo de dato Arbol por
data Arbol = H Int | N (Int -> Int -> Int) Arbol Arbol
la representación del árbol anterior es
N (-) (H 9) (N (*) (H 2) (H 4))
Definir la función
valor :: Arbol -> Int
tal que (valor a) es el valor de la expresión aritmética correspondiente al árbol a. Por ejemplo,
valor (N (-) (H 9) (N (*) (H 2) (H 4))) == 1 valor (N (+) (H 9) (N (*) (H 2) (H 4))) == 17 valor (N (+) (H 9) (N (div) (H 4) (H 2))) == 11 valor (N (+) (H 9) (N (max) (H 4) (H 2))) == 13
Aplicaciones alternativas
Definir la función
alternativa :: (a -> b) -> (a -> b) -> [a] -> [b]
tal que (alternativa f g xs) es la lista obtenida aplicando alternativamente las funciones f y g a los elementos de xs. Por ejemplo,
alternativa (+1) (+10) [1,2,3,4] == [2,12,4,14] alternativa (+10) (*10) [1,2,3,4,5] == [11,20,13,40,15]
Repetición cíclica
Definir la función
ciclica :: [a] -> [a]
tal que (ciclica xs) es la lista obtenida repitiendo cíclicamente los elementos de xs. Por ejemplo,
take 10 (ciclica [3,5]) == [3,5,3,5,3,5,3,5,3,5] take 10 (ciclica [3,5,7]) == [3,5,7,3,5,7,3,5,7,3] take 10 (ciclica [3,5..]) == [3,5,7,9,11,13,15,17,19,1] ciclica [] == []
Comprobar con QuickCheck que la función ciclica es equivalente a la predefinida cycle; es decir, para cualquier número entero n y cualquier lista no vacía xs, se verifica que
take n (ciclica xs) == take n (cycle xs)
Nota. Al hacer la comprobación limitar el tamaño de las pruebas como se indica a continuación
λ> quickCheckWith (stdArgs {maxSize=7}) prop_ciclica +++ OK, passed 100 tests.
Elemento común en la menor posición
Definir la función
elemento :: Eq a => [a] -> [a] -> [a]
tal que (elemento xs ys) es la lista formada por el elemento común a xs e ys con la menor posición. Por ejemplo.
elemento [3,7,6,9,8,0] [5,4,2,7,8,6,9] == [7] elemento [3,7,6,9] [9,5,6] == [9] elemento [5,3,6] [7,6,3] == [3] elemento [3,7,6,3,8,0] [5,4,9,1,4,2,1] == []
Nota: Como se observa en el 3ª ejemplo, en el caso de que un elemento x de xs pertenezca a ys y el elemento de ys en la misma posición que x pertenezca a xs, se elige como el de menor posición el de xs.
Cuantificadores sobre listas
Definir la función
verificaP :: (a -> Bool) -> [[a]] -> Bool
tal que (verificaP p xs) se verifica si cada elemento de la lista xss contiene algún elemento que cumple el predicado p. Por ejemplo,
verificaP odd [[1,3,4,2], [4,5], [9]] == True verificaP odd [[1,3,4,2], [4,8], [9]] == False
Nota: Se puede definir por comprensión, recursión y plegado.
Inversa a trozos
Definir la función
inversa :: Int -> [a] -> [a]
tal que (inversa k xs) es la lista obtenida invirtiendo elementos de xs, k elementos cada vez. Si el número de elementos de xs no es un múltiplo de k, entonces los finales elementos de xs se dejen sin invertir. Por ejemplo,
inversa 3 [1..11] == [3,2,1,6,5,4,9,8,7,10,11] inversa 4 [1..11] == [4,3,2,1,8,7,6,5,9,10,11]
Comprobar con QuickCheck que la función inversa es involutiva; es decir, para todo número k>0 y toda lista xs, se tiene que (inversa k (inversa k xs)) es igual a xs