在 OCaml 列表的所有位置插入元素

Question

尝试在列表的所有位置插入一个数字，结果是列表的列表。

类似于：

insert 4 [1; 2; 3] = [[4; 1; 2; 3]; [1; 4; 2; 3]; [1; 2; 4; 3]; [1; 2; 3; 4]]

我的想法是在列表上应用 Map，其功能是 returns 一个列表。导致列表列表。像 [f 1; f 2 ; f3]（我知道只有 3 个列表，但只想先让它工作）

let insert (x : 'a) (ls : 'a list): 'a list list =
  let aux p =
    List.fold_left 
      (fun f2 acc q -> 
         if p = q then List.append acc x::[q] 
         else List.append acc q::[]) 
      [] ls
  in 
  List.map aux ls

希望是，函数 aux 将 return 一个包含 x 的列表插入到正确的位置。

问题是，List.map f1 ls 行假设 ls 是 'a list list，即使它被定义为 'a list

有什么想法吗？

Answer 1

这应该可以解决问题：

let rec insert v l =
  match l with
  | []    -> [[v]]
  | x::xs -> (v::l) :: (List.map (List.cons x) (insert v xs))

补充说明，这个也想了想：

对于空列表，只有一种方法可以插入 v，结果是 [[v]]。

对于列表x::xs首先在xs中的所有位置插入v：insert v xs，这给出了列表的列表。然后为每个列表添加 x 回到前面：List.map (List.cons x) ...。这给出了在 x 之后插入 v 的所有结果。所以最后构建 x 之前添加 v 的列表：v::l。将其添加到列表列表的前面给出最终结果。

Answer 2

试着分解这个问题。

第一个障碍：你能在列表中的给定索引处插入一个元素吗？开始可能看起来像：

let rec insert lst pos v =
  (* ... *)

嗯，我们知道如果位置是0，它应该在最前面。

let rec insert lst pos v =
  match pos with
  | 0 -> v :: lst
  | _ -> (* ... *)

如果不是 0 那么您需要将 lst 中的第一个元素附加到插入列表尾部 pos - 1.[=22 的结果中=]

当然，细节决定成败。如果你尝试 insert [1; 2; 3; 4] 7 5 会发生什么？你需要找到一种方法来检查这种情况。

如果你能让这个函数起作用，那么你只需要从 0 迭代到列表的长度，将新值插入到列表中。

List.init 会很好用。

List.(
  let lst = [1; 2; 3; 4] in
  let len = length lst + 1 in
  init len (fun i -> insert lst i 5)
)

因此，如果你 insert 写对了，你应该得到：

[[5; 1; 2; 3; 4]; [1; 5; 2; 3; 4]; [1; 2; 5; 3; 4]; 
 [1; 2; 3; 5; 4]; [1; 2; 3; 4; 5]]

Answer 3

实际回答你的问题，而不是为你提供不同的方法来实现你的目标（你想知道你的代码到底出了什么问题，而不是如何解决问题。):

fold_left 的签名是 ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>。而不是 ('a -> 'b -> 'a) 你提供 fun f2 acc q -> ... = ('a -> 'b -> 'c -> 'a)。只需删除 f2 即可。
将 x::[q] 等内容括起来，或使用 @@.

您的代码：

let insert (x : 'a) (ls : 'a list): 'a list list =
  let aux p =
    List.fold_left 
      (fun f2 acc q -> 
         if p = q then List.append acc x::[q] 
         else List.append acc q::[]) 
    [] ls
  in 
 List.map aux ls

工作代码：

let insert (x : 'a) (ls : 'a list): 'a list list =
  let aux p =
    List.fold_left 
      (fun acc q -> 
         if p = q then List.append acc (x::[q]) 
         else List.append acc (q::[])) 
    [] ls
  in 
 List.map aux ls

输入insert 4 [1;2;3]这个returnsint list list = [[4; 1; 2; 3]; [1; 4; 2; 3]; [1; 2; 4; 3]]。这几乎就是你想要的。其余的可以由您解决:)。

注：

编译器抛出的错误是：Error: This expression has type 'a list but an expression was expected of type 'b list -> 'b list list。下一次，想想发生了什么事。您向 fold_left 提供 ('a -> 'b -> 'c -> 'a)；这不是“错误”，但不是你想要的。你可以写成('a -> ('b -> 'c) -> 'a)。这意味着 acc-value 是一些 'a，fold 的值是一个函数 'b -> 'c。这解释了 error-message :).

在 OCaml 列表的所有位置插入元素

insert element in all positions of a list in OCaml

ocaml