为什么 max (Operator) 不是 return 最长的列表？

Question

我想找出两个列表中最长的一个。考虑以下代码示例：

let xs = ['B']
let ys = ['A'; 'B']
let longest = max xs ys
printfn "%A" longest

与我的预期相反，该程序的输出是 ['B'] 而不是 ['A'; 'B']。

为什么List<'T> implement max会这样？ How/where 这个实现到底有没有定义？

我可以看到 max 需要 comparison，我认为这意味着 IComparable 的实现。 List<'T> 通过使用 StructuralComparison 属性自动执行此操作。但是这个自动实现是什么样子的呢？

要获得两个列表中最长的列表，最简洁的替代方法是什么？

Answer 1

F# 逐个元素地比较列表。作为 'B' > 'A' 所以它考虑第一个列表>第二个（字典顺序）并打破进一步的比较。您可以在列表中使用 .Length 属性来比较长度。例如这样；

let longest = if xs.Length > ys.Length then xs else ys

结果：

val longest : char list = ['A'; 'B']

Answer 2

这是一个可重复使用的函数，用于检查任意 2 个序列的较大长度：

let longest x y = match (Seq.length x > Seq.length y) with
                  |true -> x
                  |false -> y

Answer 3

如果你想要一个通用的方法来比较两个对象属性你可以创建一个 maxBy 函数：

let maxBy f x y = Array.maxBy f [|x; y|]

那么你可以这样做：

let longest = maxBy List.length xs ys

或直接：

let longest = Array.maxBy List.length [|xs; ys|]

Answer 4

这是一个可重复使用的函数，它将 return 来自 列表的最长列表 :

let longest ll = ll |> List.sortBy List.length |> List.rev |> List.head

示例：

> longest [xs; ys];;
val it : char list = ['A'; 'B']
> let zs = ['A' .. 'D'];;
val zs : char list = ['A'; 'B'; 'C'; 'D']
> longest [xs; zs; ys];;
val it : char list = ['A'; 'B'; 'C'; 'D']

但是，如果您输入空列表，它将不起作用，因为在这种情况下，您需要准确定义您希望的行为。

Answer 5

你可以写一个maxBy函数：

let maxBy f a b = if f b > f a then b else a

然后这样称呼它：

let longestList = maxBy List.length xs ys

因为 List.length 是 O(N)，如果列表很长，性能会受到影响。该操作将是 O(N1 + N2)，其中 N1 和 N2 是列表的长度。

一长一短，性能会受到不必要的影响。为避免这种情况，您可以编写一个更具体的函数。这个函数是 O(min(N1, N2)):

let getLongest list1 list2 =
    let rec helper = function
    | [], _ -> list2
    | _, [] -> list1
    | _ :: t1, _ :: t2 -> helper (t1, t2)
    helper (list1, list2)

let longestList = getLongest xs ys

为什么 max (Operator) 不是 return 最长的列表？

Why does max (Operator) not return the longest list?

f#

max