Ocaml - Removing middle node from doubly-linked list

Question

I am trying to remove an element from a doubly-linked list based on wether a node in that list satisfies a function that returns a bool. For some reason the previous pointer of the replacing node (next of removed) does not update and instead refers back to itself.

My Code

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

let remove p head =
  let rec remove' ll =
    match !ll with
    |Nil -> head := !head (*no node match*)
    |Cons ((a, _), c, d) -> 
        if p a then
          match (!c, !d) with
          |(Nil, Nil) -> head := ref Nil (*singleton match*)
          |(Cons(_, c', d'), Nil) -> (*last node match*)
              d' := Nil 
          |(Nil, Cons(_, c', d')) -> (*first node match*)
              head := d;
              c':= Nil
          |(Cons(_, _, d'), Cons(_, e', _))-> (*middle match; Does not work*)
              e' := !c;
              d' := !d
        else
          remove' d
  in
  remove' !head

Test Results

Initial value of head is
{contents =
 @1:{contents =
     Cons ((-1.689, 3),
           @2:{contents = Nil},
           @3:{contents =
               Cons ((0.910, -1),
                     <@1>,
                     @4:{contents =
                         Cons ((0.647, 3),
                               <@3>,
                               @5:{contents =
                                   Cons ((4.531, -1),
                                         <@4>,
                                         @6:{contents = Nil})})})})}}

Calling remove (fun x -> close x 0.646639313413) head (*close compares values accuracy up to two decimal digits*)

The value of head is now
{contents =
 @1:{contents =
     Cons ((-1.689, 3),
           @2:{contents = Nil},
           @3:{contents =
               Cons ((0.910, -1),
                     <@1>,
                     @4:{contents =
                         Cons ((4.531, -1), <@4>, @5:{contents = Nil})})})}}

user_10582650 · Answer

So, here is what is happening:

We have memory blocks M1, M2, M3:

M1 contains the object Cons((v1, x1), l1, M2) = Cons(_, _, d');
M2 contains the object Cons((v2, x2), M1, M3) = Cons(_, c, d);
M3 contains the object Cons((v3, x3), M2, r3) = Cons(_, e', _);

And then, when we do e' := !c; d' := !d, what we are doing is:

*M2 = *M1 : make a copy of the object in M1, and store it in M2;
*M2 = *M3 : make a copy of the object in M3, and store it in M2;

So, the result we get is:

M1 contains the object Cons((v1, x1), l1, M2);
M2 contains the object Cons((v3, x3), M2, r3);
M3 contains the object Cons((v3, x3), M2, r3);

Which is the result we see in the test.

To change the linked list correctly, what we can do is to create a new object in M2 that has the values stored in M3, but with the updated left pointer (the other option would be to create new objects in M1 and in M3).

This is what I would do:

let remove p head =
  let aux node_ref =
  match !node_ref with
  | Nil -> ()
  | Cons((k, _), l, r) ->
    if p k then
      node_ref := (
        match !r with
        | Nil -> Nil
        | Cons((nk, nx), nl, nr) -> Cons((nk, nx), l, nr)
      )
    else
      aux r
  in
  aux head

Ocaml - Removing middle node from doubly-linked list

1 Answers