It’s amazing how sometimes just having a different framing of the problem helps with developing a much deeper understanding of the problem. I was working through the exercises of the Data61 Functional Programming course, assisted by Brian McKenna’s video streams, and I came accross a definition of a *right fold* that can be thought of as “constructor replacement”:

The expression

`foldr f z list`

replaces in`list`

:

- Every occurence of the cons constructor
`(:)`

with`f`

- Any occurrence of the nil constructor
`[]`

with`z`

Or, to put it in a tweet:

Intuition for `foldr` as "constructor replacement" is very helpful!

— Igal Tabachnik (@hmemcpy) July 30, 2019

Given a list:

1 : 2 : 3 : []

foldr "replaces" the cons constructor (:) with a function:

1 `f` 2 `f` 3 `f` []

e.g.

foldr (*) 1 (1 : 2 : 3 : [])

replaces : with *, and [] with 1

== 1 * 2 * 3 * 1

== 6

So let’s use this new intuition to solve some course exercises using right folds only!

**Note**: you should attempt solving them yourself first! Spoilers ahead!

Let’s start with **List.hs**:

We get a definition of a list as follows:

data List t = Nil | t :. List t |

Like the builtin Haskell list type `[]`

, this custom `List`

is comprised of nil and cons data constructors, `Nil`

and `:.`

. The List module also defines a `foldRight`

function that operates on this `List`

. We will use all this information to implement the functions for `List`

using `foldRight`

only.

Let’s start with a couple of easy ones: `product`

and `sum`

. Given the following list:

1 :. 2 :. 3 :. Nil |

to get the product of all values, we replace:

`:.`

with`(*)`

`Nil`

with the neutral value`1`

.

Using `foldRight`

, we can now implement the `product`

function like so:

product :: List Int -> Int |

Thanks to Eta reduction, we can drop `xs`

from both sides of the equals sign, leaving us with:

product :: List Int -> Int |

The `sum`

function is implemented similarly, replacing `:.`

with `(+)`

and `Nil`

with `0`

:

sum :: List Int -> Int |

Let’s look at some more interesting functions in the List module.

## headOr

The `headOr`

function has the following signature:

-- | Returns the head of the list or the given default. |

The `_cons`

and `_nil`

arguments are placeholders, also called “typed holes”. This is a great Haskell feature, forcing the compiler to provide enough information about what types and values “fit” into those holes. We’ll use this information a bit later.

Let’s start from the end: the last argument to `foldRight`

is our list. Since it appears on both sides of the equation, we can omit it, simplifying to:

headOr :: a -> List a -> a |

Next is the replacements of the cons constructor `:.`

and `Nil`

. Let’s write down what we want our list to look like, using examples in the function signatures as guides. Here’s what our list looks after being “replaced” by `foldRight`

:

1 `f` 2 `f` 3 `f` n |

Where `Nil`

was replaced by the value `n`

. What should the function `f`

be?

The `foldRight`

function expects the `f`

to be a function with two arguments. In our case, we want to take just the first argument, ignoring everything else.

If we write down our list in a prefix notation, it becomes a bit more apparent:

f 1 (f 2 (f 3 n)) |

To satisfy the requirement of a binary function that ignores its second argument, we can write a lambda function `\a _ -> a`

, which takes two arguments and returns the first one:

headOr :: a -> List a -> a |

To go one step further, there exists a function called `const`

, which ignores its second argument, returning the first. This allows us to replace the lambda with `const`

and simplify the call even further, dropping the `n`

thanks to Eta reduction:

headOr :: a -> List a -> a |

## length

Following the steps above, the `length`

function:

-- | Return the length of the list. |

Similarly to `headOr`

, we want replace the `:.`

constructor with a function. Looking again at our list in its prefix form:

f 1 (f 2 (f 3 n)) |

In this case, we want to add `+1`

for every `f`

that we encounter, completely igoring the first argument. We can do this with a lambda that looks like this: `\_ b -> 1 + b`

, which we can further simplify to `\_ -> (1 +)`

, dropping the `b`

on both sides. Finally, we replace `Nil`

with `0`

, and our result is:

length :: List a -> Int |

## map

-- | Map the given function on each element of the list. |

With `map`

we want to preserve the data constructors, applying the mapping function `f`

to every element of the list. The typed hole suggests our first argument to `foldRight`

needs to have the type `a -> List b -> List b`

. We can satisfy it with the function `\a bs -> f a :. bs`

. The `Nil`

remains unchanged, and our final result is:

map :: (a -> b) -> List a -> List b |

## filter

-- | Return elements satisfying the given predicate. |

Very similar to `map`

, except we use the predicate `p`

to decide whether to take the element or drop it from our resulting list. The typed hole for `_cons`

is `a -> List a -> List a`

, satisfied with:

\x xs -> if p x then x :. xs else xs |

(I’m not using the names `a`

and `as`

because it screws up the syntax highlighter)

If the element `x`

matches the predicate `p`

, cons it to our result, otherwise just return the result. Final version:

filter :: (a -> Bool) -> List a -> List a |

## (++) aka append

-- | Append two lists to a new list. |

Here is where it gets mindblowing. The `(++)`

function takes two lists and appends them. Let’s visualize the two lists like this:

1 :. 2 :. 3 :. Nil |

This makes it very easy to see how we can use “constructor replacement” to append two lists: the `:.`

remains unchanged, and we replace `Nil`

with the second list! The result is:

(++) :: List a -> List a -> List a |

## flatten

-- | Flatten a list of lists to a list. |

Here is again the intuition for constructor replacement helps us find the answer - the `flatten`

functions takes a list of lists and *appends* them together into a single list! This should sound very familiar, as we *just* implemented a function that does that! We can use the `(++)`

function to append two lists together, so all we need to do is replace the `:.`

between the lists with `(++)`

! The result is:

flatten :: List (List a) -> List a |

Hopefully, by now, it became clear how thinking of the right fold as “constructor replacement” can help visualize and guide towards the correct implementation. I recommend finishing the rest of the `List`

module, then implement the `Optional`

module using only `foldRight`

.

I will continue the Data61 FP course, and will share more gems as I learn them! Stay tuned!