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 --
   8 -- Maintainer  :  libraries@haskell.org
   9 -- Stability   :  experimental
  10 -- Portability :  portable
  11 --
  12 -- The Fix monad.
  13 --
  14 --        Inspired by the paper
  15 --        /Functional Programming with Overloading and
  16 --            Higher-Order Polymorphism/,
  17 --          Mark P Jones (<http://www.cse.ogi.edu/~mpj>)
  18 --                Advanced School of Functional Programming, 1995.
  19 --
  20 -- Oct. 1st, 2002: Added instances for Lazy ST, ST, and List monads
  21 --
  22 -----------------------------------------------------------------------------
  23
  24 module Control.Monad.Fix (
  25         MonadFix(
  26            mfix -- :: (a -> m a) -> m a
  27          ),
  28         fix     -- :: (a -> a) -> a
  29   ) where
  30
  31 import Prelude
  32 import qualified Control.Monad.ST.Lazy as LazyST
  33 import qualified Control.Monad.ST as ST
  34 import System.IO
  35
  36 fix :: (a -> a) -> a
  37 fix f = let x = f x in x
  38
  39 class (Monad m) => MonadFix m where
  40         mfix :: (a -> m a) -> m a
  41
  42 -- Instances of MonadFix
  43
  44 -- Maybe:
  45 instance MonadFix Maybe where
  46     mfix f = let a = f (unJust a) in a
  47              where unJust (Just x) = x
  48
  49 -- List:
  50 instance MonadFix [] where
  51     mfix f = case fix (f . head) of
  52                []    -> []
  53                (x:_) -> x : mfix (tail . f)
  54
  55 -- IO:
  56 instance MonadFix IO where
  57     mfix = fixIO
  58
  59 -- Lazy State:
  60 instance MonadFix (LazyST.ST s) where
  61     mfix = LazyST.fixST
  62
  63 -- Strict State:
  64 instance MonadFix (ST.ST s) where
  65     mfix = ST.fixST