En esta sección se indicarán varios patrones de tratamiento de estructuras recursivas.
Estos patrones se aplicarán principalmente a listas, pero muchos de ellos pueden generalizarse
a otras estructuras como árboles, rosales, etc.
Ejemplo (
aplica)
> aplica :: (a -> b) -> [a] -> [b]
> aplica f [] = []
> aplica f (x:xs) = f x : aplica f xs
Nota: La función aplica está predefinida como la función
map
Obsérvese la definición de las siguientes funciones
Ejemplo (
sumaLs)
> sumaLs :: Num n => [n] -> n
> sumaLs [] = 0
> sumaLs (x:xs) = x + sumaLs xs
Ejemplo (
prodLs)
> prodLs :: Num n => [n] -> n
> prodLs [] = 1
> prodLs (x:xs) = x * prodLs xs
Ejemplo (
longLs)
> longLs :: Num n => [a] -> n
> longLs [] = 0
> longLs (x:xs) = 1 + longLs xs
En la definición de las siguientes funciones, puede observarse que se utiliza
siempre un mismo patrón. Un caso básico cuando la lista está vacía, cuyo valor es
0, 1 y 0;
y un caso recursivo en el cual se realiza una operación combinando el elemento x con
el resultado de la llamada recursiva. La operación, en el primer caso es \x r -> x + r,
en el segundo caso es \x r -> x * r y en el último caso es \x r -> 1 + r.
El patrón descrito podría generalizarse en una función foldRight que tome como parámetros
el valor e a devolver en el caso básico y la operación op a realizar en el caso recursivo.
Ejemplo (
foldRight)
> foldRight :: (a -> b -> b) -> b -> [a] -> b
> foldRight op e [] = e
> foldRight op e (x:xs) = x `op` foldRight op e xs
?-foldRight (+) 0 [2,3,4]9
Nota: La función foldRight está predefinida como la función foldr
A partir de la función foldr, pueden redefinirse las funciones
sumaLs,prodLs y longLs.
Ejemplo (
sumaLs')
> sumaLs' = foldr (+) 0
Ejemplo (
prodLs')
> prodLs' = foldr (*) 1
Ejemplo (
longLs')
> longLs' = foldr (\x r -> 1 + r) 0
Además de las funciones anteriores, existen numerosas funciones que trabajan sobre listas y
que pueden definirse a partir de la función foldr
Ejemplo (
andLs)
> andLs :: [Bool] -> Bool
> andLs = foldr (&&) True
Nota: La función andLs está predefinida como la función and
Ejemplo (
orLs)
> orLs :: [Bool] -> Bool
> orLs = foldr (||) False
Nota: La función orLs está predefinida como la función or
Ejemplo (
append)
> append :: [a] -> [a] -> [a]
> append xs ys = foldr (\x r -> x : r) ys xs
Nota: La función append está predefinida como el operador (++)
Ejemplo (
vuelta)
> vuelta :: [a] -> [a]
> vuelta = foldr (\x r -> r ++ [x]) []
Nota: La función vuelta está predefinida como la función reverse
Ejemplo (
tomaMientras)
> tomaMientras :: (a -> Bool) -> [a] -> [a]
> tomaMientras f = foldr (\x r -> if f x then x:r else []) []
?-tomaMientras (>3) [6,5,2,4,1] [6,5]
Nota: La función tomaMientras está predefinida como la función
takeWhile
Ejemplo (
filtra)
> filtra :: (a -> Bool) -> [a] -> [a]
> filtra f = foldr (\x r -> if f x then x:r else r) []
?-filtra (>3) [6,5,2,4,1] [6,5,4]
Nota: La función filtra está predefinida como la función
filter
Ejemplo (
comb)
> comb :: [a] -> [b] -> [(a,b)]
> comb xs [] = []
> comb [] ys = []
> comb (x:xs) (y:ys) = (x,y):comb xs ys
?-comb [2,3,4] "hola"[(2,'h'),(3,'o'),(4,'l')]
Nota: La función comb está predefinida como la función zip
El lenguaje Haskell admite una notación que facilita la definición de listas. Esta notación es
similar a las definiciones matemáticas intensionales
Ejemplo (
cpares20)
La función cpares20 calcula los cuadrados de los números pares entre 1 y 20
> cpares20 :: [Integer]
> cpares20 = [x ^ 2 | x <- [1..20], x `mod` 2 == 0]
?-cpares20[4,16,36,64,100,144,196,256,324,400]
Ejemplo (
divisores)
La función divisores calcula los divisores de un número
> divisores :: Integer -> [Integer]
> divisores n = [d | d <- [1..n], n `mod` d == 0]
?-divisores 24[1,2,3,4,6,8,12,24]
La función foldr actúa de la siguiente forma:
foldr op e [x1,x2,x3] = x1 `op` (x2 `op` (x3 `op` e))
Como puede observarse, la operación se asocia hacia la derecha. El nombre foldr
viene de fold-right, a la derecha.
Es posible definir una función fold-left que se denominará foldl y realiza la asociación
a la izquierda.
foldl op e [x1,x2,x3] = ((e `op` x1) `op` x2) `op` x3
Ejemplo (
foldLeft)
> foldLeft :: (b -> a -> b) -> b -> [a] -> b
> foldLeft op e [] = e
> foldLeft op e (x:xs) = foldLeft op (e `op` x) xs
?-foldLeft (+) 0 [1,3,4]8
Nota: La función foldLeft está predefinida en Haskell como foldl
Cuando la operación op es asociativa y e es el elemento neutro de op,
se cunple que:
foldr op e = foldl op e
En general, foldr es más eficiente que foldl.
Sin embargo, foldl puede ser útil en cierto tipo de definiciones
Ejemplo (
ls2n)
La función ls2n convierte una lista de dígitos en un número decimal
> ls2n :: [Integer] -> Integer
> ls2n = foldl (\r a -> r * 10 + a) 0
?-ls2n [1,3,4]134
Si las listas no están vacías, puede ser necesario aplicar la operación sobre los elementos sin
utilizar un elemento básico. Los operadores foldr1 y foldl1 actúan de
la siguiente forma:
foldr1 op [x1,x2,x3] = x1 `op` (x2 `op` x3)
foldl1 op [x1,x2,x3] = (x1 `op` x2) `op` x3
Ejemplo (
maxLs)
La función maxLs devuelve el valor máximo de una lista de enteros
> maxLs :: [Integer] -> Integer
> maxLs = foldr1 max
?-maxLs [-1,-3,-4]-1
Los operadores predefinidos scanr, scanl, scanr1 y scanl1
recorren la lista generando resultados parciales de la siguiente forma:
scanr op e [x1,x2,x3] =
[x1 `op` (x2 `op` (x3 `op` e)), x2 `op` (x3 `op` e), x3 `op` e, e]
scanl op e [x1,x2,x3] =
[e, e `op` x1, (e `op` x1) `op` x2, ((e `op` x1) `op` x2) `op` x3]
scanr1 op e [x1,x2,x3] =
[x1 `op` (x2 `op` x3), x2 `op` x3, x3]
scanl1 op e [x1,x2,x3] =
[x1, x1 `op` x2, (x1 `op` x2) `op` x3]
Ejemplo (
ruffini)
La función ruffini aplica la regla de ruffini
> ruffini :: Float -> [Float] -> [Float]
> ruffini a = scanl1 (\r x -> r * a + x)
?-ruffini 3 [2,4,3][2,10,33]
La generación de una lista a partir de un valor puede capturarse mediante
la siguiente función
Ejemplo (
unfold)
La función unfold realiza el proceso inverso a la función foldr
> unfold :: (a -> Bool) -> (a -> b) -> (a -> a) -> a -> [b]
> unfold p f g x = if p x then []
> else f x : unfold p f g (g x)
Ejemplo (
d2b)
La función d2b convierte un número decimal en su representación binaria
> d2b :: Integer -> [Integer]
> d2b = reverse . unfold (==0) (`mod` 2) (`div` 2)
?-d2b 13[1,1,0,1]
Ejemplo (
pals)
La función pals convierte devuelve la lista de palabras que forman una cadena de caracteres
> pals :: String -> [String]
> pals = palsAux . quitaEsp
> where palsAux = unfold (=="") tomaPal quitaPal
> tomaPal = takeWhile (not . esp)
> quitaPal = quitaEsp . dropWhile (not . esp)
> quitaEsp = dropWhile esp
> esp x = x == ' ' || x == '\n'
?-pals "mi perro es listo"["mi","perro","es","listo"]
Los combinadores definidos en las secciones anteriores pueden
generalizarse para otras estructuras recursivas.
Ejemplo (
foldA)
La función foldA recorre y transforma un árbol en un valor
> foldA :: (a -> b -> b -> b) -> b -> Arbol a -> b
> foldA f e Hoja = e
> foldA f e (Rama x i d) = f x (foldA f e i) (foldA f e d)
La función sumaArbol calcula la suma de los nodos de un árbol
> sumaArbol :: Num n => Arbol n -> n
> sumaArbol = foldA (\x i d -> x + i + d) 0
?-sumaArbol a114
La función nodosArbol devuelve la lista de nodos de un árbol
> nodosArbol :: Arbol a -> [a]
> nodosArbol = foldA (\x i d -> [x] ++ i ++ d) []
?-nodosArbol a1[3,4,5,2]
Ejemplo (
foldRosal)
La función foldRosal recorre y transforma un rosal en un valor
> foldRosal :: (a -> [b] -> b) -> b -> Rosal a -> b
> foldRosal f e Vacio = e
> foldRosal f e (Nodo x ls) = f x (map (foldRosal f e) ls)
La función sumaRosal calcula la suma de los nodos de un rosal
> sumaRosal :: Num n => Rosal n -> n
> sumaRosal = foldRosal (\x ls -> x + sum ls) 0
La función nodosRosal devuelve la lista de nodos de un rosal
> nodosRosal :: Rosal a -> [a]
> nodosRosal = foldRosal (\x ls -> [x] ++ concat ls) []
Nota:
Sería deseable definir una función fold genérica que recorriese y transformase
todo tipo de estructuras recursivas. Aunque Haskell no permite este tipo de definiciones,
existe una extensión del lenguaje denominada Generic Haskell que permite
definir funciones genéricas, también denominadas politípicas.
Muchas estructuras recursivas básicas que en otros lenguajes están predefinidas, pueden
ser definidas por el usuario
Ejemplo (
hasta)
La función hasta captura un patrón recursivo básico
> hasta :: (a -> Bool) -> (a -> a) -> a -> a
> hasta p f x = if p x then x
> else hasta p f (f x)
