mapM/concatMapMy

John Hughes [email protected]
Tue, 24 Oct 2000 10:16:54 +0200 (MET DST)


	Sengan Baring-Gould writes:

	>Is >>= not lazy?

	since no experts have answered yet, this newbie will answer.
	I think it's strict.

Well, it depends. (>>=) is an overloaded operator, with a different
implementation for every monad -- when you define a monad, you give the
implementation of (>>=). If your implementation is strict (presumably in the
first operand), then (>>=) is strict *at that type*. If your implementation is
lazy, then it isn't. The same goes for (+): at most types (+) is strict, but
if you define your own kind of number with a lazy addition, then on that type
(+) will be lazy.

For many monads, (>>=) *is* strict, which fits with the intuition that it is a
`sequencing' operator. But by no means for all. The simplest counter-example
is the identity monad:

	newtype Id a = Id a

	instance Monad Id where
	  return = Id
	  Id x >>= f = f x

where m>>=f is strict in m only if f is a strict function. A more interesting
example is the state transformer monad:

	newtype ST s a = ST (s -> (a,s))

	instance Monad (ST s) where
	  return x = ST (\s -> (x,s))
	  ST h >>= f = ST (\s -> let (a,s') = h s
				     ST h' = f a
				 in h' s')

where once again, the implementation of (>>=) is strict only if f is a 
strict function. Hence `lazy state' makes sense!

John Hughes