sorting - OCaml - 如何对对进行排序？

Question

我们有对:

 (3,10000) (1,2),(2,11) (2,0) (2, 10) (1,1000000)

我们想订购:

 (1,2) (1,1000000), (2,0) (2, 10) (2,11) (3,10000)

如何在 OCaml 中做到这一点？

Answer 1

List.sort函数可以对任何 'a 列表 进行排序，它采用 'a -> 'a -> int 类型的比较函数，如果第一个参数是，则该函数必须返回负数严格小于第二个，如果严格大于则为正，如果相等则为零。

let lexicographic_compare (x,y) (x',y') =
  let compare_fst = compare x x' in
  if compare_fst <> 0 then compare_fst
  else compare y y'

# List.sort lexicographic_compare [ (3,10000); (1,2); (2,11); (2,0); (2, 10); (1,1000000)];;
- : (int * int) list =
[(1, 2); (1, 1000000); (2, 0); (2, 10); (2, 11); (3, 10000)]

(此代码使用内置的 compare 函数对整数执行正确的操作。)

请注意，在实践中，compare 函数已经按字典顺序比较对，因此 List.sort Compare ... (无需编写任何新代码)似乎可以工作。但它如何在成对上工作并没有指定，所以它将来可能会改变，依赖于此是不好的风格。如果您想要精确的比较顺序，您应该编写特定于域的比较。

(当然，有些库已经提供了这个 lexicography_compare 逻辑；但重点是要学习如何自己做到这一点。)