CODEWITHSUNDEEP
linked-listocamldoubly-linked-list
Matthew Zoltak
Matthew Zoltak

Reputation: 91

Trying to add an element to front of doubly-linked list ocaml

I am trying to add an element to the front of a doubly-linked list, however, I am getting the right form for the output, but the value of the cycle node says : {content = < cycle >} when it should just say < cycle >.

add_head: (float * 'a) -> ('a lcell) ref -> unit

(* The type of linked lists. *)
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, prev, next) -> 
      let first = ref (Cons (x, ref Nil, ref !(!head))) in
      prev := !first;
      head := first

This is what the output should look like:

  {contents =
    Cons ((3.3, "c"), {contents = Nil},
     {contents =
       Cons ((1.2, "b"), <cycle>,
        {contents = Cons ((2.2, "a"),<cycle>, {contents = Nil})})})}}

This is my output:

  {contents =
    Cons ((3.3, "c"), {contents = Nil},
     {contents =
       Cons ((1.2, "b"), {contents =<cycle>},
        {contents = Cons ((2.2, "a"), {contents =<cycle>}, {contents = Nil})})})}}

Any help with why this is happening, and what I am not understanding ?

Upvotes: 0

Views: 352

Answers (2)

octachron
octachron

Reputation: 18892

When you write

      let first = ref (Cons (x, ref Nil, ref !(!head))) in

you are creating a fresh reference for first, which cannot thus appears later in the list. Then, when you update prev with

      prev := !first;

you are making prev point to the content of the new reference. Consequently, prev points to a cycle but it is not part of a cycle.

In you want to avoid this indirection, you need to reuse the already existing prev reference rather than create a new fresh one:

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

Then you should get:

# let r= ref (ref Nil);;
# add_head (0., 0) r;;
# add_head (1., 1) r;;
# add_head (2., 2) r;;
# !r;;
{contents =
  Cons ((2., 2), {contents = Nil},
   {contents =
     Cons ((1., 1), <cycle>,
      {contents = Cons ((0., 0), <cycle>, {contents = Nil})})})}

Upvotes: 1

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66803

Here is my take on the problem.

In your function, head is a reference to a cell. The function should be updating the cell, not the reference to the cell. So when you assign to the head you want to do this:

!head := <new value>

Not this:

head := ref (<new value>)

I wrote some code that follows this pattern, and it gets the answer that you say is correct.

(This is exactly the same as getting the number of * dereferences right in C. Which is one reason why functional code is so much more pleasant :-)

Upvotes: 0

Related Questions