¿Haskell tiene sobrecarga de tipos de retorno?

polymorphism

Question

Según lo que he leído sobre Haskell y la experimentación con GHC, parece que Haskell tiene una sobrecarga de tipo de retorno (también conocido como polimorfismo ad hoc). Un ejemplo de esto es la función fromInteger que puede proporcionarle un Double o un Integer dependiendo de dónde se use el resultado. Por ejemplo:

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

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

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

Una suave introducción a Haskell parece estar de acuerdo con esto cuando dice:

El tipo de polimorfismo del que hemos hablado hasta ahora se llama comúnmente polimorfismo paramétrico. Existe otro tipo llamado polimorfismo ad hoc, mejor conocido como sobrecarga. Aquí hay algunos ejemplos de polimorfismo ad hoc:

• Los literales 1, 2, etc. se utilizan a menudo para representar enteros fijos y de precisión arbitraria.

Si se considera que los literales numéricos son un ejemplo de polimorfismo ad hoc (también conocido como sobrecarga), parece que lo mismo es cierto para el resultado de funciones como fromInteger .

Y de hecho, he encontrado algunas respuestas a otras preguntas en Stack Overflow que sugieren que Haskell tiene una sobrecarga por tipo de devolución.

Sin embargo, al menos un programador de Haskell me ha dicho que esto no es una sobrecarga de tipo de retorno y, en cambio, es un ejemplo de "polimorfismo paramétrico, donde el parámetro está vinculado por un cuantificador universal".

Creo que lo que está fromInteger de hacer es que fromInteger está devolviendo un valor desde cada instancia de Num (una especie de tipo no determinista).

Esa parece ser una interpretación razonable, pero por lo que puedo decir, Haskell nunca nos permite ver más de uno de estos valores de instancia (gracias en parte a la restricción del monomorfismo ). También parece que la instancia real a quien valoramos puede determinarse estáticamente. Debido a todo esto, parece razonable decir que en la expresión fd (fromInteger 5) la subexpresión fromInteger 5 es de tipo Double , mientras que en la expresión fi (fromInteger 5) la subexpresión fromInteger 5 es de tipo Integer .

Entonces, ¿Haskell tiene sobrecarga de tipos de retorno?

Si no es así, proporcione un ejemplo de uno de los siguientes:

• código de Haskell válido que tendría un comportamiento diferente si Haskell tuviera una sobrecarga de tipo de retorno
• código de Haskell válido que no sería válido si Haskell tuviera una sobrecarga de tipo de retorno
• Código de Haskell no válido que sería válido si Haskell tuviera una sobrecarga de tipo de retorno

Answer 1

Bueno, una forma de verlo es que Haskell traduce el polimorfismo de tipo de retorno que estás pensando en polimorfismo paramétrico, usando algo llamado la traducción de paso de diccionario para las clases de tipo. (Aunque esta no es la única forma de implementar clases de tipos o razones sobre ellas, es la más popular).

Básicamente, fromInteger tiene este tipo en Haskell:

fromInteger :: Num a => Integer -> a

Eso podría traducirse internamente en algo como esto:

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

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

Entonces, para cada tipo concreto T con una instancia de Num , hay un valor NumDictionary# T que contiene una función fromInteger :: Integer -> T , y todo el código que usa la clase de tipo Num se traduce en un código que toma un diccionario como argumento.

Answer 2

El artículo seminal sobre las clases de tipos de estilo Haskell se llama "Cómo hacer que el polimorfismo ad hoc sea menos ad hoc" . Por lo tanto, la respuesta a su pregunta es un "sí" calificado, dependiendo de cómo ad hoc requiera que la sobrecarga de tipo de devolución sea ...

En otras palabras: no hay duda de que el polimorfismo ad hoc es relevante para las clases de tipos, ya que fue un ejemplo motivador para inventarlos. Pero si cree que el resultado todavía califica como "sobrecarga de tipo de retorno" depende de los detalles complicados de su definición favorita.

Answer 3

Me gustaría abordar una pequeña parte de su pregunta:

También parece que la instancia real a quien valoramos puede determinarse estáticamente.

Esto no es realmente exacto. Considere el siguiente tipo de datos extravagantes:

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

Miremos a ese tipo por un segundo antes de pasar a los bits buenos. Aquí hay algunos valores típicos del tipo 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))))))

De hecho, puede visualizar cualquier valor de este tipo como una secuencia inicial de n etiquetas de Branch seguidas de una etiqueta de Leaf "finalmente hemos terminado, gracias a Dios" seguida de una 2 ^ n-tupla del tipo contenido. Guay.

Ahora, vamos a escribir una función para analizar una representación un poco más conveniente para estos. Aquí hay un par de invocaciones de ejemplo:

*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))))))

En el camino, será conveniente escribir una función un poco más polimórfica. Aquí está:

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

Ahora nuestra función real es exactamente la misma cosa con una firma de tipo diferente:

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

Pero espera un segundo ... ¿Qué acaba de pasar aquí? Me deslicé algo por ti a lo grande! ¿Por qué no escribimos esto directamente?

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

La razón es que en la llamada recursiva, fromStringNoGood tiene un tipo diferente . No se le solicita que devuelva un PerfectlyBalancedTree Integer , se le solicita que devuelva un PerfectlyBalancedTree (Integer, Integer) . Podríamos escribirnos tal función ...

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)

... pero de esta manera se encuentra un retroceso infinito en la escritura de tipos más profundamente anidados.

El problema es que, a pesar de que estamos interesados ​​en una función monomórfica de nivel superior, ¡no podemos determinar estáticamente a qué tipo de read se está accediendo en la función polimórfica que utiliza! Los datos que pasamos determinan qué tipo de read de tupla debería devolver: más b s en la String significa una tupla más anidada.

Answer 4

Tiene sobrecarga de tipo retorno. Para un buen ejemplo ver la función de lectura. Tiene el tipo Leer a => Cadena -> a. Puede leer y devolver cualquier cosa que implemente la clase de tipo de lectura.

Answer 5

Tienes razón: Haskell tiene una sobrecarga y la proporciona a través de su mecanismo de tipo de clase.

Considere las siguientes firmas:

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

La primera firma le dice que dada una lista de elementos de cualquier tipo a , f producirá un valor de tipo a . Esto significa que la implementación de f no puede hacer suposiciones sobre el tipo a y qué operaciones admite. Este es un ejemplo de polimorfismo paramétrico . Un momento de reflexión revela que en realidad hay muy pocas opciones para implementar f : lo único que puede hacer es seleccionar un elemento de la lista provista. Conceptualmente, hay una implementación genérica única de f que funciona para todos los tipos a .

La segunda firma le dice que dada una lista de elementos de algún tipo a que pertenece a la clase de tipo Num , g producirá un valor de ese tipo a . Esto significa que la implementación de g puede consumir, producir y manipular valores de tipo a usando todas las operaciones que vienen con la clase de tipo Num . Por ejemplo, g puede agregar o multiplicar los elementos de la lista, seleccionar el mínimo de la lista, devolver una constante elevada, ... Este es un ejemplo de sobrecarga , que normalmente se considera una forma de polimorfismo ad hoc ( la otra forma principal es la coerción). Conceptualmente, hay una implementación diferente para g para todos los tipos a en Num .