BEGIN 16_10_06_GeneralizedFold.lhs

This script is entirely written in literate Haskell. Parts of
it are extracted from Section 3 (TREE-LIKE folds) and Section 7 (EXAMPLES)
in https://wiki.haskell.org/Fold

TREE-LIKE folds

The use of an initial value is mandatory when the combining function is
asymmetrical in its types, i.e. when the type of its result is
different from the type of list's elements. Then an initial value must
be used, with the same type as that of the function's result, for a
linear chain of applications to be possible, whether left- or
right-oriented.

When the function is symmetrical in its types the parentheses may be
placed in arbitrary fashion thus creating a tree of nested
sub-expressions, e.g. ((1 + 2) + (3 + 4)) + 5. If the binary operation
is also associative this value will be well-defined, i.e. the same for 
any parenthesization, although the operational details of how it is
calculated will differ.

Both finite and indefinitely defined lists can be folded over in a
tree-like fashion (except, the foldt below, being recursive, can't
work with infinite lists):

> foldt            :: (a -> a -> a) -> a -> [a] -> a
> foldt f z []     = z
> foldt f z [x]    = x
> foldt f z xs     = foldt f z (pairs f xs)
 
> foldi            :: (a -> a -> a) -> a -> [a] -> a
> foldi f z []     = z
> foldi f z (x:xs) = f x (foldi f z (pairs f xs))
 
> pairs            :: (a -> a -> a) -> [a] -> [a]
> pairs f (x:y:t)  = f x y : pairs f t
> pairs f t        = t

In the case of foldi function, to avoid its runaway evaluation on
indefinitely defined lists (i.e. infinite lists) the function f must not 
always demand its second argument's value, at least not all of it, and/or 
not immediately (example below).

EXAMPLES

Using a Haskell interpreter, we can show the structural transformation
which fold functions perform by constructing a string as shown by exp1, exp2,
exp3, and exp4, below. First, we define a particular function myConcat to be
used by foldr, foldl, foldt, and foldi:

> myConcat = (\x y -> concat ["(",x,"+",y,")"])

> exp1 = foldr myConcat "0" (map show [1..13])

which should return "(1+(2+(3+(4+(5+(6+(7+(8+(9+(10+(11+(12+(13+0)))))))))))))"
 
> exp2 = foldl myConcat  "0" (map show [1..13])

which should return "(((((((((((((0+1)+2)+3)+4)+5)+6)+7)+8)+9)+10)+11)+12)+13)"
 
> exp3 = foldt myConcat "0" (map show [1..13])

which should return "((((1+2)+(3+4))+((5+6)+(7+8)))+(((9+10)+(11+12))+13))"
 
> exp4 = foldi myConcat "0" (map show [1..13])

which should return "(1+((2+3)+(((4+5)+(6+7))+((((8+9)+(10+11))+(12+13))+0))))"

END 16_10_06_GeneralizedFold.lhs