2

As I did understand, and as it's described here, ad-hoc polymorphism is limited to compile-time dispatch. That is, if we have a function that expects an argument that belongs to a typeclass, we must know the concrete type of the argument at compile time to be able to use this function.

So the following (in Haskell-like pseudocode) will be invalid:

// C-style comments

typeclass Num(X) where:
    add :: X -> X -> X
    one :: X

implementation Num for Int:
    add x y = x + y
    one = 1

implementation Num for Rational:
    // analogous thing…

veryCleverFunction :: Num a -> a -> a
veryCleverFunction x = add x one

tooCleverFunction :: Int -> Num(?)
tooCleverFunction x = {
    y =
        if (x > 0)
            x
        else
            Rational(x, 2) // `y` has a value of unknown type,
                           // but we know it's under `Num` typeclass
    veryCleverFunction y // can work with any `Num`s, but here the concrete type is unknown…
}

(I hope it's clear what I want to depict in this snippet)

At least in Scala I'm almost sure there's no way to express this. Or I'm wrong? And is it possible in theory? Are there any languages which allow this?

  • This sounds like "duck typing", which is used all the time in Python. Of course, everything is runtime in Python. – o11c Oct 11 '14 at 21:28
  • You could end up calling veryCleverFunction with a non-Int in the recursive call, which wouldn't make sense either way given its type signature. Did you mean for the argument to be Num as well, instead of Int specifically? I know that polymorphic recursion like this kind of thing is possible in Haskell, at least for some cases. – David Nov 13 '14 at 0:51
  • 1
    Type class dispatch occurs at runtime in Haskell (or at least in GHC, I'm not sure if it's an official requirement in the Haskell specification). We can see this in a definition like this lpaste.net/114215. In fact, internally, GHC converts a signature like Num a => a to a function something like NumDict a -> a, where NumDict a is the type class dictionary for Num. Your example is trickier because the runtime polymorphism is in the return type, but it might still be possible with an existential type wrapper. – David Nov 13 '14 at 1:14
3

There are different mechanisms of polymorphism. Except for parametric polymorphism, these dispatch control flow depending on the type of function arguments. In other words: they are some kind of function overloading. The arguments can either be considered for their static type or for their dynamic type. If we dispatch a call on a static type, we call this ad-hoc polymorphism. If we dispatch on the dynamic type, this is either single dispatch if we only consider the dynamic type of one argument (typically an object on which a method is called), or multiple dispatch if we consider the dynamic type of all arguments.

All OOP languages must at least offer single dispatch. The Visitor Pattern can be used to fake multiple dispatch by using additional levels of indirection, but is impractical for more than two arguments. Multi-dispatch in general solves the same kind of problems that ad-hoc polymorphism does, except that it happens at runtime and can therefore be more expressive. Noteworthy examples of languages with multi-dispatch (sometimes called multi-methods) are the Common Lisp Object System (CLOS) and the Julia language.

The blog post you linked to does demonstrate ad-hoc polymorphism, but in an overly complicated fashion. The simplest example might be:

abstract class Pet
class Cat extends Pet
class Dog extends Pet

object Owner {
    def pet(cat: Cat) = "You can haz cuddles!"
    def pet(dog: Dog) = "Who's a good boy?"
}

val cat: Cat = new Cat()
val dog: Dog = new Dog()
val pet: Pet = new Cat()

Owner pet cat // works
Owner pet dog // works
Owner pet pet // fails, because implementation is chosen *statically*

It's the same story in Java and C++. The blog post then goes on a tangent on how using implicit parameters can be used to implement extension methods, and how they can be used to hide the visitor pattern. None of this is really relevant to ad-hoc polymorphism.


Your code example runs into problems because the return types of tooCleverFunction but more importantly of the conditional assigned to the variable y are not well defined. As y can either be Int or Rational, the type checker must reject your code. To safely allow this ambiguity, we could introduce a Union type. But if we have y :: Union Int Rational, then veryCleverFunction can't be applied to y (except of course if Union is a functor so we can do fmap veryCleverFunction y, which returns another Union for you to deal with). If we use such an Union, no static type information is lost. Instead, you have to deal with the mess you created throughout the remaining program.

You would like y to have the type Num a instead. But Num a is not a type, but a type class, i.e. a restriction on the type a.

  • Yes, but what if Num a will really be a type? Is it possible? – Sarge Borsch Oct 12 '14 at 9:37
  • @SargeBorsch No, it is not possible to use a type class as a proper type. They are merely a type constraint. Maybe a comparison to Java is helpful: Type classes are similar to interfaces, in that they can be implemented by other types. But while Java allows you to declare a method Interface foo(Interface bar), Haskell requires <A extends Interface> A foo(A bar). While invoking a method on bar will require dynamic dispatch in Java (as it is of the Interface type), Haskell can dispatch statically, as the type variable A is statically known. – amon Oct 12 '14 at 13:53
  • Okay, but the question is about such possibility in theory & in other/new languages. Your comment talks about Haskell, but this doesn't mean that what is impossible in Haskell is impossible at all. – Sarge Borsch Oct 12 '14 at 15:39
0

Your example already shows why it's not possible. Consider one. If you encountered one at runtime, should it evaluate to Int or Rational? There is no way how to decide.

A related reading resource is OOP vs type classes at Haskell Wiki.

  • Why? if you are talking about expression add x one, the types of add and one can be inferred from runtime type of x, aren't they? And if "generic values" were permitted, a sole value one with unknown concrete type can also exist, and a concrete type will be chosen later, when it's used. Why not? – Sarge Borsch Oct 11 '14 at 8:06
  • @SargeBorsch What if you have something like print one? – Petr Pudlák Oct 11 '14 at 8:52
  • This will be invalid, of course. But I think that this is not enough to disallow this entirely. – Sarge Borsch Oct 11 '14 at 11:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.