Blog de un opositor/a: julio 2012

4. Técnicas de programación Recursiva

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.

4.1. Aplicar una función a cada elemento

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

4.2. Recorrer y transformar una estructura en un valor

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

4.3. Combinar dos estructuras

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

4.4. Listas intensionales

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]

4.5. Otras posibilidades de recorrer y transformar una lista en un valor

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

4.6. Recorrer y transformar una estructura generando resultados parciales

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]

4.7. Generar una estructura

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"]

4.8. Otras estructuras recursivas

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.

4.9. Combinadores recursivos básicos

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)

Haskell (/ˈhæskəl/) es un lenguaje de programación estandarizado multi-propósito puramente funcional con semánticas no estrictas y fuerte tipificación estática. Su nombre se debe al lógico estadounidense Haskell Curry. En Haskell, "una función es un ciudadano de primera clase" del lenguaje de programación. Como lenguaje de programación funcional, el constructor de controles primario es la función. El lenguaje tiene sus orígenes en las observaciones de Haskell Curry y sus descendientes intelectuales.
Las características más interesantes de Haskell incluyen el soporte para tipos de datos y funciones recursivas, listas, tuplas, guardas y calce de patrones. La combinación de las mismas pueden resultar en algunas funciones casi triviales cuya versión en lenguajes imperativos pueden llegar a resultar extremadamente tediosas de programar. Haskell es, desde 2002, uno de los lenguajes funcionales sobre los que más se ha investigado. Se han desarrollado muchas variantes:

Versiones paralelas del MIT y Glasgow, ambas denominadas Parallel Haskell.
Más versiones paralelas y distribuidas de Haskell llamadas Distributed Haskell (anteriormente Goffin) y Eden
Una versión con ejecución especulativa: Eager Haskell
Varias versiones orientadas a objetos: Haskell++, O'Haskell y Mondrian.
Una versión educativa llamada Gofer desarrollada por Mark Jones que fue suplantada por Hugs (ver abajo).