[Haskell-cafe] problem using ST monad

[Daniel Fischer]

Am Sonntag, 26. Oktober 2008 02:18 schrieb Paul L:
> I'm have some trouble using the ST monad, and I think
> I'm confused about its use of existential type.
>
> > {-# OPTIONS -XRankNTypes #-}
> > import Control.Monad.ST
> > import Data.Array.ST
>
> I want to implement a map function that unfold
>
> all ST monads in a list:
> > mapST :: (a -> (forall s . ST s b)) -> [a] -> [b]
> > mapST f (x:xs) = runST (f x) : mapST f xs
> > mapST f [] = []
>
> This is fine. However, it wouldn't typecheck if I
> had declared its type differently:
>
>   mapST :: (a -> ST s b) -> [a] -> [b]
>
> I first thought the reason could be that runST has to
> take something of type (forall s . ST s b), but apparently
>
> this is not the case:
> > g :: (STArray s Int Int -> ST s a) -> ST s a
> > g f = newArray (0,0) 0 >>= f
>
> with this definition,
>
>   runST (t (flip readArray 0))
>
> happily returns me 0, despite the fact that the "s" in the
> type of "g" is not existentially quantified.

Sure, (g (flip readArray 0)) :: ST s Int, or, explicitly, forall s. ST s Int,
there's nothing to restrict the s, so it's legitimate to pass it to runST.

>
> Then when I try this one:
>
>   mapST g [flip readArray 0]
>
> It fails to typecheck. Why?

The type of g is forall s. (STArray s Int Int -> ST s a) -> ST s a,
but mapST needs a function of type
a -> forall s. ST s b,
not
forall s. a -> ST s b.
Since for g, s appears in a, these types are different, s escapes.

>
> Is it possible, if at all, to implement a generic mapST?

What would be a generic mapST, which type should it have?