F# 检查列表是否已排序的函数

Question

我必须编写一个函数，如果给定列表按升序排序，则该函数返回 true。空列表和 1 元素列表已排序。另外，[5,12,12] 应该返回 true。

我写了一个似乎可以工作的函数：

let rec isSorted (l: int list) = 
    match l with
    | [] -> true
    | [x] -> true
    | [x;y] -> x <= y
    | x::y::xr -> if x > y then false else isSorted([y] @ xr);

但它似乎有点不对劲......我想一定有一种更简单的方法来做到这一点？我讨厌我必须匹配 4 个案例，但我不知道如何让它变得更聪明。

还有更好的解决方案吗？

Answer 1

您可以组合现有功能：

let isAscending l = l |> Seq.pairwise |> Seq.forall (fun (a, b) -> a <= b)

printfn "%b" (isAscending []) // true
printfn "%b" (isAscending [1]) // true
printfn "%b" (isAscending [5;12]) // true
printfn "%b" (isAscending [5;12;12]) // true
printfn "%b" (isAscending [5;12;12;11]) // false

Answer 2

好吧，永远不要说

[y] @ xr

什么时候

y :: xr

会好。 （一般来说，@ 是一种代码味道。）

有点挑剔，但最后一行可以

| x::((y::_)as t) -> if x > y then false else isSorted(t)

使您免于进行任何分配。

现在，您需要第三个案例吗？如果删除它会发生什么？

Answer 3

回到原始代码（而不是建议的库调用），我想说您可以进行一些改进：

• 第三个匹配情况并不是真正需要的（已经提到过）。
• 在第二种情况下，您不想为该值指定名称，因此您不会访问它。
• 在第四种情况下，将 y::xr 拆开只是用 [y] @ xr （或 y ::xr）。 as 表达式看起来更好。
• 您只是组合了两个逻辑结果，if..then 看起来有点不合适。

我提出了以下修订版本：

let rec isSorted l =
    match l with
    | [] | [_] -> true
    | h1::(h2::_ as tail) -> h1 <= h2 && isSorted tail

我怀疑它比原始版本更有效，但它更美观。

Answer 4

就效率而言，这是一个特别糟糕的解决方案，因此我永远不会在现实世界中使用它，但这里有一个漂亮的函数式方法来查看我在博客示例中提出的问题：

let isSorted l = l = (l|>List.sort)