Understanding the Fix datatype in Haskell

Question

In this article about the Free Monads in Haskell we are given a Toy datatype defined by:

data Toy b next =
    Output b next
  | Bell next
  | Done

Fix is defined as follows:

data Fix f = Fix (f (Fix f))

Which allows to nest Toy expressions by preserving a common type:

Fix (Output 'A' (Fix Done))              :: Fix (Toy Char)
Fix (Bell (Fix (Output 'A' (Fix Done)))) :: Fix (Toy Char)

I understand how fixed points work for regular functions but I'm failing to see how the types are reduced in here. Which are the steps the compiler follows to evaluate the type of the expressions?

Ogive

Try to compare that to the plain recursive type definition data ToyR b = OutputR b (ToyR b) | BellR (ToyR b) | DoneR. You'll find that they have the same values, except that the Fix variant has an additional Fix constructor after each Toy constructor. This is needed to fold the type from Toy b (Fix (Toy b)) to Fix (Toy b). – Stavanger

Answer 1

I'll make a more familiar, simpler type using Fix to see if you'll understand it.

Here's the list type in a normal recursive definition:

data List a = Nil | Cons a (List a)

Now, thinking back at how we use fix for functions, we know that we have to pass the function to itself as an argument. In fact, since List is recursive, we can write a simpler nonrecursive datatype like so:

data Cons a recur = Nil | Cons a recur

Can you see how this is similar to, say, the function f a recur = 1 + recur a? In the same way that fix would pass f as an argument to itself, Fix passes Cons as an argument to itself. Let's inspect the definitions of fix and Fix side-by-side:

fix :: (p -> p) -> p
fix f = f (fix f)

-- Fix :: (* -> *) -> *
newtype Fix f = Fix {nextFix :: f (Fix f)}

If you ignore the fluff of the constructor names and so on, you'll see that these are essentially exactly the same definition!

---

For the example of the Toy datatype, one could just define it recursively like so:

data Toy a = Output a (Toy a) | Bell (Toy a) | Done

However, we could use Fix to pass itself into itself, replacing all instances of Toy a with a second type parameter:

data ToyStep a recur = OutputS a recur | BellS recur | DoneS

so, we can then just use Fix (ToyStep a), which will be equivalent to Toy a, albeit in a different form. In fact, let's demonstrate them to be equivalent:

toyToStep :: Toy a -> Fix (ToyStep a)
toyToStep (Output a next) = Fix (OutputS a (toyToStep next))
toyToStep (Bell next) = Fix (BellS (toyToStep next))
toyToStep Done = Fix DoneS

stepToToy :: Fix (ToyStep a) -> Toy a
stepToToy (Fix (OutputS a next)) = Output a (stepToToy next)
stepToToy (Fix (BellS next)) = Bell (stepToToy next)
stepToToy (Fix (DoneS)) = DoneS

---

You might be wondering, "Why do this?" Well usually, there's not much reason to do this. However, defining these sort of simplified versions of datatypes actually allow you to make quite expressive functions. Here's an example:

unwrap :: Functor f => (f k -> k) -> Fix f -> k
unwrap f n = f (fmap (unwrap f) n)

This is really an incredible function! It surprised me when I first saw it! Here's an example using the Cons datatype we made earlier, assuming we made a Functor instance:

getLength :: Cons a Int -> Int
getLength Nil = 0
getLength (Cons _ len) = len + 1

length :: Fix (Cons a) -> Int
length = unwrap getLength

This essentially is fix for free, given that we use Fix on whatever datatype we use!

Let's now imagine a function, given that ToyStep a is a functor instance, that simply collects all the OutputSs into a list, like so:

getOutputs :: ToyStep a [a] -> [a]
getOutputs (OutputS a as) = a : as
getOutputs (BellS as) = as
getOutputs DoneS = []

outputs :: Fix (ToyStep a) -> [a]
outputs = unwrap getOutputs

This is the power of using Fix rather than having your own datatype: generality.

Rackrent

So how does an object of type Cons a Int ever get created, if all I have is a Fix (Cons a) and a function (getLength) Cons a int -> Int? The only way I can get an Int from anything else is by using the getLength function, but for that, I already need a Cons a Int, which I don't have (I only have a Fix (Cons a)). – Receptacle

I get that if I have a Nil of ANY type, I can produce an Int 0, so in particular I could take a Fix (Cons a) and produce an Int if the value happens to be Nil. However, getLength is defined only for an input of type Cons a Int, even though Nil happens to be valid value for this type as well. – Receptacle

Never mind, I found the answer by studying this post: medium.com/@olxc/catamorphisms-and-f-algebras-b4e91380d134. Essentially, I forgot about fmap. Given our length function (Fix (Cons a) -> Int), it constructs a lifted function with type Cons (Fix (Cons a)) -> Cons a Int, so the magic happens there, where a Nil of type Fix (Cons a) gets "mapped" to a Nil of type Cons a Int by essentially doing nothing. :) – Receptacle

The definition of unwrap is not type-correct; you need to apply the accessor method of Fix to n first. See here: wiki.haskell.org/Catamorphisms – Miscue