如何在 OCaml 中获取指向列表尾部的指针?

How to get a pointer to the tail of a list in OCaml?

使用 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 中实现等效项?

假设我有这个:

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如何定义?

如果您想获取列表的尾部,只需对其调用 List.tl。 或者,您可以使用模式匹配来提取尾部。 比如Lisp的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 是否为负数。

OCaml 标准库中的 list 类型是不可变的,您无法对其进行任何操作。将指向列表的指针放入可变单元格不会使列表本身可变。幸运的是,您可以实现可变列表,甚至可以遵循 lisp 数据表示,例如

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

虽然类型系统会与你作对 :)

此外,您似乎混淆了指针和引用。在 OCaml 中,所有装箱类型(如列表、字符串、浮点数等)都表示为指针。 intchar 等立即数类型和 NoneMy_constructor 等数据构造函数表示为带标记的整数。 (顺便说一句,这与所有现代 lisps 使用的表示相同)。

引用只是标准库中定义的类型

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

所以它是一个装箱类型,包含一个指向任意值的可变指针。所以,例如,你可以在那里放一个列表,{contents = [1;2]}, 它将包含一个指向 immutable 列表的指针。您可以更改 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}]

首先,let ls = ref [1; 2; 3] 在此上下文中没有太大意义 - 它使 ls 可变,但列表内容本身不是。试试这样的 smth:

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 以了解差异说明详情)。

ocaml 中的列表始终是指向列表或 [] 的指针。列表的尾部也是一个列表,因此您已经有了指针。另一方面,ref 为其添加了另一个间接寻址。所以你的ref [1; 2; 3]实际上是一个指针,指向一个内存块的指针,其中包含一条记录为1和尾部的地址。

长话短说,检查 2 个列表是否具有物理上相同的尾部,您只需这样做

List.tl list1 == List.tl list2

这会检查物理是否相等,检查它们是否是同一个指针。请注意,您可以拥有内容相同但物理上不同的列表。只有从相同尾部构建的列表才会匹配。