Ocaml 双链表:从双链表中删除满足条件的节点

Question

我们有一个双链表，定义为：

type 'a llist =
| Nil
| Cons of (float *'a) * 'a lcell * 'a lcell
and 'a lcell = ('a llist) ref

我已经实现了一个添加头功能，如下所示：

let add_head x head = 
match !(!head) with
| Nil -> head := !(singleton x)
| Cons (e, previous, next) -> 
let temp = Cons (x, ref Nil, !head) in
previous := temp;
head := previous;; 

请注意，为了实现添加头，我使用了单例函数

let singleton (init: float * 'a): 'a lcell ref =
let l = ref (Cons (init, ref Nil, ref Nil)) in
let front = ref l in
front

我的问题是当我尝试删除一个元素时，我正在尝试编写一个 remove 函数remove: (float -> bool) -> 'a lcell ref -> unit，以便remove p head删除时间戳满足谓词p: float -> bool的第一个节点。如果没有节点的时间戳满足谓词，则列表应保持不变。

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

let remove p head =
let rec remove' ll =
match !ll with 
| Nil -> head := !head
| Cons ( (d,_), previous, next) ->
if p d then
match (!previous, !next) with 
| (Nil, Nil) -> head := ref Nil   (* empty list*)
| (Nil, Cons ( d1, p1, n1)) -> (* this is the head, remove it and reassign head*)
head := next; 
p1 := Nil
| (Cons ( d2, p2, n2), Cons ( d1, p1, n1)) -> (* this is middle, remove it and fix pointers of previous and next*)
n2 := !next;
p1 := !previous 
| (Cons ( d1, p1, n1), Nil) -> (* this is tail, remove it and make previous one the tail*)
n1:= Nil 
else remove' next              
in
remove' !head

我在删除列表中间的项目时遇到问题，即不是头部或尾部。我在删除多个元素时也遇到问题。有人可以试着帮助我吗，我想我的比赛案例中缺少一些东西。

Answer 1

当你在匹配语句中做缺点时，你搞砸了 您必须替换上一个和下一个，而不是 n2 和 p1 它应该是

| Cons(d2, p2, n2), Cons (d1, p1, n1) ->
`previous := Cons(d2, p2, next);`
`next := Cons(d1, previous, n1);