ST monad and monad tranformers

[Reid Barton]

On Mon, Feb 02, 2009 at 06:03:15PM +0100, Josef Svenningsson wrote:
> Hi Tyson,
> 
> I also needed something like this a while ago so I knocked up a really
> simple module and put it on hackage:
> http://hackage.haskell.org/cgi-bin/hackage-scripts/package/STMonadTrans

Warning!  The STMonadTrans package uses State# nonlinearly, and as a
result, can violate referential transparency:

> import Control.Monad
> import Control.Monad.Trans
> import Control.Monad.ST.Trans
> 
> data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving Show
> 
> instance Monad Tree where
>   return = Leaf
>   Leaf a >>= k = k a
>   Branch l r >>= k = Branch (l >>= k) (r >>= k)
> 
> foo :: STT s Tree Integer
> foo = do
>   x <- newSTRef 0
>   y <- lift (Branch (Leaf 1) (Leaf 2))
>   when (odd y) (writeSTRef x y)
>   readSTRef x
> 
> main = do
>   print $ runST foo
>   let Branch _ (Leaf x) = runST foo
>   print x

prints

Branch (Leaf 1) (Leaf 1)
0

Evaluating the thunk in the left branch affects the value seen in the
right branch.  In general a monad transformer version of ST would need
to duplicate its state for each branch when used in conjunction with a
nondeterminism monad like Tree, which would make it not really
different from State, I think.

Regards,
Reid