7. Data.Ord

EDIT. FIXME. Page is too long.

Note: import Data.List and import Data.Ord to access these functions.

The Ord typeclass contains things that can be compared.

An Ordering is one of three possible results:

• LT (less than) if x<y
• EQ (equal) if x==y
• GT (greater than) if x>y

Some kinds of things that can be compared are: integers, Strings, and tuples.

The compare x y function takes in two Ord things gives an Ordering. Examples:

compare 50 70 == LT
compare "Later" "Earlier" == GT

Tuple comparison is like comparing words in a dictionary. It begins at the first entry and only compares the second entry if the first entries are the same.

compare (4,10) (5,8) == LT
compare (5,10) (5,8) == GT

The normal use of Ord is in sorting.

Sorting

The Data.List module has several sorting functions.

Simple sort

• sort. Ordinary sorting, from least to greatest.

    sort [30,50,40,10] == [10,30,40,50]
    sort ["Butter","Tastes","Awesome"] == ["Awesome","Butter","Tastes"]
  

Medium: sortOn

• sortOn takes in a function of one argument, like abs that outputs something that can be ordered.

    sortOn  abs [-10,30,-60,5] == [5,-10,30,-60]
  

• The Down type creates a new thing that sorts the opposite of the original’s natural direction. Down is in the Data.Ord module.

    sortOn Down [1,5,3,6,10] == [10,6,5,3,1]
  

Danger: the list does not remember the way the items were sorted the first time, so:

step1 = sortOn abs nums
step2 = sortOn Down step1

does not sort in reverse order of absolute value! Instead, it sorts by absolute value and then re-sorts into descending numeric order.

Complex: sortBy

The sortBy function is the foundation on which all of the other sort functions are built. It is the most powerful, but also the “lowest level” and therefore it is usually the least convienient choice.

We are studying it because it provides the foundation on which all of the others build.

The sortBy function takes in a function of two arguments with a signature a -> a -> Ordering and then uses that to order the list. This function has a purpose like an old fashioned two-pan balance. It gives a way to compare the “weights” of two different objects (the two inputs) and see which one is “heaver” (GT or LT).

Here is an example of a silly function that always ranks “Young HS” above others. Notice how it selects GT or LT to make sure that the “Young HS” string ends up greater than the other one, regardless of whether that string is in the first or second argument.

cheatCompareWY "Young HS" "Young HS" = EQ
cheatCompareWY "Young HS" _          = GT
cheatCompareWY _          "Young HS" = LT
cheatCompareWY x          y          = compare x y

wySort strs = sortBy cheatCompareWY strs

Inserting a Down gives a way to reverse the order of the sorting. That could go in a helper function, like this:

cheatHelp x y = Down $ cheatCompareWY x y
wySort' strs = sortBy cheatHelp strs

The Down could also go in a lambda expression, like this:

wySort'' strs = sortBy (\x y -> Down $ cheatCompareWY x y) strs

Example of sortBy

Suppose you want to sort a list of points by distance from the origin. (This would be easier to do with sortOn.) You will break ties by using the ordinary tuple order.

    dist (x,y) = x*x+y*y
    cmp pt0 pt1
      | dist pt0 < dist pt1    = LT
      | dist pt0 > dist pt1    = GT
      | otherwise              = compare pt0 pt1

    demox = [(4,1),(-1,4),(1,4),(2,3),(-3,2)]
    demoans = sortBy cmp demox
    -- [(-3,2),(2,3),(-1,4),(1,4),(4,1)]

Creating the sortBy function (“comparing”)

The comparing function creates a comparison after applying a function. The abstract definition of comparing could be:

comparing f x y = compare (f x) (f y)

The comparing function immediately creates a function that produces an ordering.

abscompare = comparing abs
abscompare (-70) 50 == GT -- because |-70| > |50|

Usually this is used to create something suitable to use in sortBy. For example:

sortBy (comparing abs) [-70,50,-60,80]

You can actually just define sortOn using sortBy and comparing:

sortOn f xs = sortBy (comparing f) xs

Exercises A: Extended Example

A store has its inventory encoded in a list of tuples.

--           (item name,     quantity, cost)
inventory = [("Light Saber",       4, 1000),
             ("Caltrop",         300,   15),
             ("Pencil",         5000,    1),
             ("E-bike",            1, 1200),
             ("Board Marker",    400,    3)
            ]

We will define helper functions to get the item_name, item_quantity, and item_cost.

item_name (n,_,_)       = n
item_quantity (_,q,_)   = q
item_cost (_,_,c)       = c
inventory_value (_,q,c) = q*c

Many of these exercises can be done more than one way. To make sure you learn a variety of methods, some mention a required method.

1. (e1) Sort the list so the items are in increasing order of quantity. (Use sortBy.)
2. (e2) Sort the list so the items are in decreasing order of cost. (Use sortOn.)
3. (e3) Sort the list so that the smallest inventory value (=quantity*value) comes first.
4. (e4) Create a sorting function that will compare inventory value and break ties by using the name of the items (so sort items with the same inventory value alphabetically). Store the sorted list in e4.

Exercises B

Use these variables in the exercises below.

ex1 :: [Int]
ex1 = [10,-20,30,50,-40,80,-70,-60]

ex2 :: [(String,Int)]
ex2 = [("Anton",300),("Dimitry",130),("Benny",120),("Christian",150)]

ex3 :: [(String,Int)]
ex3 = [("Bar",3),("Bar",90),("Cube",50),("Cube",40)]

1. Make the variable q1 be the list ex1 sorted in increasing order.
2. Make the variable q2 be the list ex1 sorted in decreasing order.
3. Create q3 by sorting the list ex1 in decreasing order of absolute value (so 80 is the first number in the result) by using negatives.
4. (q4) Repeat the previous exercise, but use Down instead.
5. Write a sorting function that works on (String,Int). Suppose you are comparing t1 to w2. If the String part of t1 comes before “C”, then compare the Int parts of t1 and w2. Otherwise compare the String parts.