typestype-inferencelambda-calculushindley-milner

What are some types and/or terms in system-f that cannot be expressed in Hindley Milner

I remember reading somewhere that Hindley Milner was a restriction on system-f. If that is the case, could someone please provide me with some terms that can be typed in system-f but not in HM.

Solution

  • Anything involving higher-ranked (i.e. "first-class") polymorphism. For example:

    lambda (f : forall A. A -> A). (f Int 1, f String "hello")

    This function would have the type (forall A. A -> A) -> Int * String, which is not expressible in HM, where all polymorphic type schemes must be in "prenex" form (i.e. the quantifier may only occur on the outside, never nested).