fix package:unification-fd

Fix f is a fix point of the Functor f. Note that in Haskell the least and greatest fixed points coincide, so we don't need to distinguish between Mu f and Nu f. This type used to be called Y, hence the naming convention for all the yfoo functions. This type lets us invoke category theory to get recursive types and operations over them without the type checker complaining about infinite types. The Show instance doesn't print the constructors, for legibility.

This module provides a fixed point operator on functor types. For Haskell the least and greatest fixed points coincide, so we needn't distinguish them. This abstract nonsense is helpful in conjunction with other category theoretic tricks like Swierstra's functor coproducts (not provided by this package). For more on the utility of two-level recursive types, see:

• Tim Sheard (2001) Generic Unification via Two-Level Types and Parameterized Modules, Functional Pearl, ICFP.
• Tim Sheard & Emir Pasalic (2004) Two-Level Types and Parameterized Modules. JFP 14(5): 547--587. This is an expanded version of Sheard (2001) with new examples.
• Wouter Swierstra (2008) Data types a la carte, Functional Pearl. JFP 18: 423--436.