Попытка добавить элемент в начало двусвязного списка ocaml - PullRequest
Новая
       15

Попытка добавить элемент в начало двусвязного списка ocaml

0 голосов
/ 17 октября 2019

Я пытаюсь добавить элемент в начало двусвязного списка, однако я получаю правильную форму для вывода, но значение узла цикла говорит: {content = < cycle >} когда он должен просто сказать < 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

Вот как должен выглядеть вывод: 

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

Это мой вывод: 

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

Любая помощь спочему это происходит, и чего я не понимаю?

Ответы [ 2 ]

1 голос
/ 17 октября 2019

Когда вы пишете 

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

, вы создаете новую ссылку для первого, которая не может, следовательно, появиться позже в списке. Затем, когда вы обновляете prev с помощью 

      prev := !first;

, вы заставляете prev указывать на содержание новой ссылки. Следовательно, prev указывает на цикл, но он не является частью цикла.

Чтобы избежать этой косвенности, необходимо повторно использовать уже существующую ссылку prev, а не создавать новую свежую. : 

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;;

Тогда вы должны получить: 

# 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})})})}
0 голосов
/ 17 октября 2019

Вот мой взгляд на проблему.

В вашей функции head является ссылкой на ячейку. Функция должна обновлять ячейку, а не ссылку на ячейку. Поэтому, когда вы назначаете голову, вы хотите сделать это: 

!head := <new value>

Не это: 

head := ref (<new value>)

Я написал некоторый код, который следует этому шаблону, и он получает ответ, что выскажем правильно.

(Это то же самое, что получить число разыменований * прямо в C. Это одна из причин, почему функциональный код намного приятнее: -)

...