How to sort a list of tuples using both key and value in OCaml?

Question

I have a list of tuples like (1, "a"), (2, "b"), (3, "c") and I want to sort them like

1 a 2 b 3 b

Where the numerical order takes precedence first and then the alphabetical order. Like if I have

(1, "bob"), (1, "cat")

It would look like

1 bob 1 cat

Here's what I'm trying

let mylist =  List.sort (fun (c1, s1) (c2, s2) -> Pervasives.compare c2 c1 ) -> Pervasives.compare s1 s2) mysortedlist

But this obviously is syntactically incorrect.

Here's the way it is if it only sorted based on numerical order

let mylist =  List.sort (fun (c1, _) (c2, _) -> compare c2 c1) mylist

Also these let statements are part of a much larger block of let and in statements, I'm just focusing on this specific piece.

EDIT: Also I would like to do this in reverse order for the alphabetical order.

For example, (1, "bob"), (1, "cat") (0, "zebra") should look like

0 zebra 1 bob 1 cat

Answer 1

This is pretty straightforward. The function you pass to List.sort just needs to compare the values if the keys are the same.

List.sort 
  (fun (k1, v1) (k2, v2) -> 
    if k1 = k2 then compare v1 v2 
    else compare k1 k2) 
  [(1, "B"); (2, "C"); (2, "A")]

And the result is:

[(1, "B"); (2, "A"); (2, "C")]

Alternatively, since it saves us from doing both an equality check on k1 and k2 and possibly running compare on them:

List.sort 
  (fun (k1, v1) (k2, v2) ->
    match compare k1 k2 with
    | 0 -> compare v1 v2
    | c -> c)
  [(1, "B"); (2, "C"); (2, "A")]

And at the end, we can realize that Stdlib.compare already works this way for tuples and simply write:

List.sort compare [(1, "B"); (2, "C"); (2, "A")]