Polymorphwhat?

This post is a part of the F# Advent Calendar 2017. Be sure to check out other submissions!

Imagine that you are at the interview and you are asked this question:

Could you describe how polymorphism works?

Think a little bit what would be your answer.

…or just watch this Python sketch.

What I’d probably say is something like “uhh, but what kind of polymorphism?”

There are terms in programming which are quite confusing since they can have different meanings depending on the context. Polymorphism happens to be one of them. If you ask different programmers “what is polymorphism?”, you might get different answers and all of them may well be correct. In this post, I want to classify various types of polymorphism one can encounter in F#.

Note — this post assumes that you are familiar with some OO language like C# or Java :)

Without further ado…

Subtype polymorphism

This should be very familiar to anyone who ever coded in an object-oriented language, like C++, Java, C# etc. Subtype polymorphism refers to the classic type hierarchy involving inheritance and is-a relationship between objects. The syntax used in F# to denote such relations requires some getting used to:

Alternatively, you can declare an interface

A special case of subtype polymorphism is, in fact, a discriminated union. Decompiling a simple DU:

into equivalent C# code reveals that this data structure is implemented as a base class with three deriving classes, each one representing a single case of the union.

Ad-hoc polymorphism

It is just a fancy name for a concept that should also be familiar. It refers to overloaded functions — functions that have the same name, but different types and/or the number of arguments. In F#, regular functions cannot be overloaded:

but class members (both normal methods and static ones) can:

There isn’t much more to it 😃

Parametric polymorphism

You probably know this concept under the name of generics. Generics allow for specifying types and functions which are further parametrized by some other types. Collections module from the standard library is full of good examples of parametric polymorphism — e.g. a list is a type that can hold ints, floats, Reindeers, what have you. Here is an example of a simple generic data structure — a tree, defined as a discriminated union:

The generic type 'a is determined at compile time based on usage

We can also define functions that are themselves generic (meaning that they operate on generic types). For example, we can create a function that traverses our tree and prints all the elements:

Row polymorphism

This one is more interesting because it is not so widely available in popular OO languages.

Consider this situation — you want to declare a function that operates on types that have something in common — for example, expose certain property. How would you approach this task?

One way is to declare an interface with said property and call it a day.

You can then write a function that operates on types implementing this interface. For instance, you can check whether a gift will fit into a Christmas stocking:

This solution has two drawbacks. Firstly, it is not possible to attach the interface to a type that you don’t own (e.g. a type from some external library). You can only attach methods and properties using type extensions. This problem can be worked around by writing a slim adapter layer, but it can get cumbersome.

The second problem of interface approach is related to the fact that the information about the type passed into the function gets erased. When the object the function operates on is returned from the function body, we no longer have information about the object type — all we know is that it implements a certain interface. It can be seen in the example above. List.choose returns a collection of IHasVolume , even though we know they are actually of type XmasGift .

Row polymorphism is a mechanism that deals with both these shortcomings at once. In F# you can use a feature called Statically Resolved Type Parameters (SRTP) which allows you to define functions that operate on types having certain properties. The compiler analyzes the structure of the types and decides whether they comply with defined constraints. If they don’t, you will get a compilation error. Here is how you can rewrite the fitsInTheSock function to accept all types having a property named Volume returning float :

So, what is going on here?

• We inform the compiler that the function accepts a parameter of type ^a, which has to expose certain property (Volume in our case). This is a so-called constraint.
• We use that property in the body of the function
• And then we return the object of type ^a wrapped in an Option.

This allows us to do some further processing on the value returned from fitsInTheSock without doing any casting:

So, isn’t that great? It is, but there are also some drawbacks of this technique. Firstly, SRTP doesn’t work on extension methods (yet), which limits their usefulness. The syntax and compiler errors around them are also quite hard to digest. I haven’t used them in my production F# code yet, but it’s good to know what this feature does.

By the way, remember when I told that in F# you can’t overload functions? Well, I lied (a little). You can simply inline them and they may be automatically turned into SRTP functions by the compiler. This emulates function overloading pretty well:

This feature is also pretty similar to duck typing. The difference between SRTP and duck typing is that the former inspects the structure of the types at compile time, while the latter only cares about the shape of the passed object at runtime. Which brings us to…

Static and dynamic polymorphism

They are somewhat different compared to types of polymorphism described above. All previously mentioned polymorphisms were certain language features. Static and dynamic polymorphisms describe when the magic happens — respectively, during compile time or during runtime.

In case of subtype polymorphism, the compiler cannot determine at compile time what will be the type of the object which virtual method is being called (that is the whole point, after all). So this is an example of dynamic polymorphism. Duck typing could also be considered a form of dynamic polymorphism.

All other examples I described above land into the static polymorphism category. Function overloads and generics are checked during compilation, and SRTP even has static in its’ name (Statically Resolved Type Parameters).

So, why are they all called the same?

After learning about all these different types of polymorphism, one can wonder why are they all grouped under the same name? I believe that the common element in all those methods is that they all enable performing some operations on values that have different types. Sometimes the types need to be closely related (like in subtype polymorphism) and sometimes they can be totally unrelated to each other (like in duck typing or SRTP), but the core idea is to have a single interface that would allow the callee code to operate on different types.

That’s all I have to say about polymorphism. If you noticed any errors or know some other types of polymorphism I didn’t mention, please let me know :)

Merry Christmas and Happy FSharping!