What are the reasons that protocols and multimethods in Clojure are less powerful for polymorphism than typeclasses in Haskell?

Question

More broadly this question is about various approaches to the expression problem. The idea is that your program is a combination of a datatype and operations over it. We want to be able to add new cases without recompiling the old classes.

Now Haskell has some really awesome solutions to the expression problem with the TypeClass. In particular - we can do:

class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool


member :: (Eq a) => a -> [a] -> Bool
member y [] = False
member y (x:xs) = (x == y) || member y xs

Now in Clojure there are multimethods - so you can do:

(defmulti area :Shape)
(defn rect [wd ht] {:Shape :Rect :wd wd :ht ht})
(defn circle [radius] {:Shape :Circle :radius radius})
(defmethod area :Rect [r]
    (* (:wd r) (:ht r)))
(defmethod area :Circle [c]
    (* (. Math PI) (* (:radius c) (:radius c))))
(defmethod area :default [x] :oops)
(def r (rect 4 13))
(def c (circle 12))
(area r)
-> 52
(area c)
-> 452.3893421169302
(area {})
-> :oops

Also in Clojure you have protocols - with which you can do:

(defprotocol P
  (foo [x])
  (bar-me [x] [x y]))

(deftype Foo [a b c]
  P
  (foo [x] a)
  (bar-me [x] b)
  (bar-me [x y] (+ c y)))

(bar-me (Foo. 1 2 3) 42)
=> 45

(foo
 (let [x 42]
   (reify P
     (foo [this] 17)
     (bar-me [this] x)
     (bar-me [this y] x))))

=> 17

Now this individual makes the claim:

But, there are protocols and multi-methods. These are very powerful, but not as powerful as Haskell's typeclasses. You can introduce something like a typeclass by specifying your contract in a protocol. This only dispatches on the first argument, whereas Haskell can dispatch on the entire signature, including return value. Multi-methods are more powerful than protocols, but not as powerful as Haskell's dispatch.

My question is: What are the reasons that protocols and multimethods in Clojure are less powerful for polymorphism than typeclasses in Haskell?

Polar

Answer 1

Well the obvious one is that protocols can only dispatch on the first and only the first argument. This means they're roughly equivalent to

 class Foo a where
   bar  :: a -> ...
   quux :: a -> ...
   ...

Where a must be the first argument. Haskell's type classes let a appear anywhere in the function. So protocols are easily less expressive than typeclasses.

Next is multimethods. Multimethods, if I'm not mistaken, allow dispatch based on a function of all the arguments. This looks more expressive in some ways than Haskell, since you can dispatch arguments of the same type differently. However, this can actually be done in Haskell, generally by wrapping the argument in a newtype for dispatching.

A few things that can't be done with multimethods to my knowledge:

1. Dispatch on return type
2. Store values polymorphic over all types of a type class forall a. Foo a => a

To see how 1. comes into play, consider Monoid it has a value mempty :: Monoid m => m. It's not a function, and simulating this is impossible with Clojure since we don't have any type information about what method we're expected to choose.

For 2. consider read :: Read a => String -> a. In Haskell we could actually create a list which has the type [forall a. Read a => a], we've essentially deferred the computation and we can now run and rerun elements of the list to attempt to read them as different values.

Typeclasses also have static types so there's some checking to make sure you're not going to end up "stuck" without an instance to call statically, but Clojure is dynamically typed so I'll chalk this up to a difference in style between the two languages rather than a particular advantage one way or the other. Also of course is the advantage that typeclasses have a lot less overhead than multimethods since generally the witness record can be inlined and everything is resolved statically.

Electrosurgery

Problem: "I don't want to unnecessarily restrict what sort of data my code handles." ... "I know, I'll use dynamic typing." Now you have eight problems. ;) – Thanksgiving

@Thanksgiving Incitement of religious debate over typing isn't needed. There are benefits to both no matter which side of the argument you lean towards. – Salmonella

@A.Webb OK perhaps it would be fairer to say that static typing with parametric polymorphism and type classes chooses to solve this problem at compile time while dynamic typing chooses to solve this problem at runtime. – Thanksgiving

If you want to be clever, you could dispatch on return type. You could make the call to the function take the return type as an argument, and then dispatch on that in the multi-method. I mean, in fact, it seems all the limitations of multi-methods are simply from not having the type info available, but there is nothing stoping you from requesting it in your function. Haskell just enforces the programmer to always specify the type (though inference makes it trivial). So I don't actually see that Clojure polymorphism is less powerful. – Backspin

I like that your answer included limitation 2. However it will never be a real concern for Clojure programs. In a dynamically typed language, you can still make that list. If you've chosen to program in Clojure, you have already agreed that compile time type checking is unimportant to you. If that was a limitation of a statically typed language, it would be a real limitation because you've bought into the idea that type checking at compile time is valuable – Liberty

Answer 2

The most fundamental difference is that with type classes, dispatch is on types not on values. No value is needed to perform it. That allows much more general cases. The most obvious example is dispatch on (part of) the result type of a function. Consider e.g. Haskell's Read class:

class Read a where
  readsPrec :: Int -> String -> [(a, String)]
  ...

Such dispatch is clearly impossible with multi-methods, which have to dispatch on their arguments.

See also my more extensive comparison with plain OO.

Aquarist