wiki:ScopedTypeVariables

Version 11 (modified by ross@…, 8 years ago) (diff)

--

Scoped Type Variables

See ExtensionDescriptionHowto for information on how to write these extension descriptions. Please add any new extensions to the list of HaskellExtensions.

Brief Explanation

In Haskell 98, it is sometimes impossible to give a signature for a locally defined variable, e.g. cmp in

sortImage :: Ord b => (a -> b) -> [a] -> [a]
sortImage f = sortBy cmp
  where cmp x y = compare (f x) (f y)

The argument type of cmp is the type a in the signature of sortImage, but there is no way to refer to it in a type signature. Quantification of type variables over expressions is needed.

GHC provides three extensions that bind type variables:

  • Explicit foralls in type signature declarations. The bound variables scope over the function body, e.g.
    sortImage :: forall a b. Ord b => (a -> b) -> [a] -> [a]
    sortImage f = sortBy cmp
      where cmp :: a -> a -> Ordering
            cmp x y = compare (f x) (f y)
    
  • Pattern type signatures. Free variables in the type stand for new types in the scope of the pattern, e.g.
    sortImage (f::a->b) = sortBy cmp
      where cmp :: a -> a -> Ordering
            cmp x y = compare (f x) (f y)
    
  • Result type signatures, giving the type of both sides of the equation. Free variables in the type stand for new types in the scope, e.g.
    sortImage f :: [a] -> [a] = sortBy cmp
      where cmp :: a -> a -> Ordering
            cmp x y = compare (f x) (f y)
    

In the latter two cases, the variable can stand for any type, not necessarily a type variable as in these examples, i.e. the variable is existentially quantified. Hugs supports only pattern type signatures, with the type variables universally quantified.

In GHC, type variables in the head of a class or instance declaration scope over bindings in the where part.

References

Note that although GHC and Hugs use the same syntax, the meaning of type variables is quite different, and there are other differences too.

Pros

  • Allows better documentation (without them, some expressions cannot be annotated with their types).
  • Extensions such as RankNTypes and GADTs require such annotations, so even more important in conjunction with them.

Cons

  • Many different forms of scoped type variables in GHC makes them hard to reason about. For example:
        f :: a -> a 
        f = \x -> (x :: a)
    
    is rejected but
        g = let f :: a -> a = \x -> (x :: a) in f 
    
    is allowed.
  • With pattern and result signatures, one must examine outer bindings to determine whether an occurrence of a type variable is a binding. This creates a potential trap. A rule like ExplicitQuantification might be needed if these were put into the standard.

Proposal 1

Both let-bound and lambda-bound type variables are in scope in the body of a function, and can be used in expression signatures. However, just as a let-binding can shadow other values of the same name, let-bound type variables may shadow other type variables. Thus no type variables are ever already in scope in a let-bound signature. Lambda-bound type variables (e.g. in a pattern) do not shadow but rather refer to the same type. ExplicitQuantification is required for all expression type signatures but not let-bound signatures.

This proposal tries to strike a balance between backwards compatibility, avoiding accidental type errors, and simplicity. Let-bound type signatures always create a new scope, lambda-bound ones are always in the same scope, and it is clear from expression type signatures which are the scoped type vars.

(perhaps this text can be cleaned up further? what is a better term for expression type signature?)

Proposal 2

Restrict the above extensions to:

  • for function bindings, optional explicit foralls in type signatures.
  • for pattern bindings, result type signatures. Explicit universal quantification might be made mandatory.

plus binding of type variables in instance heads.