Are polymorphic functions "restrictive" in Scala?

Question

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?

Lytta

This is just a logical consequence; nothing to do with Scala per se. – Kalisz

Answer 1

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.)

Heal

It's worth pointing that this constraint-by-type is one of the reason the rather fabulous Hoogle tool for Haskell works as well as it does. For instance, to use one of the examples from this answer: haskell.org/hoogle/?hoogle=Bool+-%3E+Bool – Reexamine

Nice explanation, but I'm not sure it's quite apparent how big the assumptions of purity, totality, and parametricity are! If you don't have all three, types tell you far less than you think. For instance, mysteryMethod((A,B)) could very well be a select-or-default operation pattern matching on A and mysteryMethod(Boolean) could very well be a logging or map-put operation. These things are really useful, but so is knowing what a method does from types alone, and you can't really have both at the same time. – Rigadoon

Answer 2

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

Here, partial1 takes as parameters value of type A, and a function that takes a parameter of type A and a parameter of type B, returning a value of type C.

partial1 must return a function taking a value of type B and returning a C. Given A, B, and C are arbitary, we cannot apply any functions to their values. So the only possibility is to apply the function f to the value a passed to partial, and the value of type B that is a parameter to the function we return.

So you end up with the single possibility that's in the definition f(a,b)

Reexamine

Answer 3

To take a simpler example, consider the type Option[A] => Boolean. There's only a couple ways to implement this:

def foo1(x: Option[A]): Boolean = x match { case Some(_) => true
                                            case None    => false }
def foo2(x: Option[A]): Boolean = !foo1(x)
def foo3(x: Option[A]): Boolean = true
def foo4(x: Option[A]): Boolean = false

The first two choices are pretty much the same, and the last two are trivial, so essentially there's only one useful thing this function could do, which is tell you whether the Option is Some or None.

The space of possible implementation is "restricted" by the abstractness of the function type. Since A is unconstrained, the option's value could be anything, so the function can't depend on that value in any way because you know nothing about what it. The only "understanding" the function may have about its parameter is the structure of Option[_].

Now, back to your example. You have no idea what C is, so there's no way you can construct one yourself. Therefore the function you create is going to have to call f to get a C. And in order to call f, you need to provide an arguments of types A and B. Again, since there's no way to create an A or a B yourself, the only thing you can do is use the arguments that are given to you. So there's no other possible function you could write.

Tenaille