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