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?

Display Name
  • 265
  • 1
  • 10
  • 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 00: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 http://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 01:14

2 Answers2

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.

amon
  • 132,749
  • 27
  • 279
  • 375
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.

Petr
  • 5,507
  • 3
  • 29
  • 46
  • 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? – Display Name Oct 11 '14 at 08:06
  • @SargeBorsch What if you have something like `print one`? – Petr Oct 11 '14 at 08:52
  • This will be invalid, of course. But I think that this is not enough to disallow this entirely. – Display Name Oct 11 '14 at 11:10