Two-list folds

Some functions take two lists as input, but we might still want to use a fold (for many reasons).

How can we use folds to create two-list functions?

Take one very common function - zip.

zip (x:xs) (y:ys) = (x, y): zip xs ys
 
zip _ _ = []

In many ways this looks like a fold - it has the single call back to itself, along with a base case.

So how to turn it into a fold? First - let’s look at the types.

zip :: [a] -> [b] -> [(a, b)]

We can rewrite this as:

zip :: [a] -> ([b] -> [(a, b)])

Now we can see - we need a fold on a list of type [a] that returns a function of type [b] -> [(a, b)]

Let’s establish the base case first: what does this function on an empty list look like? We already know:

zip [] ys = []

So we have our e:

zip = foldr f e
  where
    e = const []

Where we use the function const to just return [] regardless of the contents of ys. (This preserves (the lack of) strictness in the original zip.)

Now for the general case. We need a function of the following signature:

f :: a -> ([b] -> [(a,b)]) -> ([b] -> [(a, b)])

We can remove the last set of parentheses to make it clearer:

f :: a -> ([b] -> [(a, b)]) -> [b] -> [(a, b)]

What does this signify? f takes:

• An element of the first list
• A function that takes a list of type b and returns a list of type (a, b) by pairing the elements from the remainder of the first list with the input list.
• The list of elements of b.

We can now write our function:

f x g [] = []
f x g (y:ys) = (x, y): g ys

And now we can put it all together:

zip = foldr f (const [])
  where
    f x g [] = []
    f x g (y:ys) = (x, y) : g ys