- 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)
