Что такое параметрически полиморфная функция?

Question

Может ли кто-нибудь объяснить мне это в связи с алгоритмами сортировки?

Answer 1

Позвольте мне попробовать самое простое, что я могу.

Предположим, у вас есть пара целых чисел:

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

и предположим, что вам нужна функция, которая меняет положение целых чисел в этой паре. Вы могли бы сделать это:

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

Но теперь, если вам нужна подобная функция для Double с, вам придется ее реализовать снова:

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

Вы должны отметить пару вещей: (1) коды swapDouble и swapInt идентичны, за исключением их сигнатур типов, (2) нигде в коде вы не ссылаетесь ни на что, что будет зависеть от того, что это типы x и y. Этот код действителен независимо от их типа. Таким образом, должен быть способ написать код только один раз и позволить компилятору автоматически специализировать код для каждого типа, который вам нужен. Способ сделать это - параметрический полиморфизм. Для этого конкретного случая вы можете написать:

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

Что это значит? Вы говорите компилятору: есть функция swap, которая берет пару (x, y), где x имеет тип a, а y имеет тип b, и возвращает пару (y, x). a и b могут быть любого типа, поэтому эта функция называется полиморфной функцией. Когда вы применяете swap к определенной паре, компилятор проверит тип этой пары и автоматически создаст версию этой функции, подходящую для вашего кортежа.

Например:

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 )

Давайте разберемся в названии: полиморфная - это любая функция или структура данных, которая работает со многими различными типами. Параметрическая причина Способ реализации полиморфизма состоит в том, чтобы иметь «параметры типа» в типе функции или структуры данных. Когда вы пишете (a,b), a и b являются параметрами типа.

Многие структуры данных могут быть реализованы независимо от типа, который содержится в then: списки, массивы, карты, кортежи, ... все они могут иметь параметрически полиморфную реализацию. И функции, которые работают с ними: sort, map, fold, ... могут быть реализованы без необходимости ссылаться на конкретные типы, но на параметры типов, которые будут автоматически специализироваться компилятором.

Существуют и другие виды полиморфизма, и Haskell также реализует, например, ad hoc полиморфизм с классами типов.

Answer 2

Функция, которая не зависит от типов аргументов, с которыми она работает.

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

Мой Haskell ржавый, поэтому, если кто-то сможет исправить ошибки в комментариях, которые будут оценены.

Идея здесь в том, что linear_search может предварительно выполнить линейный поиск в списке любого типа;это то, что делает функцию параметрически (то есть параметры функции) полиморфной (потому что они могут быть разных типов).

# 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"

Говоря о типе этой функции, она указывается как (a -> b -> Bool) -> a -> [b] -> Maybe b.Важно отметить, что буквы обозначают переменные типа , что означает, что их тип может быть любым - опять же свойство, которое делает функции параметрически полиморфными.

Answer 3

Параметрический полиморфизм позволяет обобщенно записывать функцию или тип данных, чтобы он мог обрабатывать значения одинаково, независимо от их типа. Параметрический полиморфизм - это способ сделать язык более выразительным, сохраняя при этом полную статическую безопасность типов.

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

Что касается поисков, я думаю, что это зависит больше от точного контекста - я не могу там помочь.