[Haskell-cafe] Type inference
brianh at metamilk.com
Wed Feb 8 17:25:29 EST 2006
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.
More information about the Haskell-Cafe