Control/Monad/Fix.hs

   1 -----------------------------------------------------------------------------
   2 -- |
   3 -- Module      :  Control.Monad.Fix
   4 -- Copyright   :  (c) Andy Gill 2001,
   5 --                (c) Oregon Graduate Institute of Science and Technology, 2002
   6 -- License     :  BSD-style (see the file libraries/base/LICENSE)
   7 -- Maintainer  :  libraries@haskell.org
   8 -- Stability   :  experimental
   9 -- Portability :  portable
  10 --
  11 -- Monadic fixpoints.
  12 --
  13 -- For more details, see Levent Erkok's thesis,
  14 -- /Value Recursion in Monadic Computations/, 2002.
  15 --
  16 -----------------------------------------------------------------------------
  17
  18 module Control.Monad.Fix (
  19         MonadFix(
  20            mfix -- :: (a -> m a) -> m a
  21          ),
  22         fix     -- :: (a -> a) -> a
  23   ) where
  24
  25 import Prelude
  26 import System.IO
  27
  28 -- | @'fix' f@ is the least fixed point of the function @f@.
  29 fix :: (a -> a) -> a
  30 fix f = let x = f x in x
  31
  32 -- | Monads having fixed points with a \`knot-tying\' semantics.
  33 -- Instances of 'MonadFix' should satisfy the laws
  34 --
  35 -- [purity]
  36 --      @'mfix' ('return' . h)  =  'return' ('fix' h)@
  37 --
  38 -- [left shrinking (or tightening)]
  39 --      @'mfix' (\x -> a >>= \y -> f x y)  =  \y -> 'mfix' (\x -> f x y)@
  40 --
  41 -- [sliding]
  42 --      @'mfix' ('Control.Monad.liftM' h . f)  =  'Control.Monad.liftM' h ('mfix' (f . h))@,
  43 --      for strict @h@.
  44 --
  45 -- [nesting]
  46 --      @'mfix' (\x -> 'mfix' (\y -> f x y))  =  'mfix' (\x -> f x x)@
  47 --
  48 -- This class is used in the translation of the recursive @do@ notation
  49 -- supported by GHC and Hugs.
  50 class (Monad m) => MonadFix m where
  51         -- | The fixed point of a monadic computation.
  52         -- @'mfix' f@ executes the action 'f' only once, with the eventual
  53         -- output fed back as the input.  Hence @f@ should not be strict,
  54         -- for then @'mfix' f@ would diverge.
  55         mfix :: (a -> m a) -> m a
  56
  57 -- Instances of MonadFix for Prelude monads
  58
  59 -- Maybe:
  60 instance MonadFix Maybe where
  61     mfix f = let a = f (unJust a) in a
  62              where unJust (Just x) = x
  63
  64 -- List:
  65 instance MonadFix [] where
  66     mfix f = case fix (f . head) of
  67                []    -> []
  68                (x:_) -> x : mfix (tail . f)
  69
  70 -- IO:
  71 instance MonadFix IO where
  72     mfix = fixIO