[Haskell-cafe] REALLY simple STRef examples

[Chad Scherrer]

Thanks, Simon. I've begun putting together some text describing very
simple STRef examples, as Bulat suggested earlier. I think I know how
to make it work, but I'll still need to work on typing subtleties. I'm
headed to bed now, but I'll go through this in detail when I get a
chance to try to get my head around it.

-Chad

On 8/4/06, Simon Peyton-Jones <simonpj at microsoft.com> wrote:
> Chad
>
> | x = runST $ return (1::Int)
>
> This code looks simple, but it isn't. Here are the types:
>
>        runST :: forall a.  (forall s. ST s a) -> a
>
>        ($) :: forall b c. (b->c) -> b -> c
>
>        return 1 :: forall s. ST s Int
>
> To typecheck, we must instantiate
>        b       with (forall s. ST s Int)
>        c       with Int
>
> In H-M that's impossible, because you can't instantiate a type variable
> (b) with a polytype (forall s. ST s Int).  GHC will now let you do that
> (a rather recent change), but in this case it's hard to figure out that
> it should do so.  Equally plausible is to instantiate b with (ST s'
> Int), where s' is a unification variable.
>
> One way to make this work is to look at $'s first argument first. Then
> it's clear how to instantiate b.  Then look at the second argument.  But
> if you look at the second argument first, matters are much less clear.
> GHC uses an algorithm that is insensitive to argument order, so it can't
> take advantage of the left-to-right bias of this example.
>
> It's unfortunate that such a simple-looking piece of code actually
> embodies a rather tricky typing problem!  Of course there is no problem
> if you don' use the higher order function $.  Use parens instead
>
>        x = runST (return 1)
>
> Simon
>
>
> | -----Original Message-----
> | From: haskell-cafe-bounces at haskell.org
> [mailto:haskell-cafe-bounces at haskell.org] On Behalf Of
> | Chad Scherrer
> | Sent: 19 July 2006 23:02
> | To: haskell-cafe at haskell.org
> | Subject: [Haskell-cafe] REALLY simple STRef examples
> |
> | I've looked around at the various STRef examples out there, but still
> | nothing I write myself using this will work. I'm trying to figure out
> | how the s is escaping in really simple examples like
> |
> | x = runST $ return 1
> |
> | y = runST $ do {r <- newSTRef 1; readSTRef r}
> |
> | Neither of these works in ghci - they both say
> |
> | <interactive>:1:0:
> |     Inferred type is less polymorphic than expected
> |       Quantified type variable `s' escapes
> |       Expected type: ST s a -> b
> |       Inferred type: (forall s1. ST s1 a) -> a
> |     In the first argument of `($)', namely `runST'
> |     In the definition of `it':
> |        ...
> |
> | I thought maybe I needed to replace 1 with (1 :: Int) so the state
> | representation didn't force the type, but it still gives the same
> | result.
> |
> | Can someone point me to the simplest possible runST example that
> | actually works? Thanks!
>


-- 

Chad Scherrer

"Time flies like an arrow; fruit flies like a banana" -- Groucho Marx