Strict Monad

[Álvaro García Pérez-2]

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:

> newtype StrictT m a = InStT { outStT :: m a }
>
> instance Monad m => Monad (StrictT m) where
>     return = InStT . return
>     m >>= t = InStT $ (\x -> x >>= (\a -> outStT $ t a)) $! (outStT m)
>
> instance MonadTrans StrictT where
>     lift = InStT

Is it common practice to use this monad and this transformer? Why is it not in the standard library? I looked for this monad in the literature but I didn't find anything similar. It seems naive to me that this has never been previously described. Am I doing something wrong and this is not a monad at all?

Alvaro.

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Ryan Ingram]

2009/11/4 Álvaro García Pérez <agarcia@...>:

> 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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Álvaro García Pérez-2]

You're right. It must be "data" not "newtype". I first wrote it with "data", but then I consider using "newtype" instead, as the identity monad does, and the fact that the transformer worked right with "newtype" got me confused. After some tests I finally realised that whenever you use "newtype" in your underlying monad then the transformer gives something which is not a monad.

The problem (I think) is as follows: If you write a transformer which turns your monads into strict ones, then it may give something which is not a monad for some particular strict monads. If you relax your trasnformer in order to always have a monad, then it won't be strict for some particular lazy monads. Is the same old problem lifted to the transformers world. Does this intuition make any sense? I'm always referring to using Haskell strict primitives, not CPS.

Alvaro.

El 5 de noviembre de 2009 06:19, Ryan Ingram <ryani.spam@...> escribió:

2009/11/4 Álvaro García Pérez <agarcia@...>:

> 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 -> fDoes this make sense, or am I  wrong intuition? 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

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe