Some thoughts and exercises on folding

I assume you know what are foldl and foldr and have basic experience with them - you know how to express functions like sum, maximum using these folds. Here are some very nice diagrams showing fold and related functions.

Warmup exercise:

compose :: [a -> a] -> a -> a
compose [f1, f2, ..., fn] = f1 . f2 . ... . fn

Write map and compose using foldr. Write foldr using map and compose.

Solution at the end.

Automata
A finite automaton is some device that has finitely many states (finite memory), reads a string, letter by letter, and changes its state according to some fixed transition rules. For example, it can remember if the number of a's was even or odd - it toggles a single bit after each 'a'. Here's an automaton that checks if the whole word is built of 'x' and 'y' only:

aut = foldl (\state a -> state && (a == 'x' || a == 'y')) True

Automata are really doing foldl. In this case we could have written this more easily using all, but in general the behaviour can be quite complex.

Exercise:

I described a deterministic automaton - it always worked in the same way.

deterministic :: (a -> b -> a) -> a -> [b] -> a
deterministic = foldl

Now, we have a nondeterministic one - it can choose from some list of possible states and go on. Return all possible states the automaton could finish with.

nondeterministic :: (a -> b -> [a]) -> a -> [b] -> [a]

Don't worry about removing duplicates.



Solution:

You can regard a nondeterministic automaton as a deterministic one whose states are lists of states.

Our transition function is a -> b -> [a]. To use foldl, we need [a] -> b -> [a].

convert :: (a -> b -> [a]) -> [a] -> b -> [a]
convert f m a = concatMap (\x -> f x a) m

nondeterministic f s = foldl (convert f) [s]

Does the convert function remind you of something? We can easily change the code to work with Maybe - the automaton will be deterministic, but it will be able to abort the computation anytime. It could also ask the user about the next state using IO. It's the list monad.

convert' :: (Monad m) => (a -> b -> m a) -> m a -> b -> m a
convert' f m a = m >>= (\x -> f x a)

nondeterministic' :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a
nondeterministic' f s = foldl (convert' f) (return s)

This function is called foldM and is available in Control.Monad.

foldM :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a

Unfolding
Suppose you have types a,b such that b = 1 + a b. Then, by substituting this equality into itself, we get

b = 1 + ab = 1 + a(1 + ab) = 1 + a + aab = 1 + a + aa(1 + ab) = 1 + a + aa + aaa + aaab = ... = 1 + a + aa + aaa + ...

b has changed into 1 + a + a a + a a a + ... This is the same as a list, [a].

Equality of types x=y means that we can pair corresponding x's and y's. But we don't need that. Instead, we just need a map b -> 1 + a b that doesn't have to be an isomorphism. We can change all "equals" signs in above reasoning to ->:

b -> 1 + ab -> 1 + a(1 + ab) -> ... -> 1 + a + aa + ... -> [a]

and it stays OK. So, given a function (b -> 1 + a b), we get b -> [a]. This is known as unfolding. This name is very suggestive - we unfolded b into a list of a's. Since 1 + a is called in Haskell Maybe a, we have a higher order function

unfold :: (b -> Maybe (a, b)) -> (b -> [a])

Exercise: Write it.



Solution:

unfold f x = case f x of
            Nothing -> []
            Just (a,x') -> a:(unfold f x')

Data.List calls this function unfoldr.

If you invert this reasoning, given a function (f :: 1 + a b -> b) you get [a] -> b. This is folding. f Nothing is our initial value, and f $ Just (a,b) tells how to combine a and b.

Fold vs unfold
Some simple exercises. Recursion is not allowed directly, use only foldl, foldr and unfold.

1. Write factorial.

2. Write functions

toBinary :: Integer -> [Bool]
fromBinary :: [Bool] -> Integer

that convert between a natural number and its binary representation.
For example, fromBinary [False, True, True] == 6.

3. Now you have binary numbers. Write exponentiation by squaring.

power :: (Monoid a) => a -> Integer -> a

Exponent will be nonnegative.

A natural number is a list
An important degenerate case of lists are natural numbers. A list of () is really a natural number (its length). This is unary numeral system.

foldl :: (a -> b -> a) -> a -> [b] -> a

If we take b = (), we get

foldl' :: (a -> a) -> a -> Integer -> a

This is n-th power of a function.

Other resources
If you're interested in fold, check out these resources. They are really worth reading and will give you much insight and many intereresting ideas.

* A tutorial on the universality and expressiveness of fold
* The Monad.Reader 6
* Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire
* Proof methods for structured corecursive programs

Solution to the warmup exercise:

map f = foldr (\a x -> f x : a) []
compose = foldr (.) id
foldr f a xs = compose (map f xs) a

Here's another version of compose, by roconnor:

compose l x = foldr ($) x l