¿Qué es una función paramétricamente polimórfica?

Question

¿Puede alguien explicarme esto en relación con los algoritmos de clasificación?

Answer 1

Déjame intentar lo más simple que pueda.

Suponga que tiene un par de enteros:

foo :: (Int, Int) 
foo = (2,5) 

y supongamos que desea una función que intercambie la posición de los números enteros en ese par. Usted puede hacer esto:

swapInt :: (Int, Int) -> (Int, Int) 
swapInt (x,y) = (y,x) 

Pero ahora, si se necesita una función similar para Double s, habría que implementarlo Againt:

swapDouble :: (Double, Double) -> (Double, Double) 
swapDouble (x,y) = (y,x) 

Hay que señalar un par de cosas: (1) los códigos de swapDouble y swapInt son idénticos excepto por sus firmas de tipo, (2) en ninguna parte del código se hace referencia a nada que dependa de los tipos de x y y. Este código es válido cualquiera que sean sus tipos. Entonces debería haber una forma de escribir el código solo una vez y dejar que el compilador especialice el código automáticamente para cada tipo que necesite. La forma de hacerlo es el polimorfismo paramétrico. Para este caso particular, se puede escribir:

swap :: (a,b) -> (b,a) 
swap (x,y) = (y,x) 

Lo que esto significa? Le está diciendo al compilador: hay un intercambio de funciones, que toma un par (x, y) donde x es de tipo a y y es de tipo b, y devuelve el par (y, x). ayb pueden ser de cualquier tipo, por lo que esta función se denomina función polimórfica. Cuando aplique swap a un par específico, el compilador verificará el tipo de este par y creará automáticamente una versión de esta función que sea adecuada para su tupla.

Por ejemplo:

swap ('a', 1) = (1,'a') -- in this case swap :: (Char, Int) -> (Int, Char) 
swap (0 , 5) = (5, 0) -- in this case swap :: (Int , Int) -> (Int, Int) 

Vamos a entender el nombre: polimórfica es cualquier estructura o función de los datos que funciona con muchos tipos diferentes. La causa paramétrica de la forma de implementar el polimorfismo es tener "parámetros de tipo" en el tipo de función o estructura de datos. Cuando escriba (a,b), a y b son parámetros de tipo.

Se pueden implementar muchas estructuras de datos independientemente del tipo que se encuentre en ese momento: listas, matrices, mapas, tuplas, ... todas ellas pueden tener una implementación paramétricamente polimórfica. Y las funciones que operan sobre ellos: ordenar, mapear, plegar, ... se pueden implementar sin tener que referirse a tipos específicos, sino a escribir parámetros que serán especializados de manera automática por el compilador.

Existen otros tipos de polimorfismo, y Haskell también implementa ad hoc polimorfismo con clases de tipos, por ejemplo.

Answer 2

El polimorfismo paramétrico permite que una función o un tipo de datos se escriban de forma genérica, de modo que pueda manejar valores idénticos sin depender de su tipo. El polimorfismo paramétrico es una forma de hacer que un lenguaje sea más expresivo, a la vez que se mantiene la seguridad de tipo estático completo.

- desde: http://en.wikipedia.org/wiki/Polymorphism_(computer_science).

En relación con las búsquedas, supongo que eso depende más del contexto exacto. No puedo evitarlo.

Answer 3

Una función que es independiente de los tipos de argumentos con los que trabaja.

linear_search f n [] = Nothing 
linear_search f n (x:xs) 
    | f n x  = Just x 
    | otherwise = linear_search f n xs 

Mi Haskell está oxidado, por lo que si alguien puede corregir los errores en los comentarios que se agradecerán.

La idea aquí es que linear_search puede realizar una búsqueda lineal en una lista de cualquier tipo; esto es lo que hace que la función sea paramétrica (es decir, los parámetros de la función) polimórfica (porque pueden ser de muchos tipos).

# preforming on integers 
linear_search (==) 5 [1,2,3,4,5] 
# returns Just 5 

# preforming on strings 
linear_search (elem) 'e' ["doctor", "apron", "horse", "sky"] 
# returns Just "horse" 

Al hablar sobre el tipo de esta función, se afirma como (a -> b -> Bool) -> a -> [b] -> Maybe b. Es importante destacar que las letras indican variables de tipo, lo que significa que su tipo puede ser cualquier cosa, de nuevo la propiedad que hace funciones paramétricamente polimórficas.