= Folds =
TODO:
{{{#!haskell
last :: [a] -> a
last xs = foldl (\_ x -> x) lastError xs
-- a necessary cludge
lastError :: a
lastError = errorEmptyList "last"
}}}
== Foldr ==
{{{foldr}}} encapsulates a recursive traverse of a list (of nested conses and the empty list - {{{(cons 1 (cons 2 (cons 3 '())))}}} with {{{'()}}} as the base-case of recursion, and uses the ''initial element'' for a given ''binary combiner procedure''.
Another way of "visualizing" what ''right fold'' or {{{foldr}}} does is to imaging that it ''transforms a whole given list'' (re-writes it) into a ''new expression'' (data-structure), such that all the "conses" {{{(:)}}} will be replaced with given ''binary combining function'' {{{f}}} and the ''initial value'' {{{i}}} will be used instead of {{{[]}}} at the end.
Then this "new expression" will be ''evaluated'' to produce a final value.
Another way of visualizing what folds are doing is to realize that expression {{{foldr (+) 0 [1,2,3,4,5]}}} is equivalent of transforming the list {{{[1,2,3,4,5]}}} into an expression {{{1 + (2 + (3 + (4 + (5 + 0)))}}} (''parenthesis in Haskell are used for precedence, like in Math'') and then evaluate it, while expression {{{foldl (+) 0 [1,2,3,4,5]}}} "produces" an expression {{{((((0 + 1) + 2) + 3) + 4) + 5}}} and evaluates it.
Think first in terms of plain substitution, without recursion.
{{{
foldr f z [1,2,3,4] = f 1 (f 2 (f 3 (f 4 z)))
}}}
{{{
foldl f a [1,2,3,4] = ((( a `f` 1) `f` 2) `f` 3) `f` 4
}}}
''Right'' fold ({{{foldr}}}) is a ''non-tail-recursive'' process - O(n) growth of stack space.
{{{
(define (foldr f z xs)
(if (null? xs)
z
(f (car xs) (foldr f z (cdr xs)))))
}}}
same in Haskell
{{{
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
}}}
and Erlang
{{{
foldr(F, Z, [H|T]) -> F(H, foldr(F, Z, T));
foldr(F, Z, []) when is_function(F, 2) -> Z.
}}}
In ''lazy languages'' such as Haskell {{{foldr}}} could be applied to so-called ''infinite lists'' like {{{[1..]}}} or {{{let ones = 1 : ones}}} when {{{f}}} is ''non-strict'' function. Each call to {{{foldr}}} then would "go only one level deep into the list {{{xs}}}" and a ''thunk'' (or a ''promise'') would be generated, to be called on the next recursive call for {{{foldr}}}.
Also notice that recursion on "infinite lists" has ''no base case'', so ''early termination'' must be encoded into {{{f}}}. Think of {{{take}}} or ''short-circuiting'' {{{or}}}.
''Strict function'' on an ''infinite list'' will not terminate (no ''base case'' will be ever reached).
Now realize that using {{{foldr}}} with a ''strict function'' (like {{{+}}}) in a ''lazy language'' is a "bad idea", because it generates a long chain of ''thunks'' "up to the base case" - exactly like it would be in case of a ''strict language'' like Erlang.
-----
Giving that we could ''re-define'' (re-write) almost any recursive procedure which does traverse of a list of ''nested conses'' in terms of {{{foldr}}}
First, realize that {{{foldr (:) []}}} replaces all the {{{(:)}}} with {{{(:)}}} and {{{[]}}} with {{{[]}}}. In other words, it ''builds a new list''.
We could define a {{{copy}}} procedure like this
{{{
copy = foldr (:) []
}}}
so
{{{
> copy [1,2,3]
[1,2,3]
}}}
''builds a new list'' (technically - a ''new "spine" of a list aliasing old values'').
In Scheme we have to write explicit {{{lambda}}} while Haskell uses "section" - another bit of ''syntactic sugar''.
{{{
(define (copy xs)
(foldr (lambda (x xs) (cons x xs)) '() xs))
}}}
In Haskell {{{(:)}}} is an abbreviation for {{{\x -> \y -> x : y}}} which is roughly equivalent to {{{(lambda (x y) (cons x y))}}} given that Haskell uses ''curried procedures'' to "emulate" a procedure with multiple arguments, using ''syntactic sugar'' for definition and application for curried procedures.
Details are [wiki:/HighOrderProcedures here]
There are few more classic recursive procedures on lists defined in terms of {{{foldr}}} and a combine procedure:
{{{
product = foldr (*) 1
}}}
Note that for multiplication 1 is an identity. 0 would turn everything to 0. it is identity for addition.
{{{
and = foldr (&&) True
}}}
notise the initial value.
{{{
length = foldr (\_ a -> a+1) 0
}}}
which is nothing but
{{{
(define (length xs)
(foldr (lambda (_ a) (+ 1 a)) 0 xs))
}}}
{{{every}}} using ''list comprehensions''
{{{
every f xs = and [f x |x <- xs]
}}}
which is the same as with explicit {{{map}}}
{{{
every f xs = and (map f xs)
}}}
which is
{{{
every f = foldr (\x a -> f x && a) True
}}}
remember that {{{f}}} must be a ''predicate function'' of type {{{a -> Bool}}},
Here is tail-recursive {{{reverse}}} which uses concatenation procedure {{{(++)}}} also known as {{{append}}}
{{{
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
}}}
It is efficient (it will be TCO-ed by compiler) but {{{(++)}}} itself is non-tail recursive:
{{{
[] ++ ys = ys
(x:xs) ++ ys = x : xs && ys
}}}
So, in terms of {{{foldr}}} we could define it as
{{{
xs ++ ys = foldr (:) ys xs
}}}
which shows chow exactly {{{foldr}}} encapsulates recursion.
There is another definition of {{append}}} which captures reverse in order of arguments {{{ys xs}}}
{{{
append = flip (foldr (:))
}}}
Now {{{reverse}}}
{{{
reverse = foldr (\x xs -> xs ++ [x]) []
}}}
Notice that {{{append}}} accepts only lists as its arguments, so we have to transform {{{x}}} into {{{[x]}}} before applying {{{++}}} and that we have ''reversed'' order of concatenation.
Here is the same in Scheme
{{{
(define (reverse xs)
(foldr (lambda (x xs) (append xs (list x))) '() xs)
}}}
where
{{{
(define (append xs ys)
(foldr (lambda (x xs) (cons x xs)) ys xs))
}}}
note how we have to write explicit {{{lambda}}} for consing.
{{{map}}} in terms of {{{foldr}}} and {{{compose}}} - {{{(.)}}}
{{{
map f = foldr ((:) . f) []
}}}
where
{{{
f . g = \x -> f (g x)
}}}
which is just
{{{
(define (compose f g)
(lambda (x) (f (g x))))
}}}
but we are using {{{lambda}}} instead of {{{compose}}}
{{{
(define (map f xs)
(foldr (lambda (x xs) (cons (f x) xs)) '() xs))
}}}
because we don't have ''implicit currying'' in Scheme, and our {{{cons}}} requires exactly two arguments, while in Haskell {{{(:)}}} is a curried procedure.
and {{{filter}}}
{{{
filter p = foldr f []
where
f x xs
| p x = x : xs
| otherwise = xs
}}}
== Foldl ==
''Left'' fold {{{foldl}}} is a ''tail-recursive'' process (a constant-space loop with an accumulator, that's why we are using {{{a}}} instead of {{{i}}} for a binding).
{{{
(define (foldl f a xs)
(if (null? xs)
a
(foldl f (f a (car xs)) (cdr xs))))
}}}
or in Haskell
{{{
foldl f a [] = a
foldl f a (x:xs) = foldl f (f a x) xs
}}}
or in Erlang
{{{
foldl(F, A, [H|T]) -> foldl(F, F(H, A), T);
foldl(F, A, []) when is_function(F, 2) -> A.
}}}
{{{foldl}}} is ''tail-recursive'', will be TCO-ed.
In Haskell, due to its ''lazy evaluation'' the accumulator will "grow" by building up an expression like {{{(((0 + 1) + 2) + 3) + 4}}} without evaluating it, until {{{foldl}}} will reach the base case of recursion.
There is a quick fix for this
{{{
foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f a [] = a
foldl' f a (x:xs) = let a' = f a x in seq a' (foldl f a' xs)
}}}
which just "evaluates" accumulator {{{a'}}} on each recursive call, like an ''eager evaluation'' version (Scheme) would do.
''Right'' fold could be defined as a "flipped" ''Left'' fold on a reversed list, to avoid ''non-tail recursion''.
{{{
(define (foldr f z xs)
(foldl (flip f) z (reverse xs))))
}}}
where
{{{
(define (flip f)
(lambda (x y) (f y x)))
}}}
This is more efficient definition of {{{reverse}}} - it runs in ''O(n)'' but still does ''consing'' (which is inefficient in non-pool-allocated implementations).
{{{
(define (reverse xs)
(foldl (flip cons) '() xs))
}}}
same in Haskell
{{{
reverse = foldl (flip (:)) []
}}}
Notice that there is no {{{append}}}.
{{{foldl}}} goes ''from left to right'' and {{{flip}}} does the job.