Haskell: Polymorphic functions explanation

Question

So i am given this

intCMP :: Int -> Int -> Ordering
intCMP a b | a == b = EQ
     | a < b = LT
     | otherwise = GT

intCMPRev :: Int -> Int -> Ordering
intCMPRev a b | a == b = EQ
     | a < b = GT
        | otherwise = LT

floatCMP :: Float -> Float -> Ordering
floatCMP a b | a == b = EQ
       | a < b = LT
       | otherwise = GT

I need to write this function

sort3 :: Ord a => (a -> a-> Ordering) -> [a] -> [a]
sort3 cmp xs =

Which will sort 3 or less elements by comparison. No recursion. I was wondering how this works as far as passing say intCMP. Why would you pass that into the sort function? Does it serve a purpose when sorting and returning the sorted list? I'm not really sure how to do the comparisons manually like that without any sort of recursive call, so I'm just trying to understand it better.

I was thinking of doing 3 comparisons and then moving the element to a certain position in the list, but i really don't know how i could even do this in haskell. Any clues on how to start this would be great. Maybe some sort of pattern?

Thanks.

Answer 1

You're not writing polymorphic functions (which is by definition a function that takes more than one type). Write one first:

cmp :: Ord a => a -> a -> Ordering
cmp x y =
  | x == y = EQ
  | x < y  = LT
  | otherwise = GT

You would write the above that way the functionality that compares the elements in the sort, need not be a part of the sort. To sort a list is by nature recursive: at least if length is undefined. To achieve this simply write a sort that can make use of your custom comparison, here is quick sort though you could write a different type of sort.

sort3 :: (Ord a) => [a] -> [a]  
sort3 [] = []  
sort3 (x:xs) =   
    let smallerSorted = filter (<=)
        biggerSorted = filter(>)
    in  smallerSorted ++ [x] ++ biggerSorted  

Answer 2

Here's a hint:

• If you have an empty list, clearly the result of sorting it will be an empty list.
• Likewise, a list with just a single element is also already sorted.
• If you have a 2-element list, there are only 2 possible orderings, hence only 2 possible return values from your function.
• If you have a 3-element list, there are 6 possible orderings (the first element can be 1 of 3 input elements, the next element can be 1 of the 2 remaining, leaving only 1 choice for the last element). You can easily write down the 6 different conditions, causing you to return 1 of the 6 possible lists of the 3 elements.

Answer 3

Partial answer to the first part of your question:

Passing in intCMP to sort3 lets you control the way the sorting is done. Presumably, sort3 intCMP [7,3,6] will return [3,6,7], whereas sort3 intCMPRev [7,3,6] will return [7,6,3]. You could even make your own weird sorting functions like first all the even numbers and then all the odd ones in descending order, like so:

intCMPWeird :: Int -> Int -> Ordering
intCMPWeird a b
    | even a && even b = intCMP a b -- even numbers compare as usual
    | odd a  && odd b  = intCMPRev a b  -- odd numbers compare in reverse order
    | even a && odd b  = LT -- evens are all 'smaller' than odds
    | odd a  && even b = GT -- odds are all 'greater' than evens

Using this, sort3 intCMPWeird [7,3,6] should give [6,7,3].

What happens during typechecking when you pass one of the intCMP... functions into sort3 is (in a very small nutshell) that the compiler tries to match the type of sort3's first argument (a -> a -> Ordering) with the type of the supplied value (Int -> Int -> Ordering) and succeeds in doing that, by making a equal to Int. Then it needs to check whether the constraint Ord a is satisfied for Int, which works! Finally the compiler can figure out that the type of sort3 intCMP is [Int] -> [Int]. Similarly, sort3 floatCMP has type [Float] -> [Float].

I'm not 100% sure why the Ord constraint is on the type of sort3, since you can get the needed information from the passed-in comparison function - are you sure you've typed that correctly?

EDIT: Hint on how to use a where clause to get a readable definition, you still have to fill in some bits and add some more clauses:

sort3 cmp [x,y,z] 
    | x <= y && somethingElse1 = listWithXyzInSomeOrder1
    | x <= z && somethingElse2 = listWithXyzInSomeOrder2
        where a <= b = cmp a b /= GT