Photo by Kevin Ku on Unsplash

Functional Polymorphism using Clojure’s Multimethods

Who says you have to be OOP in order to have Polymorphism? In this post I am going to explore how Clojure provides us with a much richer Polymorphic capabilities then your standard OOP languages with Multimethods.

The Basics

A Clojure multimethod consists of a dispatching method (defined with the defmulti Macro), and one or more methods (defined with the defmethod Macro).

Let’s see the following example:

(defmulti make-sound (fn [x] (:type x)))
(defmethod make-sound "Dog" [x] "Woof Woof")
(defmethod make-sound "Cat" [x] "Miauuu")
(make-sound {:type "Dog"}) => "Woof Woof"
(make-sound {:type "Cat"}) => "Miauuu"

1. We defined a multimethod called make-sound that gets a Map, and we defined it’s dispatching function to return the Map’s value for key :type (the value returned is called the dispatching value).
2. We defined 2 methods — one that returns “Woof Woof” if the dispatching value is “Dog”, and one that returns “Miauuu” if it’s “Cat”.

As you see, there’s almost no limit to the behavior we can define in the dispatching function. We can define a specific behavior per data type just like we do in OOP, but we can also define a specific behavior for a specific attribute, a combination of attributes, a combination of different arguments’ values — just write the suitable dispatching function.

You can think of the dispatching function as Clojure’s equivalent to the part in an OOP language that determines what method in the class hierarchy of an object should be executed when executing a method on that (done in runtime, not compile time) — only here you can control that logic, and that’s a very powerful tool.

Abstracting away Sorting

Let’s see it in action using sorting algorithms. For arrays small enough we’d want to use Quick Sort (because the constant part of the runtime is relatively small), but for larger arrays we’d want to use Merge Sort. Also, for an array of only integers we’d always rather use Counting Sort.

In an OOP language this behavior can’t be implemented in a Polymorphic way — it would have to be a code with an if statement. In Clojure however, we can achieve this quite easily.

For simplicity reasons, we define the array size threshold for when Merge Sort is better than Quick Sort as 5. First we define the multimethod:

(def QUICK-SORT-THRESHOLD 5)
(defmulti my-sort (fn [arr]
                    (if (every? integer? arr)
                       :counting-sort
                       (if (< (count arr) QUICK-SORT-THRESHOLD)
                          :quick-sort
                          :merge-sort))))here

Fairly simple — if every element in the array is an integer then the function dispatches the value :counting-sort. Otherwise, if the array size is less then 5 then it dispatches :quick-sort, otherwise it dispatches :merge-sort.

The next step is to define the methods:

(defmethod my-sort :counting-sort [arr] "Counting for the win!")
(defmethod my-sort :quick-sort [arr] "Quick Sort it is")
(defmethod my-sort :merge-sort [arr] "Good ol' Merge Sort")
(my-sort [1 2 3]) => "Counting for the win!"
(my-sort [1 2 3 "a"]) => "Quick Sort it is"
(my-sort [1 2 3 4 "a"]) => "Good ol' Merge Sort"

And that’s it! We’ve implemented runtime polymorphism in choosing the right sorting algorithm based on the input array’s characteristics — cool, right?

There is one more tweak we can do here. The keen-eyed must have noticed that default sorting algorithm here is Merge Sort. If only there was a way to define a default implementation…. 😉:

The Ins and Outs of(defmulti my-sort (fn [arr] 
                    (if (every? integer? arr)
                      :counting-sort
                      (when (< (count arr) QUICK-SORT-THRESHOLD)
                        :quick-sort))))
(defmethod my-sort :counting-sort [arr] "Counting for the win!")
(defmethod my-sort :quick-sort [arr] "Quick Sort it is")
(defmethod my-sort :default [arr] "Good ol' Merge Sort")

We got rid of the :merge-sort dispatch value, and instead defined a default implementation for my-sort using the :default keyword.

Our own + Operator on Steroids

Of course, sometimes all we need is just simple Polymorphism, type based and all. Well, for these use cases we can (and should, according to the Rule of Least Power) use Protocols — a subject that I won’t cover in this post.

Instead, I am going to define a function called ++ that accepts two arguments, and works in the following manner:

1. If the 2 arguments are numbers, then perform mathematical addition.
2. If both of the arguments are Collections, union them.
3. If the first argument is a Collection, then add to it the second argument.
4. If the second argument is a Collection, then add to it the first argument.
5. Perform string concatenation on the 2 arguments.

Let’s begin. First, we define the multimethod:

(defmulti ++ (fn [x y] [(class x) (class y)]))

What we’re interested in is the data types of the 2 arguments, so we return a vector with those 2 data types. Next, we define the method for (1):

(defmethod ++ [Number Number] [x y] (+ x y)) ; 1

The Clojure data types we wish to treat as collections are Vectors, Lists and Sets. One way to define behavior for the 3 of them is using the derive function:

(derive clojure.lang.PersistentVector ::collection)
(derive clojure.lang.PersistentList ::collection)
(derive clojure.lang.PersistentHashSet ::collection)

We use the derive function establish a parent — child relationship — here we say that ::collection (a symbol we just defined, not a data type of it’s own) is the parent of these 3 data types.

Now it’s fairly straight-forwards to implement (2) — (4) :

(defmethod ++ [::collection ::collection] [x y] (concat x y))
(defmethod ++ [::collection java.lang.Object] [x y] (conj x y))
(defmethod ++ [java.lang.Object ::collection] [x y] (++ y x))

Pay attention that I’ve used (3)’s implementation to implement (4), no need to duplicate code. That leaves us with the default implementation of (5):

(defmethod ++ :default [x y] (str x y))

Now, let’s see that it actually works of course:

(++ 2 3) => 5
(++ [1 2] ‘(3 4)) => Execution error (IllegalArgumentException) multiple methods in multimethod '++' match dispatch value: ... and neither is preferred

Oops! What happened here? Well, apparently if there are several methods that match the dispatching value, then Clojure throws an error — because it doesn’t know which of the methods to run.

Here, since the objects that derive from ::collection are also standard Objects, Clojure has no preference over the 3 implementations. We can fix that by using the prefer-method function:

(prefer-method ++ 
  [::collection ::collection] [::collection java.lang.Object])
(prefer-method ++ 
  [::collection ::collection] [java.lang.Object ::collection])
(prefer-method ++ 
  [::collection java.lang.Object] [java.lang.Object ::collection])

And let’s try this again:

(++ 2 3) => 5
(++ [1 2] ‘(3 4)) => (1 2 3 4)
(++ [1 2] “3”) => [1 2 “3”]
(++ 1 [“2” “3”]) => [“2” “3” 1]
(++ 3.5 “ is a float”) => “3.5 is a float”

See how easy it was? We were able to define different behaviors based on the different data types of the method’s arguments without any hassle. Now if someone would want to add a (6) implementation, he would just have to add his own method instead of changing existing code.

Conclusion

In this post I introduced Clojure’s Multimethods feature, and the cool stuff we can do with it. Multimethods is actually a general programming concept that exists in multiple languages, and you can read more about it in here.

I intentionally avoided providing classic examples of Polymorphism in this post because those can be achieved using Clojure’s Protocols feature. You can learn more about Multimethods from the Clojure doc and mainly from the wonderful book “Clojure for the Brave and True” — the book is fully available online, and the relevant chapter on Multimethods can be found here.

All of the code shown in this post is available here. Hope you enjoyed the post, and see you in the next one.