Sunday, 6 May 2012

How do I sort lexicographically in F#?

F# does this for you automatically when you define a tuple, record or union type:
> 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 ofIComparable 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#.

No comments: