Does Haskell have return type overloading?

 

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

    • 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.

    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 b s in the String means a deeper-nested tuple.

    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.

    链接地址: http://www.djcxy.com/p/43126.html

    上一篇: Int和Num类型的haskell

    下一篇: Haskell是否有返回类型重载？