Search code examples
scalapolymorphic-functions

Are polymorphic functions "restrictive" in Scala?

In the book Functional Programming in Scala MEAP v10, the author mentions

Polymorphic functions are often so constrained by their type that they only have one implementation!

and gives the example

def partial1[A,B,C](a: A, f: (A,B) => C): B => C = (b: B) => f(a, b)

What does he mean by this statement? Are polymorphic functions restrictive?

Solution

  • Here's a simpler example:

    def mysteryMethod[A, B](somePair: (A, B)): B = ???

    What does this method do? It turns out, that there is only one thing this method can do! You don't need the name of the method, you don't need the implementation of the method, you don't need any documentation. The type tells you everything it could possibly do, and it turns out that "everything" in this case is exactly one thing.

    So, what does it do? It takes a pair (A, B) and returns some value of type B. What value does it return? Can it construct a value of type B? No, it can't, because it doesn't know what B is! Can it return a random value of type B? No, because randomness is a side-effect and thus would have to appear in the type signature. Can it go out in the universe and fetch some B? No, because that would be a side-effect and would have to appear in the type signature!

    In fact, the only thing it can do is return the value of type B that was passed into it, the second element of the pair. So, this mysteryMethod is really the second method, and its only sensible implementation is:

    def second[A, B](somePair: (A, B)): B = somePair._2

    Note that in reality, since Scala is neither pure nor total, there are in fact a couple of other things the method could do: throw an exception (i.e. return abnormally), go into an infinite loop (i.e. not return at all), use reflection to figure out the actual type of B and reflectively invoke the constructor to fabricate a new value, etc.

    However, assuming purity (the return value may only depend on the arguments), totality (the method must return a value normally) and parametricity (it really doesn't know anything about A and B), then there is in fact an awful lot you can tell about a method by only looking at its type.

    Here's another example:

    def mysteryMethod(someBoolean: Boolean): Boolean = ???

    What could this do? It could always return false and ignore its argument. But then it would be overly constrained: if it always ignores its argument, then it doesn't care that it is a Boolean and its type would rather be

    def alwaysFalse[A](something: A): Boolean = false // same for true, obviously

    It could always just return its argument, but again, then it wouldn't actually care about booleans, and its type would rather be

    def identity[A](something: A): A = something

    So, really, the only thing it can do is return a different boolean than the one that was passed in, and since there are only two booleans, we know that our mysteryMethod is, in fact, not:

    def not(someBoolean: Boolean): Boolean = if (someBoolean) false else true

    So, here, we have an example, where the types don't give us the implementation, but at least, they give as a (small) set of 4 possible implementations, only one of which makes sense.

    (By the way: it turns out that there is only one possible implementation of a method which takes an A and returns an A, and it is the identity method shown above.)

    So, to recap:

    • purity means that you can only use the building blocks that were handed to you (the arguments)
    • a strong, strict, static type system means that you can only use those building blocks in such a way that their types line up
    • totality means that you can't do stupid things (like infinite loops or throwing exceptions)
    • parametricity means that you cannot make any assumptions at all about your type variables

    Think about your arguments as parts of a machine and your types as connectors on those machine parts. There will only be a limited number of ways that you can connect those machine parts together in a way that you only plug together compatible connectors and you don't have any leftover parts. Often enough, there will be only one way, or if there are multiple ways, then often one will be obviously the right one.

    What this means is that, once you have designed the types of your objects and methods, you won't even have to think about how to implement those methods, because the types will already dictate the only possible way to implement them! Considering how many questions on StackOverflow are basically "how do I implement this?", can you imagine how freeing it must be not having to think about that at all, because the types already dictate the one (or one of a few) possible implementation?

    Now, look at the signature of the method in your question and try playing around with different ways to combine a and f in such a way that the types line up and you use both a and f and you will indeed see that there is only one way to do that. (As Chris and Paul have shown.)