保持排序功能

Question

我正在尝试解决一个名为“keepsorted”的函数的问题；

这个函数必须从一个名为 l1 的列表中保留一个不断增长的数字的子列表。

例如，如果我有

let l1 = [1; 2; 0; 1; 2; 4; 3; 5; 3; 2; 6]

，返回的是一个包含数字

[1; 2; 2; 4; 5; 6]

的列表

我尝试了很多解决方案，但我不明白。

我最后的解决方案是：

let rec keepsorted l = 
  match l with
  | [] -> [] 
  | a1::a2::r when a1 >= a2 -> a1::keepsorted r 
  | a::r -> a::keepsorted r;;

结果是：

- : int list = [1; 2; 1; 2; 4; 5; 2; 6]

Answer 1

此行有两个问题：

a1::a2::r when a1 >= a2 -> a1::keepsorted r

第一个问题是您要从递归调用中删除

a1

，因此与

a1

相比，下一个数字将始终被接受而不开始。

例如，考虑列表

10 :: 9 :: 8 :: r

：

keepsorted (10::9::8::r)
10 :: keepsorted (8::r)
10 :: 8 :: ...

10 从未与 8 进行比较。

您可以通过以下方式轻松解决该问题：

a1::a2::r when a1 >= a2 -> keepsorted (a1::r)

现在

a1

可以与

r

的下一个元素进行比较

第二个问题是，当

a2

时，您要丢弃

a1 >= a2

，但您的示例表明您只想在

a2

时丢弃

a1 > a2

。如果相等，则保留两者。

最终功能：

let rec keepsorted l = 
  match l with
  |[] -> [] 
  |a1::a2::r when a1 > a2 -> keepsorted (a1::r) 
  |a::r -> a::keepsorted r;;

Answer 2

作为 Stef 正确答案的替代方案，您需要跟踪迭代时添加到输出的最后一个值以及当前元素。如果我们以正确的顺序构建列表，这不是很有效，但如果我们使用左折叠以相反的顺序构建它，那就是是。最后我们只需要颠倒该列表即可。

let keepsorted lst =
  let f i x = 
    match i with
    | [] -> x::i 
    | y::_ when x >= y -> x::i 
    | _ -> i
  in
  lst
  |> List.fold_left f [] 
  |> List.rev

如果我们考虑这如何适用于您的测试用例：

keepsorted [1; 2; 0; 1; 2; 4; 3; 5; 3; 2; 6]
List.fold_left f [] [1; 2; 0; 1; 2; 4; 3; 5; 3; 2; 6]
List.fold_left f [1] [2; 0; 1; 2; 4; 3; 5; 3; 2; 6]
List.fold_left f [2; 1] [0; 1; 2; 4; 3; 5; 3; 2; 6]
List.fold_left f [2; 1] [1; 2; 4; 3; 5; 3; 2; 6]
List.fold_left f [2; 1] [2; 4; 3; 5; 3; 2; 6]
List.fold_left f [2; 2; 1] [4; 3; 5; 3; 2; 6]
List.fold_left f [4; 2; 2; 1] [3; 5; 3; 2; 6]
List.fold_left f [4; 2; 2; 1] [5; 3; 2; 6]
List.fold_left f [5; 4; 2; 2; 1] [3; 2; 6]
List.fold_left f [5; 4; 2; 2; 1] [2; 6]
List.fold_left f [5; 4; 2; 2; 1] [6]
List.fold_left f [6; 5; 4; 2; 2; 1] []
List.rev [6; 5; 4; 2; 2; 1]
[1; 2; 2; 4; 5; 6]

附带好处：这自然是尾递归，尽管这对于琐碎的数据集来说并不重要。