– or “polymorphic fixed point combinator”

This article explains recursion combinators and polymorphic recursion, and deduces a polymorphic recursion combinator.

Haskell allows us to write recursive functions, that is functions which refer to themselves in their definitions. Here is a recursively defined (and somewhat inefficient) list length function.

```
-- Type can be inferred
lengthList :: [a] -> Int
= case xs of
lengthList xs -> 0
[] :rest) -> 1 + lengthList rest (_
```

```
> lengthList [1,2,3]
3
```

Another approach is to factor out the recursive call and make the
recursion happen elsewhere. Notice how the parameter `recurse`

replaces the recursive call.

```
-- Type can be inferred
lengthListF :: ([a] -> Int) -> [a] -> Int
= case xs of
lengthListF recurse xs -> 0
[] :rest) -> 1 + recurse rest
(_
-- Type can be inferred
lengthList2 :: [a] -> Int
= lengthListF lengthList2 lengthList2
```

```
-- > lengthList2 [1,2,3]
-- 3
```

We can abstract this pattern even further by writing a “recursion combinator” or “fixed point combinator”.

```
-- Type can be inferred
fix :: (a -> a) -> a
= f (fix f) fix f
```

The recursion combinator allows us to write

```
-- Type can be inferred
lengthList3 :: [a] -> Int
= fix lengthListF lengthList3
```

```
-- > lengthList3 [1,2,3]
-- 3
```

As an aside, the actual definition of `fix`

in the Haskell standard
library is a more efficient version, but that’s not important in this
article.

```
-- More efficient fix
fix :: (a -> a) -> a
= let x = f x in x fix f
```

As well as recursive data structures and functions like lists and
`length`

, Haskell also allows us to write *polymorphically* recursive
data structures and functions.

```
data Nested a = Nil | a :< Nested [a]
infixr 5 :<
= 1 :< [2, 3] :< [[3, 4], [5]] :< Nil nested
```

`Nested`

is recursively defined in terms of itself but the recursive
parameter is `[a]`

not the original `a`

, so this recursive data type
definition is called “polymorphic”. We can write a recursive function
to calculate the length of `Nested`

s.

```
-- Type cannot be inferred
lengthNested :: Nested a -> Int
= case ns of
lengthNested ns Nil -> 0
:< nns -> 1 + lengthNested nns _
```

```
-- > lengthNested nested
-- 3
```

This is a *polymorphically* recursive function because the type of the
argument `ns`

, `Nested a`

, differs from the type of the argument to
the recursive call `nns`

, which is `Nested [a]`

. Nonetheless we can
play the same trick as above, replacing the recursive call with a
parameter.

```
-- Type can be inferred
lengthNestedF :: (Nested [a] -> Int) -> Nested a -> Int
= case ns of
lengthNestedF recurse ns Nil -> 0
:< nns -> 1 + recurse nns
_
-- Type cannot be inferred
lengthNested2 :: Nested a -> Int
= lengthNestedF lengthNested2 lengthNested2
```

```
-- > lengthNested3 nested
-- 3
```

But trying to define this in terms of `fix`

does not work.

```
lengthNested2 :: Nested a -> Int
= fix lengthNestedF
lengthNested2
-- Couldn't match type `a' with `[a]'
```

The argument to `lengthNestedF`

has type `Nested [a] -> Int`

and the
return value has type `Nested a -> Int`

. `fix`

will not work here
because the argument and return type must be the same. We can try to
be sneaky by providing a more general type.

```
-- Requires RankNTypes
-- Type cannot be inferred
lengthNestedF2 :: (forall a. Nested a -> Int) -> Nested a -> Int
= case ns of
lengthNestedF2 recurse ns Nil -> 0
:< nns -> 1 + recurse nns _
```

This gets us closer but not close enough.

```
lengthNested2 :: Nested a -> Int
= fix lengthNestedF
lengthNested2
-- Couldn't match type `forall a1. Nested a1 -> Int'
-- with `Nested a -> a'
```

What hope is there of representing polymorphic recursion with a
combinator? The answer is that we need to generalise the type of
`fix`

.

```
-- Requires ScopedTypeVariables
-- Type signature must be provided.
fixPolymorphic :: forall f. ((forall a. f a) -> (forall a. f a))
-> forall a. f a
= let x :: f b
fixPolymorphic f = f x
x in x
```

To use this with `lengthNestedF2`

we also need an ad hoc data type
that does nothing except massage the type `Nested a -> Int`

into a
different form.

```
newtype NestedFunction a =
NestedFunction { unNestedFunction :: Nested a -> Int }
-- Type signature is not required
lengthNested2 :: Nested a -> Int
=
lengthNested2 -> NestedFunction
unNestedFunction (fixPolymorphic (\x
(lengthNestedF2 (unNestedFunction x))))
```

```
-- > lengthNested2 nested
-- 3
```

Because `NestedFunction`

is a `newtype`

, `NestedFunction`

and
`unNestedFunction`

don’t actually do anything. We only need
`NestedFunction`

to massage type parameters around. Morally, the
definition of `lengthNested2`

is just

```
lengthNested2 :: Nested a -> Int
= fixPolymorphic lengthNestedF2 lengthNested2
```

And there we have it, a polymorphic recursion combinator.

It’s a bit disappointing that we have *two* different combinators,
though. Can we combine them? Yes! With another ad hoc data type

`newtype Forall f = Forall { unForall :: forall a. f a }`

we can write

```
fixPolymorphic2 :: forall f. ((forall a. f a) -> (forall a. f a))
-> forall a. f a
= unForall (fix (\x -> Forall (f (unForall x)))) fixPolymorphic2 f
```

As above, `Forall`

and `unForall`

really don’t do anything, and
morally the definition of the polymorphic recursion combinator is

```
fixPolymorphic2 :: forall f. ((forall a. f a) -> (forall a. f a))
-> forall a. f a
= fix f fixPolymorphic2 f
```

That is, recursion and polymorphic recursion in Haskell are exactly the same thing!

(Thanks to winterkoninkje on Reddit for explaining a type system issue.)