In general, finds the “fixed point” of some endofunctor, which means some type t
, such that f t ~ t
. The simplest operator is often called Fix
, and takes advantage of a language’s primitive recursion to provide a very straightforward definition:
newtype Fix f = Fix { unfix :: f (Fix f) }
There are some problems with this, however:
- most languages provide general recursion (and, in fact, this definition requires it), so such a definition can’t be total; and