Does Haskell have return type overloading?

19
votes

Based on what I've read about Haskell, and the experimentation I've done with GHC, it seems like Haskell has return type overloading (aka ad hoc polymorphism). One example of this is the fromInteger function which can give you a Double or an Integer depending on where the result is used. For example:

fd :: Double -> String
fd x = "Double"

fi :: Integer -> String
fi x = "Integer"

fd (fromInteger 5)  -- returns "Double"
fi (fromInteger 5)  -- returns "Integer"

A Gentle Introduction to Haskell seems to agree with this when it says:

The kind of polymorphism that we have talked about so far is commonly called parametric polymorphism. There is another kind called ad hoc polymorphism, better known as overloading. Here are some examples of ad hoc polymorphism:

  • The literals 1, 2, etc. are often used to represent both fixed and arbitrary precision integers.

If the numeric literals are considered to be an example of ad hoc polymorphism (aka overloading), then it seems that the same is true for the result of functions like fromInteger.

And in fact, I've found some answers to other questions on Stack Overflow that suggest that Haskell has overloading by return type.

However, at least one Haskell programmer has told me that this isn't return type overloading, and is instead an example of "parametric polymorphism, where the parameter is bound by a universal quantifier".

I think what he's getting at is that fromInteger is returning a value from every instance of Num (sort of a nondeterministic type).

That seems like a reasonable interpretation, but as far as I can tell, Haskell never lets us look at more than one of these instance values (thanks in part to the Monomorphism restriction). It also seems like the actual instance who's value we look at can be determined statically. Because of all of this, it seems reasonable to say that in the expression fd (fromInteger 5) the subexpression fromInteger 5 is of type Double, while in the expression fi (fromInteger 5) the subexpression fromInteger 5 is of type Integer.

So, does Haskell have return type overloading?

If not, please provide an example of one of the following:

  • valid Haskell code that would have different behavior if Haskell had return type overloading
  • valid Haskell code that would be invalid if Haskell had return type overloading
  • invalid Haskell code that would be valid if Haskell had return type overloading
5
haskellpolymorphism
Can you say carefully what you consider the difference between parametric polymorphism and return-type overloading to be? – Daniel Wagner
@DanielWagner I appreciate your desire for more clarity, but if it were only about what I consider to be the difference then I wouldn't need to ask this question. I'd just do an experiment based on my personal definition. These aren't terms I made up, however. "Return-type overloading" is a form of ad hoc polymorphism, rather than a form of parametric polymorphism. – Laurence Gonsalves
That said, here's one thing that suggests that this is not (just) parametric polymorphism: From Wikipedia, parametric polymorphism makes it possible to "handle values identically without depending on their type", so if Num a => a is parametric polymorphism then I'd expect Num a => would mean "the type of a is some instance of Num, you can't rely on which". It would only let you perform operations that applied to all instances of Num, but Haskell lets you perform operations on a Num a => a that only apply to specific instance of Num. You can depend on their type. – Laurence Gonsalves
Another thing: ML has parametric polymorphism, but very limited ad hoc polymorphism. It's been years since I did anything with ML so please correct me if I'm wrong, but I believe that it is not possible in ML to have a function like fromInteger where the result can be given to both a function that accepts only Integer and also to one that accepts only Double (modulo whatever the types in ML are called). This suggests that either Haskell has a more powerful form of parametric polymorphism, or that the difference is not coming from parametric polymorphism. – Laurence Gonsalves
Aha! I'm very glad you clarified. In that case, the answer is an unqualified, "Yes, Haskell has ad-hoc polymorphism, including in its return types."! As detailed below, that actually doesn't give you anything you couldn't get with parametric polymorphism and a little pain (in fact, the very first thing GHC does is compile the ad-hoc polymorphism into parametric polymorphism), but gosh dang is it convenient. (By the way, this is not the only implementation strategy; for example, at least one implementation actually keeps type information at runtime to do class dispatch.) – Daniel Wagner

5 Answers

17
votes

Well, one way to look at it is that Haskell translates the return type polymorphism that you're thinking of into parametric polymorphism, using something called the dictionary-passing translation for type classes. (Though this is not the only way to implement type classes or reason about them; it's just the most popular.)

Basically, fromInteger has this type in Haskell:

fromInteger :: Num a => Integer -> a

That might be translated internally into something like this:

fromInteger# :: NumDictionary# a -> Integer -> a
fromInteger# NumDictionary# { fromInteger = method } x = method x

data NumDictionary# a = NumDictionary# { ...
                                       , fromInteger :: Integer -> a
                                       , ... }

So for each concrete type T with a Num instance, there's a NumDictionary# T value that contains a function fromInteger :: Integer -> T, and all code that uses the Num type class is translated into code that takes a dictionary as the argument.

13
votes

The seminal paper on Haskell-style typeclasses is called "How to make ad-hoc polymorphism less ad hoc". So, the answer to your question is a qualified "yes" -- depending on just how ad hoc you require your return-type overloading to be...

In other words: there is no question that ad hoc polymorphism is relevant to typeclasses, since that was a motivating example for inventing them. But whether you think the result still qualifies as "return-type overloading" depends on the fiddly details of your favored definition.

12
votes

I'd like to address one small part of your question:

It also seems like the actual instance who's value we look at can be determined statically.

This isn't really accurate. Consider the following wacky data type:

data PerfectlyBalancedTree a
    = Leaf a
    | Branch (PerfectlyBalancedTree (a,a))
    deriving (Eq, Ord, Show, Read)

Let's gawk at that type for a second first before we move on to the good bits. Here are a few typical values of the type PerfectlyBalancedTree Integer:

Leaf 0
Branch (Leaf (0, 0))
Branch (Branch (Leaf ((0,0),(0,0))))
Branch (Branch (Branch (Leaf (((0,0),(0,0)),((0,0),(0,0))))))

In fact, you can visualize any value of this type as being an initial sequence of n Branch tags followed by a "we're finally done, thank goodness" Leaf tag followed by a 2^n-tuple of the contained type. Cool.

Now, we're going to write a function to parse a slightly more convenient representation for these. Here's a couple example invocations:

*Main> :t fromString
fromString :: String -> PerfectlyBalancedTree Integer
*Main> fromString "0"
Leaf 0
*Main> fromString "b(42,69)"
Branch (Leaf (42,69))
*Main> fromString "bbb(((0,0),(0,0)),((0,0),(0,0)))"
Branch (Branch (Branch (Leaf (((0,0),(0,0)),((0,0),(0,0))))))

Along the way, it will be convenient to write a slightly more polymorphic function. Here it is:

fromString' :: Read a => String -> PerfectlyBalancedTree a
fromString' ('b':rest) = Branch (fromString' rest)
fromString' leaf = Leaf (read leaf)

Now our real function is just the same thing with a different type signature:

fromString :: String -> PerfectlyBalancedTree Integer
fromString = fromString'

But wait a second... what just happened here? I slipped something by you big time! Why didn't we just write this directly?

fromStringNoGood :: String -> PerfectlyBalancedTree Integer
fromStringNoGood ('b':rest) = Branch (fromStringNoGood rest)
fromStringNoGood leaf = Leaf (read leaf)

The reason is that in the recursive call, fromStringNoGood has a different type. It's not being called on to return a PerfectlyBalancedTree Integer, it's being called on to return a PerfectlyBalancedTree (Integer, Integer). We could write ourselves such a function...

fromStringStillNoGood :: String -> PerfectlyBalancedTree Integer
fromStringStillNoGood ('b':rest) = Branch (helper rest)
fromStringStillNoGood leaf = Leaf (read leaf)

helper :: String -> PerfectlyBalancedTree (Integer, Integer)
helper ('b':rest) = Branch ({- ... what goes here, now? -})
helper leaf = Leaf (read leaf)

... but this way lies an infinite regress into writing deeperly and deeperly nested types.

The problem is that, even though we're interested in a monomorphic top-level function, we nevertheless cannot determine statically what type read is being called at in the polymorphic function it uses! The data we're passed determines what type of tuple read should return: more bs in the String means a deeper-nested tuple.

5
votes

You're right: Haskell does have overloading and it provides it through its type-class mechanism.

Consider the following signatures:

f :: [a] -> a
g :: Num a => [a] -> a

The first signature tells you that given a list of elements of any type a, f will produce a value of type a. This means that the implementation of f cannot make any assumptions about the type a and what operations it admits. This is an example of parametric polymorphism. A moment's reflection reveals that there are actually very little options for implementing f: the only thing you can do is select an element from the provided list. Conceptually, there is a single generic implementation of f that works for all types a.

The second signatures tells you that given a list of elements of some type a that belongs to the type class Num, g will produce a value of that type a. This means that the implementation of g can consume, produce, and manipulate values of type a using all operations that come with the type class Num. For example, g can add or multiply the elements of the list, select the minimum of the list, return a lifted constant, ... This is an example of overloading, which is typically taken to be a form of ad-hoc polymorphism (the other main form being coercion). Conceptually, there is a different implementation for g for all types a in Num.

1
votes

It has return type overloading. For a good example see the Read function. It has the type Read a => String -> a. It can read and return anything that implements the read type class.