.
UPDATE: See the discussion at
http://groups.google.com/group/fa.haskell/browse_thread/thread/df7071830c8a4c4eLong I've been confused by what
Lazy and
Strict mean in the context of monads. I happened to come across the discussion [1] and then did some search. Now I seem to have a better idea.
IO is strict, and Identity, Reader, Writer, State are lazy. In fact, State has both a
strict version and a
lazy version. We can try to spot their differences. They key is in the (>>=) function. If (>>=) is strict in its left argument, i.e., destructs the argument before performing the next action, the monad is strict. Otherwise, lazy. This is well explained in
this post. Basically, the key difference is that one uses lazy
let-binding, while the other uses
case...of to force evaluation. The following example illustrates the difference.
import Control.Monad.State.Lazy as LS
import Control.Monad.State.Strict as SS
-- The final state is going to be 'undefined'. But since it's not used, we happily computes 0
testL = fst $ LS.runState (undefined >> return 0) 1
-- 'undefined' is forced to be evaluated before 'return 0'
testS = fst $ SS.runState (undefined >> return 0) 1
We show the Identity monad as another example. The
default version is a lazy one. The lazy let-binding approach and the strict case...of approach is general. But Identity is special, so we can define it in a more straightforward manner.
--
http://www.haskell.org/haskellwiki/Newtype data IdentityS a = IdentityS { runIdentityS :: a } deriving Show
instance Monad IdentityS where
return = IdentityS
(IdentityS m) >>= k = k m
testS = runIdentityS (undefined >> return 0)
Or, we can mimic the State monad.
-- 3. mimicking Control.Monad.State.Lazy
newtype Identity3 a = Identity3 { runIdentity3 :: a } deriving Show
instance Monad Identity3 where
return a = Identity3 a
m >>= k = Identity3 $ let
a = runIdentity3 m
in runIdentity3 (k a)
-- 5. mimicking Control.Monad.State.Strict
data Identity5 a = Identity5 { runIdentity5 :: a } deriving Show
instance Monad Identity5 where
return a = Identity5 a
-- m >>= k = Identity5 $ case runIdentity5 m of
-- a -> runIdentity5 (k a)
m >>= k = Identity5 $ case m of
Identity5 a -> runIdentity5 (k a)
Just for fun, let's play with fixed-points. First, the plain fixed-points.
-- import Data.Function
-- We can also define fix f = f $ fix f. But the standard definition allows sharing
fix :: (a -> a) -> a
fix f = let x = f x in x
-- the factorial function is the fixed point of facF
facF f = \i ->
if i == 0
then 1
else i * f (i - 1)
test3 = fix facF 3
Now, the monadic fixed-points.
-- import Control.Monad.Fix
class (Monad m) => MonadFix m where
-- | The fixed point of a monadic computation.
-- @'mfix' f@ executes the action @f@ only once, with the eventual
-- output fed back as the input. Hence @f@ should not be strict,
-- for then @'mfix' f@ would diverge.
mfix :: (a -> m a) -> m a
-- This default definition is NOT correct, but that is another post.
-- mfix f = (mfix f) >>= f
mfix f = let x = x >>= f in x
-- standard stuff from Control.Monad.Identity
-- instance MonadFix Identity where
-- mfix f = Identity (fix (runIdentity . f))
instance MonadFix IdentityL
-- mfix diverges due to strict (>>=)
instance MonadFix IdentityS
-- the factorial function is the monadic fixed point of facFM
facFM :: (Monad m) => (Int -> Int) -> m (Int -> Int)
facFM f = return (\i ->
if i == 0
then 1
else i * f (i - 1)
)
test1 = runIdentityL (mfix facFM) 3
test2 = runIdentityS (mfix facFM) 3