Las funciones foldr
, foldl
, reduce
, etc realizan operaciones de reducción de modo que van acumulando operaciones a través de cada uno de los elementos de la lista para dar un resultado. Lo que da es un resultado final, que no tiene porqué ser un elemento de la lista, ni siquiera ser coincidente con el tipo de datos de los elementos.
foldr f z [x1, x2, ..., xn]
(aka "plegado por la derecha") recibe tres argumentos:
f
función acumuladora (eg: f x acc = acc + x
)
z
valor inicial
[x1, x2, ..., xn]
lista con la que operar
foldr f z [x1, x2, ..., xn]
es equivalente a f x1 (f x2 ... (f xn z)...)
, o sea, se aplica la función sobre el último elemento, se vuelve a aplicar con el penúltimo y el resultado anterior, así hasta llegar al primero que opera con el resultado que se obtiene del resto de la lista. Este hecho de empezar por la derechar hasta llegar al primero es por lo que se dice que "pliega desde la derecha", foldr
, ya que parece que va plegando la lista hasta quedarse con un solo valor.
Como preguntas en concreto por dos reducciones, veamos cómo funciona:
misterio1 lista = foldr (\x n -> x + 1) 0 lista
Aquí la función acumuladora ignora el primer argumento, es decir, ignora el acumulador. Con cada operación se ignora el resultado de la operación anterior por lo que podemos reducir el cálculo a lo siguiente:
foldr (\ x n -> x + 1) 0 [] == 0 -- valor inicial
foldr (\ x n -> x + 1) 0 (y:ys) == y + 1
Para el otro caso:
misterio2 lista = foldr (\x y -> 1 + y) 0 lista
La función acumuladora ignora el primer argumento, es decir el elemento de la lista. Va a ir sumando 1 al acumulador por cada elemento de la lista, lo que nos dará al final la longitud de la lista:
foldr (\x y -> 1 + y) 0 ys == length ys