Haskell Hero

foldr i foldl jsou ternární funkce, jejímiž argumenty jsou:

• binární funkce f typu
  • foldr: b -> a -> a
  • foldl: a -> b -> a
• hodnota v typu a (na tuto hodnotu se výraz vyhodnotí v případě prázdného seznamu ve třetím argumentu, většinou se používá neutrální hodnota k funkci f)
• seznam [x1,x2,...,xn], jehož prvky jsou stejného typu jako argumenty funkce f, typ [a]

Funkce foldr s funkcí f, hodnotou v a seznamem [x1,x2,...,xn] udělá to, že mezi prvky x1, x2,...,xn nacpe funkci f a úplně nakonec vloží hodnotu v. Jednotlivé aplikace ozávorkuje zprava.

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

Funkce foldl udělá to samé, akorát aplikace ozávorkuje zleva a hodnotu v vloží na začátek.

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

Definice

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

Příklady

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 a foldl1 jsou binární funkce fungující stejně, jako funkce foldr a foldl, s tím rozdílem, že nejsou definované na prázdných seznamech. Tím pádem odpadá nutnost hodnoty v, na kterou se výraz vyhodnocuje v případě aplikace na prázdný seznam.

Definice

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

Příklady

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