OCaml在列表中插入一个元素

Question

将元素插入OCaml列表中特定位置的标准方法是什么？只允许递归.不允许任何分配操作.

我的目标是通过使用in_degree = out_degree = 1删除顶点来压缩ocaml中的图形.出于这个原因,我需要删除相邻的边缘以形成单个边缘.现在边缘在列表中[(6,7);(1,2);(2,3);(5,4)].所以我需要从列表中删除这些边并添加一个边.所以上面的列表现在看起来像[(6,7);(1,3);(5,4)].在这里我们看到(1,2);(2,3)被移除并且(1,3)被插入第二位置.我为此设计了一种算法.但要做到这一点,我需要知道如何从位置2,3移除边(1,2);(2,3)并在位置2中插入(1,3)而没有任何显式变量并且以递归方式.

Answer 1

OCaml列表是不可变的,因此没有像在列表操作中删除和插入元素那样的事情.

您可以做的是通过重用旧列表的某些部分来创建新列表.例如,要创建一个列表(1, 3)::xs',(1, 2)::(2, 3)::xs'您实际上可以重用xs'并使用cons构造函数创建新列表.

模式匹配非常方便使用:

let rec transform xs =                                             
  match xs with
  | [] | [_] -> xs
  | (x, y1)::(y2, z)::xs' when y1 = y2 -> (x, z)::transform xs'
  | (x, y1)::(y2, z)::xs' -> (x, y1)::transform ((y2, z)::xs')