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?

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.

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.