[Haskell-cafe] Strict Monad

[Ryan Ingram]

2009/11/4 Álvaro García Pérez <agarcia at babel.ls.fi.upm.es>:
> 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