# What is the difference between Fix, Mu and Nu in Ed Kmett's recursion scheme package

In Ed Kmett's `recursion-scheme` package, there are three declarations:

``````newtype Fix f = Fix (f (Fix f))

newtype Mu f = Mu (forall a. (f a -> a) -> a)

data Nu f where
Nu :: (a -> f a) -> a -> Nu f
``````

What is the difference between those three data types?

Solution

• `Mu` represents a recursive type as its fold, and `Nu` represents it as its unfold. In Haskell, these are isomorphic, and are different ways to represent the same type. If you pretend that Haskell doesn't have arbitrary recursion, the distinction between these types becomes more interesting: `Mu f` is the least (initial) fixed point of `f`, and `Nu f` is its greatest (terminal) fixed point.

A fixed point of `f` is a type `T` an isomorphism between `T` and `f T`, i.e. a pair of inverse functions `in :: f T -> T`, `out :: T -> f T`. The type `Fix` just uses Haskell's built-in type recursion to declare the isomorphism directly. But you can implement in/out for both `Mu` and `Nu`.

For a concrete example, pretend for a moment that you can't write recursive values. The inhabitants of `Mu Maybe` , i.e. values `:: forall r. (Maybe r -> r) -> r`, are the naturals, {0, 1, 2, ...}; the inhabitants of `Nu Maybe`, i.e. values `:: exists x. (x, x -> Maybe x)`, are the conaturals {0, 1, 2, ..., ∞}. Think about the possible values of these types to see why `Nu Maybe` has an extra inhabitant.

If you want to get some intuition for these types, it can be a fun exercise to implement the following without recursion (roughly in increasing order of difficulty):

• `zeroMu :: Mu Maybe`, `succMu :: Mu Maybe -> Mu Maybe`
• `zeroNu :: Nu Maybe`, `succNu :: Nu Maybe -> Nu Maybe`, `inftyNu :: Nu Maybe`
• `muTofix :: Mu f -> Fix f`, `fixToNu :: Fix f -> Nu f`
• `inMu :: f (Mu f) -> Mu f`, `outMu :: Mu f -> f (Mu f)`
• `inNu :: f (Nu f) -> Nu f`, `outNu :: Nu f -> f (Nu f)`

You can also try to implement these, but they require recursion:

• `nuToFix :: Nu f -> Fix f`, `fixToMu :: Fix f -> Mu f`

`Mu f` is the least fixed point, and `Nu f` is the greatest, so writing a function `:: Mu f -> Nu f` is very easy, but writing a function `:: Nu f -> Mu f` is hard; it's like swimming against the current.

(At one point I was meaning to write a more detailed explanation of these types, but it might be a little too long for this format.)