Copyright | (c) Andy Gill 2001 (c) Oregon Graduate Institute of Science and Technology 2002 |
---|---|

License | BSD-style (see the file libraries/base/LICENSE) |

Maintainer | libraries@haskell.org |

Stability | experimental |

Portability | portable |

Safe Haskell | Trustworthy |

Language | Haskell2010 |

Monadic fixpoints.

For a detailed discussion, see Levent Erkok's thesis,
*Value Recursion in Monadic Computations*, Oregon Graduate Institute, 2002.

# Documentation

class Monad m => MonadFix m where Source #

Monads having fixed points with a 'knot-tying' semantics.
Instances of `MonadFix`

should satisfy the following laws:

*purity*`mfix`

(`return`

. h) =`return`

(`fix`

h)*left shrinking*(or*tightening*)`mfix`

(\x -> a >>= \y -> f x y) = a >>= \y ->`mfix`

(\x -> f x y)*sliding*

, for strict`mfix`

(`liftM`

h . f) =`liftM`

h (`mfix`

(f . h))`h`

.*nesting*`mfix`

(\x ->`mfix`

(\y -> f x y)) =`mfix`

(\x -> f x x)

This class is used in the translation of the recursive `do`

notation
supported by GHC and Hugs.

## Instances

is the least fixed point of the function `fix`

f`f`

,
i.e. the least defined `x`

such that `f x = x`

.

For example, we can write the factorial function using direct recursion as

`>>>`

120`let fac n = if n <= 1 then 1 else n * fac (n-1) in fac 5`

This uses the fact that Haskell’s `let`

introduces recursive bindings. We can
rewrite this definition using `fix`

,

`>>>`

120`fix (\rec n -> if n <= 1 then 1 else n * rec (n-1)) 5`

Instead of making a recursive call, we introduce a dummy parameter `rec`

;
when used within `fix`

, this parameter then refers to `fix'`

argument, hence
the recursion is reintroduced.