sorting - 将元素插入升序列表 [ocaml]

Question

以下代码将一个元素插入到按升序排序的列表中。

let rec insert x l =
  match l with
    | [] -> [x]
    | y::ys -> if x < y then x::y::ys else y::insert x ys

但是，我如何仅使用 List.fold_right 实现上述功能，并且没有递归？

Answer 1

看看最简单的实现List.fold_right：

let rec fold_right f li init = match li with
  | [] -> init
  | y::ys -> f y (fold_right f ys init)

你可以尝试类似的东西

let insert x li =
  let add_x y inserted_ys =
    if x < y then x::y::inserted_ys
    else y::inserted_ys
  in
  List.fold_right add_x li [x]

问题是then分支不正确：您将进入x两个地方，一个是列表的开头，另一个是inserted_ys. 但是，您知道列表中x的哪个位置：就inserted_ys在开头，因为 的所有元素ys都大于x。所以你可以删除xwith List.tl。

let insert x li =
  let add_x y inserted_ys =
    if x < y then x::y::(List.tl inserted_ys)
    else y::inserted_ys
  in
  List.fold_right add_x li [x]

请注意，这是一种复杂的编写方式insert。更好的技术是add_x返回一对列表和一个布尔值，布尔值告诉您是否x已经添加或尚未添加。

Answer 2

我想解决方案的方案是这样的：

fun insert x l =
    List.fold_right (fun a b -> if <test> then a :: x :: b else a :: b) l []

每次调用该函数时，它都会看到最终列表的末尾，以及通常会排在列表前面的新元素。x似乎可以根据此信息决定是否在当前位置插入您的值。

该方案的简单实现会将 x 多次插入结果中。但在我看来，如果你做得<test>足够具体，它会起作用。

当 x 位于列表的开头时，此方案也不起作用。您将不得不单独处理该案件。

正如加什所说，这不是建立升序列表的有效方法。（FWIW gasche 是一位比我知识渊博的 OCaml 专家 :-)