Двойной связанный список 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;; 

Обратите внимание, что для реализации добавления головы я использовал синглтонfunction

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: (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);