[Haskell-cafe] Composing functions with runST

[Yitzchak Gale]

Brandon S. Allbery KF8NH wrote:
> I think the problem is that technically runST is a data constructor
> (possibly not relevant)

No, at least not in GHC. It is a function.

> which takes a function as a parameter (definitely relevant).

It takes the type (forall s. ST s a) as its only parameter.
How is that more or less a function than anything else?

> In the normal compositional model, (f . g) x
> = f (g x), you're conceptually invoking f on the result of g x (g is
> independent of f); here, you're lifting the function g x into the ST
> s a monad via f (g is dependent on f).

I don't think I am using any special lifting mechanism here.
The "return" function does exploit the fact that ST s has a Monad
instance, but I only used the "return" function for simplicity. The
same thing happens if you construct a function that explicitly
returns (forall s. ST s a) and use that instead of "return":

Prelude Control.Monad.ST> :set -fglasgow-exts
Prelude Control.Monad.ST> let {f :: a -> (forall s. ST s a); f x = return x}
Prelude Control.Monad.ST> runST (f 42)
42
Prelude Control.Monad.ST> (runST . f) 42

<interactive>:1:9:
    Couldn't match expected type `forall s. ST s a'
           against inferred type `ST s a1'
...

Here is another possible clue to what is happening. When I
try to define that same function f using monomorphic syntax,
it fails:

Prelude Control.Monad.ST> let {f :: a -> (forall s. ST s a); f = return}

<interactive>:1:39:
    Inferred type is less polymorphic than expected
      Quantified type variable `s' escapes
      Expected type: a -> forall s1. ST s1 a
      Inferred type: a -> ST s a
    In the expression: return
    In the definition of `f': f = return

(Of course, the MR is not relevant here, because I am providing
an explicit type signature.)

_ _ ...   ... _ _
-Yitz