[Haskell-cafe] Type inference

[Brian Hulley]

Fred Hosch wrote:
> Is type inferencing in Haskell essentially the same as in SML? Thanks.

Well, that depends on what you mean by "essentially the same" ;-)

Both languages are based on the same Hindley-Milner type inference 
algorithm, so both suffer from the same problem that a function such as

       f g x y = (g x, g y)

can't be given a very satisfactory type (ie there exist perfectly good 
programs that will be rejected by both SML and Haskell due to limitations 
inherent in the kinds (excuse the pun) of type system that can be used with 
HM type inference)

However, Haskell has a lot of advanced features that are bolted on to this 
foundation, which SML doesn't. One such feature is arbitrary rank 
polymorphism, which allows you to use a function argument in more than one 
way within a function, for example (compile with ghc -fglasgow-exts):

      h :: (forall a. a->a) -> b -> c -> (b,c)
      h g x y = (g x, g y)  -- the argument g is used polymorphically

This function can't be written in SML. Note that although h is similar to f, 
there would not exist a type for h if g could be an arbitrary function ie 
a->d instead of a->a.

Of course SML's types are a bit different - they use tuples to introduce a 
notion of dimensionality and they don't have any higher order types.

SML also has a complicated thing called the "value restriction" because it 
allows mutable references to be altered via side effects. Because Haskell 
has no side effects, there is no need for a value restriction.

Regards, Brian.