如何在OCAML中编写一个函数，它返回一个列表，其中第二个列表插入到第一个列表中

Question

如何编写一个函数，它接受两个列表和一个整数（例如：int n）作为输入，然后返回一个列表，其中第二个列表插入第一个列表，到第n个位置（这就是为什么该函数还将INT作为输入）。

这就是我已经完成的工作，但我似乎对“变量”list1“有一个问题，”prev“类型，我不确定它是否甚至被称为”prev“。功能代码应该工作，但编译器给我这个错误：

第12行，字符18-22：错误：此记录模式应具有类型列表字段prev不属于类型列表

编译器为“prev”可变变量提供的错误基本上只是语法错误。

type list = {
    value : int;
    mutable next : list1
    mutable prev : list1
    }

  and list1 = 
  Empty
  | Node of list ;;

let rec insert sez x = match sez with Empty -> Node {value=x; prev=Empty; 
  next=Empty}
  | Node {value=r; prev=lb; next=rb} -> 
    if x < r then Node {value=r; prev=(insert lb x); next=rb} 
    else Node {value=r; prev=lb; next=(insert rb x)};;

Answer 1

假设我们有两个列表 - L1和L2 - 并且位置k将后者插入到前者中，简单的算法可能如下所示：

1. 创建一个由L1的前k个元素组成的列表（让我们将它命名为prefix）
2. 创建一个由其余L1元素组成的列表（让我们将其命名为postfix）
3. Concat prefix，L2和postfix

前缀和后缀列表可以被描述为“先取k个元素”和“先放下k个元素然后休息” - 听起来很熟悉，对吧？所以我们可以从这些辅助功能开始：

let rec take k lst =
  match k with
    | 0 -> []
    | k -> (match lst with
      | [] -> failwith "too short"
      | h::t -> h :: (take (k - 1) t))

let rec drop k lst =
  match k with
    | 0 -> lst
    | k -> (match lst with
      | [] -> failwith "too short"
      | h::t -> drop (k-1) t)

现在解决方案变得非常简单：

let insert l1 l2 n =
  match n with
    | 0 -> l2 @ l1
    | n ->
      if n = List.length l1 then l1 @ l2
      else (take n l1) @ l2 @ (drop n l1)

（由于连接不是很有效，但很简单）

UPD。实际上，insert本身可能就像

let insert l1 l2 n =
  (take n l1) @ l2 @ (drop n l1)