[Haskell-cafe] Master's thesis topic sought

Brent Yorgey byorgey at seas.upenn.edu
Fri Nov 6 17:25:06 EST 2009


On Fri, Nov 06, 2009 at 03:29:47PM +0000, Stephen Tetley wrote:
> Hello all,
> 
> Are any of the of the more exotic recursion schemes definable without
> a least-fixed point /Mu/ type?

Note that Haskell datatypes have a built-in implicit "mu" (that is,
every recursive Haskell datatype can be thought of as the fixed point
of some suitable functor); the "Mu" type you see in the types of those
recursion schemes just makes the knot-tying explicit.  Given any
particular recursive type, it should be possible to implement any of
the recursion schemes specifically for that type without mentioning
Mu.  However, to write recursion schemes that work generally over
*any* recursive type (aside from generic programming techniques)
requires the explicit use of the Mu type, because you need to be able
to refer to the functor of which the recursive type is a fixed point,
and there's no (easy) way to take a recursive Haskell data type and
"unfix" it to get the underlying structure functor.

-Brent


More information about the Haskell-Cafe mailing list