haskellrecursionfixpoint-combinators

How the type `Fix` and function `fix` are same in Haskell?

I'm trying to convince myself that type Fix and function fix are the same thing.
But I can't find the correlation between their definitions

-- definition of fix 
fix :: (p -> p) -> p
fix f = let {x = f x} in x -- or fix f = f (fix f)
-- definition of Fix
newtype Fix f = Fix { unFix :: f (Fix f) }

How does the constructor Fix fit into the form of (x -> x) -> x?

Solution

  • Look at the kind of the type constructor Fix:

    > :k Fix
Fix :: (* -> *) -> *

    The type constructor Fix is what's analogous to the function fix.

    The data constructor is something else. Following the explanation found in Understanding F-Algebras, Fix is an evaluator: it evaluates a term of type f (Fix f) to produce a value of type Fix f. This evaluation is lossless; you can recover the original value from the result using unFix.