Haskell Hero

foldr i foldl son funciones ternarias que toman como parámetros:

• una función binaria f de tipo
  • foldr: b -> a -> a
  • foldl: a -> b -> a
• un valor v de tipo a (la expresión se evalúa a este valor cuando el tercer parámetro es una lista vacía, normalmente se usa el valor neutro respecto de la función f)
• una lista [x1,x2,...,xn] cuyos elementos son del mismo tipo que los parámetros de la función f, de tipo [a]

La función foldr funciona de esta manera: Entre los elementos x1, x2, ..., xn pone la función f y al fin pone el valor v. Las aplicaciones individuales de la función f las pone entre paréntesis, empezando desde la derecha.

foldr f v [x1,x2,...,xn]  ~>*  f x1 (f x2 (... (f xn v)))

foldr f v [x1,x2,...,xn]  ~>*  x1 `f` (x2 `f` (... (xn `f` v)))

La función foldl hace lo mismo pero las aplicaciones las pone entre paréntesis, empiezando de la izquierda, y el valor v lo pone al principio.

foldl f v [x1,x2,...,xn]  ~>*  f (f (... (f v x1) x2) ... ) xn

foldl f v [x1,x2,...,xn]  ~>*   ((v `f` x1) `f` x2) ... `f` xn

Definición

foldr           ::  (b –> a –> a) –> a –> [b] –> a
foldr _ v []     =  v
foldr f v (x:s)  =  f x (foldr f v s)

foldl           ::  (a –> b –> a) –> a –> [b] –> a
foldl _ v []     =  v
foldl f v (x:s)  =  foldl f (f v x) s

Ejemplos

foldr (+) 0 [1..5]  ~>*  1 + (2 + (3 + (4 + (5 + 0))))  ~>*  15
foldl (+) 0 [1..5]  ~>*  ((((0 + 1) + 2) + 3) + 4) + 5  ~>*  15

foldr (^) 1 [2..4]  ~>*  2 ^ (3 ^ (4 ^ 1))
                    ~>*  2417851639229358349412352

foldl (^) 1 [2..4]  ~>*  ((1 ^ 2) ^ 3) ^ 4
                    ~>*  1

foldr1 y foldl1 son funciones binarias que funcionan de la misma manera que las funciones foldry foldl, solamente no se pueden aplicar a listas vacías. Por eso el valor v al que se evalúa la expresión cuando el tercer parámetro es una lista vacía no es necesario aquí.

Definición

foldr1         ::  (a –> a –> a) –> [a] –> a
foldr1 _ [x]    =  x
foldr1 f (x:s)  =  f x (foldr1 f s)

foldl1         ::  (a –> a –> a) –> [a] –> a
foldl1 f (x:s)  =  foldl f x s

Ejemplos

foldr1 (+) [1..5]  ~>*  1 + (2 + (3 + (4 + 5)))
foldl1 (+) [1..5]  ~>*  (((1 + 2) + 3) + 4) + 5

and

and  ::  [Bool] -> Bool
and   =  foldr (&&) True

or

or  ::  [Bool] -> Bool
or   =  foldr (||) False

sum

sum  ::  Num a => [a] -> a
sum   =  foldr (+) 0

product

product  ::  Num a => [a] -> a
product   =  foldr (*) 1

compose

compose  ::  [a -> a] -> a -> a
compose   =  foldr (.) id

minimum

minimum  ::  Ord a => [a] –> a
minimum   =  foldl1 min

maximum

maximum  ::  Ord a => [a] –> a
maximum   =  foldl1 max