4

我正在玩一个玩具问题（凸壳识别），并且已经需要字典排序两次。其中一个案例给出了一个列表type Point = { X: float; Y: float }，我想按 X 坐标排序，如果相等，则按 Y 坐标排序。
我最终写了以下内容：

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 ]

这让我可以做

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

到目前为止，一切都很好。但是，这感觉有点重。我必须创建返回 -1、0 或 1 的特定比较器，到目前为止，在 List.minBy 之类的情况下，我还看不到直接使用它的方法。理想情况下，我想做一些事情，提供一个可以比较的函数列表（比如 [(fun p -> pX); (fun p -> pY)]），并做一些类似列表的字典最小的事情支持该功能列表的项目。

有没有办法在 F# 中实现这一点？还是我想错了？

4

3 回答 3

3

有没有办法在 F# 中实现这一点？还是我想错了？

当您定义像您这样的记录类型时，F# 会自动为您执行此操作：

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

您可以立即开始比较值。例如，定义一个 3 元素的点列表并使用内置的按字典顺序对其进行排序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;}]

请注意，结果首先按 排序X，然后按 排序Y。

您可以使用内置compare函数比较任何可比较类型的两个值。

如果您想使用自定义排序，那么您有两个选择。如果您想使用自定义总订单来完成所有操作，那么它属于类型定义作为IComparable和朋友的实现。如果您想对一些操作使用自定义排序，那么您可以使用高阶函数，例如List.sortByand List.sortWith。例如，将按然后List.sortBy (fun p -> p.Y, p.X)排序，因为 F# 会为您生成 2 元组的字典比较 (!)。YX

这是 F# 的一大优势。

于 2012-04-09T12:19:09.217 回答
3

好吧，首先，您可以依赖 F# 的内置compare函数：

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

或者，如果需要，您可以清楚地抽象一下：

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

或者，正如您所注意到的，您可以将此方法直接构建到列表处理函数中：

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

这里的一个重要限制是，由于您将它们放入列表中，因此这些函数都必须具有相同的返回类型。这在您的示例中不是问题Point（因为两个函数都有 type Point -> float），但它会阻止您Person按名称和年龄对两个对象进行排序（因为第一个投影将具有 typePerson -> string但第二个将具有 type Person -> int）。

于 2012-04-07T03:12:59.210 回答
2

我认为我没有正确理解您的问题，但是以下代码不能正常工作吗？

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

似乎 F# 对记录数据类型执行隐式比较。我的小实验表明比较恰好是字典顺序的。但我找不到任何证据来支持这一结果。

所以我还不确定 F# 按字典顺序比较记录。我仍然可以使用 tuple 以以下方式编写：

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 }

我希望这篇文章能有所帮助。

于 2012-04-07T14:18:18.420 回答