runST and function composition

by

The short answer is that type inference doesn’t always work with higher-rank types. In this case, it is unable to infer the type of (.), but it type checks if we add an explicit type annotation:

> :m + Control.Monad.ST
> :set -XRankNTypes
> :t (((.) :: ((forall s0. ST s0 a) -> a) -> (a -> forall s1. ST s1 a) -> a -> a) runST return) $ True
(((.) :: ((forall s0. ST s0 a) -> a) -> (a -> forall s1. ST s1 a) -> a -> a) runST return) $ True :: Bool

The same problem also happens with your first example, if we replace ($) with our own version:

> let app f x = f x
> :t runST `app` (return `app` True)
<interactive>:1:14:
    Couldn't match expected type `forall s. ST s t0'
                with actual type `m0 t10'
    Expected type: t10 -> forall s. ST s t0
      Actual type: t10 -> m0 t10
    In the first argument of `app', namely `return'
    In the second argument of `app', namely `(return `app` True)'

Again, this can be solved by adding type annotations:

> :t (app :: ((forall s0. ST s0 a) -> a) -> (forall s1. ST s1 a) -> a) runST (return `app` True)
(app :: ((forall s0. ST s0 a) -> a) -> (forall s1. ST s1 a) -> a) runST (return `app` True) :: Bool

What is happening here is that there is a special typing rule in GHC 7 which only applies to the standard ($) operator. Simon Peyton-Jones explains this behavior in a reply on the GHC users mailing list:

This is a motivating example for type inference that can deal with
impredicative types. Consider the type of ($):

($) :: forall p q. (p -> q) -> p -> q

In the example we need to instantiate p with (forall s. ST s a), and that’s what
impredicative polymorphism means: instantiating a type variable with a
polymorphic type.

Sadly, I know of no system of reasonable complexity that can typecheck
[this] unaided. There are plenty of complicated systems, and I have
been a co-author on papers on at least two, but they are all Too
Jolly Complicated to live in GHC. We did have an implementation of
boxy types, but I took it out when implementing the new typechecker.
Nobody understood it.

However, people so often write

runST $ do ...

that in GHC 7 I implemented a special typing rule, just for infix uses of ($). Just think of (f $ x) as a new
syntactic form, with the obvious typing rule, and away you go.

Your second example fails because there is no such rule for (.).

More Related Contents:

  1. What is the difference between . (dot) and $ (dollar sign)?
  2. What does (f .) . g mean in Haskell?
  3. Haskell function composition (.) and function application ($) idioms: correct use
  4. Haskell function composition operator of type (c→d) → (a→b→c) → (a→b→d)
  5. Dot Operator in Haskell: need more explanation
  6. `String’ is applied to too many type arguments
  7. Equal (=) Vs left arrow (
  8. Confused by the meaning of the ‘Alternative’ type class and its relationship to other type classes
  9. Is monad bind (>>=) operator closer to function composition (chaining) or function application?
  10. How can I poll files, sockets or handles to become readable/writable in Haskell?
  11. How to extract value from monadic action
  12. Large-scale design in Haskell? [closed]
  13. Splitting list into a list of possible tuples
  14. What is the purpose of the reader monad?
  15. Haskell: I/O and Returning From a Function
  16. Ordering of parameters to make use of currying
  17. No instance for (Fractional Int) arising from a use of `/’
  18. Prefix form of unary operator in Haskell
  19. How can I generate different random values in Haskell?
  20. Can you overload + in haskell?
  21. Non-Trivial Lazy Evaluation
  22. Is there a way to see the list of functions in a module, in GHCI?
  23. Haskell GHC: what is the time complexity of a pattern match with N constructors?
  24. Creating unique labels in Haskell
  25. What’s the status of multicore programming in Haskell?
  26. Tools for analyzing performance of a Haskell program
  27. Haskell Constraint is no smaller than the instance head
  28. Can I match a data constructor wildcard in Haskell?
  29. Is there, in Haskell, something similar to sub-guards?
  30. What is the Comonad typeclass in Haskell?

Leave a Comment