Lexicographic sorting in F#

Question

I am playing with a toy problem (Convex hull identification) and needed lexicographic sorting twice already. One of the cases was given a list of type Point = { X: float; Y: float }, I would like to sort by X coordinate, and in case of equality, by Y coordinate.
I ended up writing the following:

let rec lexiCompare comparers a b =
   match comparers with
   [ ] -> 0
   | head :: tail -> 
      if not (head a b = 0) then head a b else
      lexiCompare tail a b 

let xComparer p1 p2 = 
   if p1.X > p2.X then 1 else
   if p1.X < p2.X then -1 else
   0

let yComparer p1 p2 = 
   if p1.Y > p2.Y then 1 else
   if p1.Y < p2.Y then -1 else
   0

let coordCompare =
   lexiCompare [ yComparer; xComparer ]

Which allows me to do

let lowest (points: Point list) =
   List.sortWith coordCompare points 
   |> List.head

So far, so good. However, this feels a bit heavy-handed. I have to create specific comparers returning -1, 0 or 1, and so far I can't see a straightforward way to use this in cases like List.minBy. Ideally, I would like to do something along the lines of providing a list of functions that can be compared (like [(fun p -> p.X); (fun p -> p.Y)]) and do something like lexicographic min of a list of items supporting that list of functions.

Is there a way to achieve this in F#? Or am I thinking about this incorrectly?

possibly note: http://stackoverflow.com/a/211691/19299 – Brian Apr 07 '12 at 07:30 — Brian, Apr 07 '12 at 07:30

score 3 · Answer 1 · answered Apr 07 '12 at 03:12

Well, to start with, you can rely on F#'s built-in compare function:

let xComparer p1 p2 = compare p1.X p2.X
let yComparer p1 p2 = compare p1.Y p2.Y

Alternatively, you can clearly abstract this a bit if desired:

let compareWith f a b = compare (f a) (f b)
let xComparer = compareWith (fun p -> p.X)
let yComparer = compareWith (fun p -> p.Y)

Or, as you note, you could build this approach directly into the list handling function:

let rec lexiCompareWith l a b =
    match l with
    | [] -> 0
    | f::fs ->
        match compare (f a) (f b) with
        | 0 -> lexiCompareWith fs a b
        | n -> n

One important limitation here is that since you're putting them into a list, the functions must all have identical return types. This isn't a problem in your Point example (since both functions have type Point -> float), but it would prevent you from sorting two Person objects by name and then age (since the first projection would have type Person -> string but the second would have type Person -> int).

Thank you, very helpful - the built-in compare is already useful information. The issue you raise in the end re: various return types is relevant, as for the other example I have to deal with, I have a mixed bag of float and integers. — Mathias, Apr 07 '12 at 04:31

score 3 · Accepted Answer · answered Apr 09 '12 at 12:19

Is there a way to achieve this in F#? Or am I thinking about this incorrectly?

F# does this for you automatically when you define a record type like yours:

> type Point = { X: float; Y: float };;
type Point =
  {X: float;
   Y: float;}

You can immediately start comparing values. For example, defining a 3-element list of points and sorting it into lexicographic order using the built-in List.sort:

> [ { X = 2.0; Y = 3.0 }
    { X = 2.0; Y = 2.0 }
    { X = 1.0; Y = 3.0 } ]
  |> List.sort;;
val it : Point list = [{X = 1.0;
                        Y = 3.0;}; {X = 2.0;
                                    Y = 2.0;}; {X = 2.0;
                                                Y = 3.0;}]

Note that the results were sorted first by X and then by Y.

You can compare two values of any comparable type using the built-in compare function.

If you want to use a custom ordering then you have two options. If you want to do all of your operations using your custom total order then it belongs in the type definition as an implementation of IComparable and friends. If you want to use a custom ordering for a few operations then you can use higher-order functions like List.sortBy and List.sortWith. For example, List.sortBy (fun p -> p.Y, p.X) will sort by Y and then X because F# generates the lexicographic comparison over 2-tuples for you (!).

This is one of the big advantages of F#.

Thank you! It looks like lexicographic sorting works on Tuples of more than 2 elements, so this does the job: mapping elements of the lists to a tuple in the desired lexicographic order and sorting the result works perfect. — Mathias, Apr 12 '12 at 02:36
"It looks like lexicographic sorting works on Tuples of more than 2 elements". Absolutely, `compare` works on all comparable F# types including tuples, records and unions. All of the code you need is autogenerated for you. This is tremendously useful! — J D, Apr 12 '12 at 09:58

score 2 · Answer 3 · answered Apr 07 '12 at 14:18

I don't think I understand your question correctly, but doesn't the following code work fine?

let lowest (points : Point list) = List.sort points |> List.head

It seems that F# performs implicit comparison on record data types. And my little experiment indicates that the comparison happens to be lexicographic. But I could not find any evidence to support that result.

So I'm not yet sure F# compares records lexicographically. I can still write in the following manner using tuple instead:

let lowest (points : Point list) =
    let tuple = List.map (fun pt -> (pt.X, pt.Y)) points |> List.sort |> List.head
    { X = fst tuple; Y = snd tuple }

I hope this post could help.

My problem is not specifically about the list of Points; what I am after is the ability to define what lexicographical order to use. For instance, even if the sort above sorts lexicographically by X and then Y, imagine that I want to sort by Y and then X - how would I go about that? Interesting that Record sorting works by default though! — Mathias, Apr 07 '12 at 19:50

Lexicographic sorting in F#

3 Answers3