Funciones recursivas en listas

Hay dos enfoques para trabajar con listas:

• Escribir funciones utilizando definiciones recursivas que atraviesan la estructura de la lista.
• Utilizar funciones estandar. 

Se prefiere el segundo enfoque, pero las funciones estándar de procesamiento de listas deben definirse, y esas definiciones usan el primer enfoque (definiciones recursivas).

Se crea una lista a partir de la lista vacía [] y la función cons :: a → [a] → [a] la cual se puede escribir con ":"

Una lista se puede definir como : 

• [] o
• (x: xs) para algunas x (el encabezado de la lista) y xs (la cola) donde (x: xs) 

La lista esta definida de forma recursiva, el caso base de la recursión es [], el caso de recursión (o inducción) es (x: xs).

La longitud de una lista se puede calcular de forma recursiva de la siguiente manera:

length :: [a] -> Int           -- function type

length [] = 0                  -- base case

length (x:xs) = 1 + length xs  -- recursion case

filter recibe un predicado (una función que da un resultado booleano) y una lista, y devuelve una lista de los elementos que satisfacen el predicado.

filter :: (a->Bool) -> [a] -> [a]

filter (<5) [3,9,2,12,6,4] -- > [3,2,4]

La podemos definir así:

filter :: (a -> Bool) -> [a] -> [a]

filter pred []    = []

filter pred (x:xs)

  | pred x         = x : filter pred xs

  | otherwise      = filter pred xs

Muchos cálculos que serían calculados con bucles for / while en un lenguaje imperativo se expresan naturalmente como cálculos de lista en un lenguaje funcional.

En Haskell tenemos: 

• Map : Realizar un cálculo en cada elemento de una lista
• Foldl: Iterar sobre una lista, de izquierda a derecha 
• Foldr: Iterar sobre una lista, de derecha a izquierda

Es una buena práctica usar estas tres funciones cuando corresponda

Podemos expresar un gran cálculo "encadenando" una secuencia de funciones que realizan cálculos más pequeños. Por ejemplo tenemos un argumento de tipo a, aplicamos una función g :: a−> b, obteniendo un resultado intermedio de tipo b luego aplicamos una función f :: b−> c al resultado intermedio, obteniendo el resultado final de tipo c. El cómputo completo (primero g, luego f) se escribe como f∘g. Esta es la notación matemática tradicional; solo recuerda que en f∘g, las funciones se usan en orden de derecha a izquierda.

Haskell utiliza el . como operador de composición de funciones

(.) :: (b->c) -> (a->b) -> a -> c

(f . g) x = f (g x)