0

使用 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定义？

4

4 回答 4

2

OCaml 标准库中的list类型是不可变的，你不能用它做任何事情。将指向列表的指针放入可变单元格不会使列表本身可变。幸运的是，您可以实现可变列表，甚至可以遵循 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]}它将包含一个指向不可变列表的指针。您可以将 to 更改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}]
于 2019-03-27T12:27:22.363 回答
0

如果你想得到一个列表的尾部，只需调用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 是否为负。

于 2019-03-27T12:09:36.653 回答
0

首先，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差异详细解释）。==

于 2019-03-27T12:55:38.160 回答
0

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

长话短说，检查 2 个列表是否具有相同的尾部，您只需执行

List.tl list1 == List.tl list2

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

于 2019-04-01T13:27:21.167 回答