Как получить указатель на хвост списка в OCaml? - PullRequest
Новая
       73

Как получить указатель на хвост списка в OCaml?

0 голосов
/ 27 марта 2019

С помощью lisps (например, Scheme) можно проверить, идентичны ли два хвоста списка: 

(define ls '(1 2 3))

(define tail1 (cdr ls))  ; Get the tail of the list.
(define tail2 (cdr ls))

(eqv? tail1 tail2)  ; Check if identical. Returns true.

Как может быть реализован эквивалент в OCaml с использованием ссылок?

Предположим, что Iесть это: 

let ls = ref [1; 2; 3]
let tail1 : int list ref = get_tail_ref ls
let tail2 : int list ref = get_tail_ref ls
assert (tail1 == tail2)  (* Ensure that they are identical. *)

Это правильный подход?Как можно определить get_tail_ref?

Ответы [ 4 ]

2 голосов
/ 27 марта 2019

Тип list в стандартной библиотеке OCaml является неизменным, и вы ничего не можете с ним сделать.Помещение указателя на список в изменяемой ячейке не делает сам список изменчивым.К счастью, вы можете реализовать изменяемые списки и даже следовать представлению данных lisp, например, 

type ('a,'b) cell = {mutable car : 'a; mutable cdr : 'b}

Система типов будет бороться с вами, хотя :)

Кроме того, похоже, что вы 'запутанные указатели и ссылки.В OCaml все коробочные типы (такие как списки, строки, плавающие и т. Д.) Представлены в виде указателей.Непосредственные типы, такие как int, char, и конструкторы данных, такие как None, My_constructor, представлены как целочисленные теги.(Это то же представление, которое используют все современные lisps, кстати).

Ссылка - это просто тип, определенный в стандартной библиотеке как 

type 'a ref = {mutable contents : 'a}

Так что это коробочный тип, который содержит изменяемый указатель на произвольное значение.Так, например, вы можете поместить туда список {contents = [1;2]}, и он будет содержать указатель на список неизменный .Вы можете изменить contents, чтобы он указывал на другой список, но вы не можете изменить сам список.Опять же, они неизменны, и вы не можете превратить нечто неизменное в изменчивое.

Также обратите внимание, что OCaml будет обмениваться данными, например, 

let common_tail = [3;4]
let head_one = 1 :: common_tail
let head_two = 0 :: common_tail

Они оба будут иметь один и тот же хвост, например, 

List.tl head_one == List.tl head_two

Обычно это довольноневинный, так как люди не часто используют изменяемые типы данных в OCaml, но вы можете создать список ссылок, к которым они также будут предоставлены, например, 

let common_tail = [ref 3; ref 4]
let head_one = ref 1 :: common_tail
let head_two = ref 0 :: common_tail

И если вы сейчас установите cadr до 33

List.hd (List.tl head_two) := 33;;

Это повлияет на оба списка 

# head_one;;
- : int ref list = [{contents = 1}; {contents = 33}; {contents = 4}]

# head_two;;
- : int ref list = [{contents = 0}; {contents = 33}; {contents = 4}]
0 голосов
/ 01 апреля 2019

Список в ocaml - это всегда указатель на список или [].Хвост списка снова является списком, поэтому у вас уже есть указатель.Ссылка с другой стороны добавляет к этому еще одно косвенное указание.Таким образом, ваш ref [1; 2; 3] на самом деле является указателем на указатель на блок памяти, содержащий запись 1 и адрес хвоста.

Короче говоря, чтобы проверить, имеют ли два списка физически одинаковыеtail вы просто делаете 

List.tl list1 == List.tl list2

Это проверяет физическое равенство, проверяет, являются ли они оба одинаковыми указателями.Помните, что у вас могут быть списки с одинаковым содержанием, которые физически не совпадают.Только списки, построенные из одного хвоста, будут совпадать.

0 голосов
/ 27 марта 2019

Прежде всего let ls = ref [1; 2; 3] не имеет особого смысла в этом контексте - он делает ls изменяемым, но не само содержимое списка. Попробуйте что-то вроде этого: 

let ls = [1; 2; 3]
let tail1 = List.tl ls (* Note the type is `int list option` here, not `int list` *)
let tail2 = List.tl ls
assert (tail1 = tail2)

Обратите внимание, что важно использовать = вместо == в последней строке - вам нужна проверка на семантическое равенство, а не на физическую (см. https://caml.inria.fr/pub/old_caml_site/FAQ/FAQ_EXPERT-eng.html#egalite для различий, подробно описанных).

0 голосов
/ 27 марта 2019

Если вы хотите получить хвост списка, просто наберите на нем List.tl. Кроме того, вы можете использовать сопоставление с образцом, чтобы извлечь хвост. Например, вы можете написать Lisp's nthcdr следующим образом: 

let rec nthcdr n list =
  if (n <= 0) then
    list
  else match list with
       | [] -> []
       | _::list -> (nthcdr (n - 1) list)

Вы можете использовать его следующим образом: 

let x = [1; 2; 3; 4] in
  assert ((nthcdr 3 x) == (nthcdr 3 x))

На практике вышеупомянутая функция была бы обернута в другую, которая проверяет, является ли N отрицательным перед повторением.

...