What is a parametrically polymorphic function?

Question

Can any one explain this to me in relation to sorting algorithms?

Answer 1

Let me try the simplest thing I can.

Suppose you have a pair of integers:

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

and suppose you want a function that swap the position of the integers on that pair. You could do this:

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

But now if you need a similar function for Doubles, you'd have to implement it againt:

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

You have to note a couple of things: (1) the codes of swapDouble and swapInt are identical except for their type signatures, (2) nowhere in the code you make reference to anything that would depend on what are the types of x and y. This code is valid whatever are their types. So there should be a way to write the code just once and let the compiler specialize the code automatically for each type you need. The way to do this is parametrical polymorphism. For this particular case, you can write:

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

What this means? You're telling the compiler: there's a function swap, that takes a pair (x,y) where x is of type a and y is of type b, and return the pair (y,x). a and b can be any type, thus this function is called a polymorphic function. When you apply swap to a specific pair, the compiler will check the type of this pair and automatically instantiate a version of this function that is adequate for your tuple.

For example:

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 )

Let's understand the name: polymorphic is any function or data structure that works with many different types. Parametric cause the way to implement the polymorphism is to have "type parameters" in the type of the function or data structure. When you write (a,b), a and b are type parameters.

Many data structures can be implemented irrespective of the type that is contained in then: lists, arrays, maps, tuples,... all of them can have a parametrically polymorphic implementation. And functions that operate on them: sort, map, fold,... can be implemented without having to refer to specific types, but to type parameters that will be specialized automatically by the compiler.

Other kinds of polymorphism exist, and Haskell also implement ad hoc polymorphism with typeclasses, for example.

Answer 2

A function which is agnostic to the argument types it works with.

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

My Haskell is rusty, so if someone could correct mistakes in the comments that would be appreciated.

The idea here is that linear_search can preform a linear search on a list of any type; this is what makes the function parametrically (meaning the function parameters) polymorphic (because they can be many types).

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

When talking about the type of this function, it is stated as (a -> b -> Bool) -> a -> [b] -> Maybe b. Importantly, letters indicate type variables, meaning their type can be anything -- again the property which makes functions parametrically polymorphic.

Answer 3

Parametric polymorphism allows a function or a data type to be written generically, so that it can handle values identically without depending on their type. Parametric polymorphism is a way to make a language more expressive, while still maintaining full static type-safety.

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

In relation to searches, I guess that depends more on the exact context - I can't help there.