F＃一个函数来检查列表是否排序

我必须编写一个函数，如果给定列表按升序排序，则返回true。空的和1元素的列表被排序。另外，[5,12,12]应该返回true。F＃一个函数来检查列表是否排序

我已经写了，似乎工作的函数：

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例，但我不知道如何让它变得更聪明。

任何更好的解决方案？

来源

2010-09-04 Peter

好，从来不说

[y] @ xr

时

y :: xr

将事情做的很好。（一般情况下，@是一个代码味道。）

还挺挑剔，但最后一行可能是

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

，并保存你做的任何分配。

现在，你需要第三种情况吗？如果你删除它会发生什么？

来源

2010-09-04 12:06:47 Brian

感谢您的支持！通过使用y :: xr，不需要第三种情况。我想这就是欺骗了我 - 它看起来很奇怪。 – Peter 2010-09-04 12:28:50

你可以结合现有的其他功能：

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

来源

2010-09-04 12:07:28 desco

啊，我不知道原来的解决方案有多少效率，但确实很高雅:-) – 2010-09-04 13:08:45

@EdgarSánchez：'Seq's是懒惰地构造/评估的，所以仍然只有一次遍历。 – Dario 2010-09-04 14:29:51

这是在效率方面特别坏的解决方案，所以在现实世界中我从来没有使用这一点，但这里是寻找一个漂亮的功能性的方式我想出了这个问题作为一个博客示例的一部分：

让isSorted L = L =（L |> List.sort）

来源

2010-09-04 14:19:02 TechNeilogy

再回到原来的代码（而不是建议的库调用），我会说你可以做一些改进：

第三场比赛的情况并不是真的需要（已经提到过）。
在第二种情况下，您不想给该值起一个名称，但您没有访问它。
在第四种情况下，拆开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

我怀疑它比原来的更有效，但它是对眼睛更容易。

来源

2010-09-10 11:21:33

不错的工作。我希望OP返回将其标记为接受的答案。我期望它比原来的效率更高，因为你已经在每次调用“isSorted（[y] @ xr）”时节省了不必要和昂贵的尾部重构，尽管如果这是固定的，按照Brian的帖子，那么可能没有太多的节约，但是，是的，它在眼睛上更容易。 – 2010-09-12 02:32:19

F＃一个函数来检查列表是否排序

回答

相关问题