When is explicit recursion necessary?

Question

In Haskell, it is idiomatic to write as much of your code in higher-order functions like folds, maps, and unfolds as possible. So what kinds of code can't be written with those higher-order functions? When is explicit recursion necessary?

Answer 1

Let's assume we have a language without recursion or anything like it. This means no looping structures either. It also means we have (non-recursive) types as well so that we can't form a Y-combinator and escape. In this language, we are truly weak, separated from so many of our tools.

But we can ask a very good question about this language. Namely, what is the smallest thing we must give it in order for it to become just as powerful as a language with no such restrictions?

It turns out there are two answers.

1. We can introduce recursive binders, like a let rec command or something like Haskell's let which is always let rec. In other words, a structure which lets us define let x = e in b such that if x is free in e then it is computed as a fixed point on the equation x = e.

2. We can introduce the function fix :: (a -> a) -> a such that fix f reduces in one step to f (fix f).

It should be clear from the above presentation that fix can be implemented using recursive binders. What's a little less clear is that recursive binders can be implemented from non-recursive ones using fix, but here we are:

let x = fix $ \this -> e

The value this refers to the whole expression which ends up bound as x which is just what we want.

---

So why did I go out of my way to say all of the above?

Essentially, I'd like to argue that it's not possible to say that recursion is necessarily implemented via HOF combinators like map so long as you're willing to consider fix on that list. I'd also like to argue that any recursion implemented by combinators in that set can be done "explicitly" using recursive binders. They're equally powerful.

The interesting part comes in when you consider HOF combinators like foldr/unfoldr by themselves. These are technically somewhat weaker than fix/recursive binders. The advantage is that if you build a programming language off only a select set of foldr/unfoldr-like principles then you can get a very rich, sub-Turing complete language which can be total or guaranteed to terminate.

Answer 2

I think a lot of people find recursive data definitions easier to read than Mu/Fix/Nu types. It's not strictly necessary, but very useful there.

Similarly, you'll write the Foldable/Unfoldabe instances for such a data type by using recursion, but once those are provided, explicit recursion is not required going forward.