ocaml - 使用 List.fold_right 将数字插入排序列表

Question

我正在尝试使用 Ocaml 的 List.fold_right 将数字 x 插入到排序列表 l 中，并返回包含插入元素的列表。如果元素要位于列表的前面或列表的中间，我已经找到了一种插入它的方法，但是我无法弄清楚如何对元素大于列表中的每个元素的情况进行编码因此必须放在最后。

这是我到目前为止所拥有的:

let insert_number (x: int) (l: int list): int list =
  List.fold_right l ~f:(
    fun cur -> fun acc -> 
      if x < cur then cur::x::accum 
      else cur::accum
  ) ~init: []

将其与测试用例一起使用，例如:

insert_number (3) ([1; 2; 4]);;
- : int list = [1; 2; 3; 4]

给出了正确答案。但是，对于这样的测试用例:

insert_number (3) ([1; 2]);;
- : int list = [1; 2]

该号码未插入，因为它应该添加到列表末尾。

有人可以帮助我理解如何将这种情况集成到与 List.fold_right 使用的函数中吗？

Answer 1

折叠的工作原理是在迭代列表(或其他可折叠数据结构)中的每个元素时传递一组状态。传入的函数接受当前元素和该状态。

我认为你真的很接近，但是你需要像 Jeffrey 建议的那样使用一个 bool 标志来指示该值是否已被插入。这将防止多次插入，如果折叠完成后标志仍然为 false，我们可以检测到这一点并添加要插入的值。

此匹配还可以让我们有机会丢弃不再需要的 bool 标志。

let insert v lst =
  match List.fold_right 
    (fun x (inserted, acc) -> 
       if v > x && not inserted then (true, x::v::acc) 
       else (inserted, x::acc))
    lst
    (false, []) with
  | (true, lst) -> lst
  | (_,    lst) -> v::lst