2009/11/4 Álvaro García Pérez
Hi,
I'm trying to characterise some strict monads to work with a particular lambda-calculus evaluator, as an alternative to CPS monad.
In the thread "Stupid question #852: Strict monad" the implementation of some strict monads (and pseudo-monads, not meeting the identity laws) is discussed. It's clear form that thread that using pattern-matching in the (>>=) operation will force evaluation, then the Id monad defined with pattern-matching is strict (and it's indeed a monad):
newtype Id a = Id a
instance Monad Id where return = Id (Id a) >>= f = f a
But it's impossible to derive a monad transformer from it, because you don't know the constructors of the monads you're transforming. I then tried to use strict application ($!). My first attempt was
newtype Strict a = InSt { outSt :: a }
instance Monad Strict where return = InSt m >>= f = (\x -> f x) $! (outSt m)
which is not a monad (doesn't meet the left identity law).
(return undefined) >>= (\x -> const (return 1) x) =/= (return 1)
Then I wondered if it was enough to force the evaluation of the whole monad, instead of the value inside the monad, yielding the second attempt:
newtype Strict a = InSt { outSt :: a }
instance Monad Strict where return = InSt m >>= f = (\x -> f (outSt x)) $! m
I placed the outSt inside the anonymous function, leaving the monad on the right of the ($!). This meets the identity laws and surprisingly (I was expecting a lazy behaviour) implements strict semantics (it behaves like CPS, which is strict as well). A transformer from this monad can be easily written:
This seems like it has the same problem to me: return undefined >>= const return 1 = InSt undefined >>= const return 1 = (\x -> (const return 1) (outSt x)) $! (InSt undefined) = let y = InSt undefined in seq y ((\x -> (const return 1) (outSt x)) y) = undefined -- since InSt is a newtype. You would get different behavior with data InStD a = InStD a which puts another element in the domain: InSt () contains [_|_, InSt ()] only whereas InStD () contains [_|_, InStD _|_, InStD ()] -- ryan