Sunday, April 1, 2012

“Inference” is “proof assistance”.

As a Lisper, I'm used to just writing out some code that more or less expresses what I mean, then trying it out. I don't want to mess around with proving that what I'm writing makes sense. Moreover, when I first started learning Haskell, I didn't know nearly enough to begin proving what I meant.

Fortunately, Haskell can figure out all the argument types and return types of very complex functions.¹ You know how to write a function that applies a function to each element of a list, and then combines all the resulting lists into one, so just write it:

    concatMap _ [] = []
concatMap f (x:xs) = f x ++ concatMap f xs
-- inferred type of concatMap is (t → [a]) → [t] → [a]

That's pretty nice; I didn't have to specify a single type, and Haskell figured out not only the types of the arguments and results, one of which was itself a function type, but figured out the precise level of polymorphism appropriate. A frequent mistake when trying to guess this type is writing (a → [a]) → [a] → [a], which is not as general as the inferred version above. It will compile, but unnecessarily (and often fatally) restrict users of the concatMap function.²

So inference helps you prove things, often avoiding or explaining generalizations you didn't think of. It is a “proof assistant”. It greatly aids in refactoring, if you continue to rely on it, as you have to fix your proof in fewer places when you change the rules. It's an absolutely vital tool for entry into the typeful world, when you frequently know how to write a function, but not how to express its true, maximally polymorphic type.

Unfortunately, the “proof assistant” can't figure out absolutely everything. Moreover, the semantics of the language and type system affect how much the assistant can prove.³


[1] Haskell is really figuring out “the types of very complex expressions”, but that doesn't sound quite so good, despite being quite a bit better.

[2] As it happens, we've restricted ourselves to lists, where concatMap actually makes sense for all monads, but that's a result of our using the list-only operations for our implementation, not a failure of the type inference. In Haskell terms, concatMapM f xs = join (liftM f xs), which is inferred as a Monad m ⇒ (t → m a) → m t → m a. Other generalizations are possible, and you can accidentally lock them down in exactly the same way as concatMap, including to our original inferred type.

[3] To be overly general, features like mutability and looking up functions by name on a receiver type make inference harder. These are the rule in Simula-inspired object-oriented environments, making inference harder in OOP, and conversely, easier in functional environments. For example, in the Java expression x.getBlah(y), you can't infer anything about getBlah until you know the type of x. But in Haskell, getBlah has one known type, albeit perhaps polymorphic or constrained by typeclasses, which can be used to infer things about x and y without necessarily knowing anything else about them.

No comments: