– 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.
> 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.
-- > lengthList2 [1,2,3] -- 3
We can abstract this pattern even further by writing a “recursion combinator” or “fixed point combinator”.
The recursion combinator allows us to write
-- > 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.
As well as recursive data structures and functions like lists and
length, Haskell also allows us to write polymorphically recursive data structures and functions.
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
-- > lengthNested nested -- 3
This is a polymorphically recursive function because the type of the argument
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.
-- > lengthNested3 nested -- 3
But trying to define this in terms of
fix does not work.
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.
This gets us closer but not close enough.
What hope is there of representing polymorphic recursion with a combinator? The answer is that we need to generalise the type of
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.
-- > lengthNested2 nested -- 3
NestedFunction is a
unNestedFunction don’t actually do anything. We only need
NestedFunction to massage type parameters around. Morally, the definition of
lengthNested2 is just
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
we can write
unForall really don’t do anything, and morally the definition of the polymorphic recursion combinator is
That is, recursion and polymorphic recursion in Haskell are exactly the same thing!
(Thanks to winterkoninkje on Reddit for explaining a type system issue.)