ocaml - 如何使用 fold_left 在 OCaml 中找到列表的第二小数？

Question

到目前为止，我有一个小代码片段可以搜索列表中的最小值

let sec_small lst=
let min_helper min curr =
    if (min < curr) then min else curr
in List.fold_left min_helper (List.hd lst) lst

这是一段返回列表最小值的代码。我只是想知道，我应该如何进行才能找到列表中第二小的元素？

Answer 1

与其记住一个数字，不如记住其中的两个？

（顺便说一下，当你做这样的事情时，代码会变得非常复杂。这可能是练习的重点。如果你想要第三小的数字，你几乎宁愿只是对列表进行排序并完成它。）

Answer 2

如果你有一些循环前代码来建立一个很好的不变量，那么这会更容易。在这种情况下，很明显您想要的是到目前为止看到的最小和第二小的元素的有序对。匹配让事情变得简单：

let second_smallest list =
  match list with
   | [] | [_] -> failwith "no second element to return"
   | a::b::rest ->
       snd (List.fold_left
              (fun ((sm, ssm) as same) elt ->
                if elt < ssm then
                  if elt < sm then elt, sm else sm, elt
                else same)
              (if a < b then a, b else b, a)
              rest)

Answer 3

为什么不对您第一次获得的最小项目执行 List.drop，然后再次调用您的 sec_small 函数？因此，代替使用 lst 调用 sec_small 函数一次，我将有一个以 sec_small 作为其内部函数的外部函数，然后将其称为

(sec_small (List.drop (lst, sec_small lst)))