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

Question

我必须编写一个函数,如果给定列表按升序排序,则返回true.空元素和单元素列表已排序.此外,[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] @ xry::xras
• 你只是结合了两个逻辑结果,if..then看起来有点不合适.

我想出了以下修订版:

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

我怀疑它比原版更有效,但它在眼睛上更容易.