haskellrecursive-datastructuresrecursion-schemesfixpoint-combinators# 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.)

- Comparing lists in Haskell
- Is there a non-identity monad morphism M ~> M that is monadically natural in M?
- Problem with loading module ‘Distribution.Simple’
- Improving efficiency in Stirling numbers calculation
- Does sequencing an infinite list of IO actions by definition result in a never-ending action? Or is there a way to bail out?
- How to call pgQuery from postgresql-query?
- How to avoid whitespace after a tag (link) in Hamlet templates?
- Understanding type-directed resolution in Haskell with existential types
- Why is seq bad?
- Understanding bind function in Haskell
- How to create route that will trigger on any path in Servant?
- How do I use a global state in WAI middleware?
- nixos 23.11 cabal install mysql-simple problem - "Missing (or bad) C libraries"
- Is there a way to kill all forked threads in a GHCi session without restarting it?
- Why can an invalid list expression such as 2:1 be assigned to a variable, but not printed?
- Iterate over a type level list and call a function based on each type in the list
- How does this solution of Project Euler Problem 27 in the Haskell Wiki work?
- Why `Monad` is required to use `pure`?
- Can't do partial function definitions in GHCi
- recommended way to convert Double -> Float in Haskell
- Haskell profiling understanding cost centre summary for anonymous lambda
- Why is Haskell fully declarative?
- GHC Generating Redundant Core Operations
- Question about Event firing in reflex-frp
- Using Haskell's "Maybe", type declarations
- How can I elegantly invert a Map's keys and values?
- Why there is no output for wrapped IO in Haskell?
- What are the definitions of Weather and Memory in xmobar repo?
- Serializing a Data.Text value to a ByteString without unnecessary \NUL bytes
- Using Haskell with VS Code