Lisp中树结构的定义 [英] Definition of tree structure in Lisp

问题描述

来自Common Lisp HyperSpec词汇表:

From the Common Lisp HyperSpec glossary:

树 n. 1.二进制递归数据结构，由conses和 原子:优点本身也是树(有时称为 子树"或分支")，原子是终端节点(有时 称为叶子).通常，叶子代表数据，而叶子代表 分支在该数据之间建立某种关系. 2.一般而言， 任何具有分支"概念的递归数据结构，以及 树叶.

tree n. 1. a binary recursive data structure made up of conses and atoms: the conses are themselves also trees (sometimes called "subtrees" or "branches"), and the atoms are terminal nodes (sometimes called leaves). Typically, the leaves represent data while the branches establish some relationship among that data. 2. in general, any recursive data structure that has some notion of "branches" and leaves.

树结构. (一棵树的)构成树的一组约束. 请注意，尽管每个此类缺点的car [1b]组件都是 树结构，是树中每个缺点的汽车的对象 本身不是树结构的一部分，除非它们也 简而言之.

tree structure n. (of a tree) the set of conses that make up the tree. Note that while the car[1b] component of each such cons is part of the tree structure, the objects that are the cars of each cons in the tree are not themselves part of its tree structure unless they are also conses.

树形结构定义中的最后一句提出了一个问题，那就是也可以对cdrs说同样的话吗?

The last sentence in the definition of tree structure raises a question, which is, can the same be said about cdrs too?

在树"的定义中使用二进制"一词似乎表明，就树而言，car与cdr之间没有区别，但是随后，树结构"的定义似乎将汽车视为特殊，所以我很困惑.

Use of the word binary in the definition of "tree" seems to suggest that there is no difference between car vs cdr for the purposes of trees, but then the definition of "tree structure" seems to treat cars special, so I am confused.

推荐答案

简短答案

树结构定义中的最后一句提出了一个 问题是，也可以对cdrs说同样的话吗?

The last sentence in the definition of tree structure raises a question, which is, can the same be said about cdrs too?

我认为答案是是". 列表结构的定义与此类似，措辞几乎相同.在列表结构中，关于缺点车的价值是否是列表结构的一部分，存在更多的混淆可能性，因为可能会引起一些疑问，例如，替换列表中的X是什么意思(X(X)是)?" CDR并不是真正的问题，因为CDR是列表中的 rest .显然是列表结构的一部分.

I think the answer is "yes." There's a similar definition for list structure with almost identical wording. There's more potential for confusion about in list structure about whether the value of a car of a cons is part of the list structure, since questions can aris about, e.g., "what does it mean to replace X in the list (X (X) Y)?" The cdr isn't really in question much, since the cdr is the rest of the list; it's sort of obviously part of the list structure.

对于树结构，我认为模棱两可较少；汽车中的缺点或cdr是子树. 树结构和列表结构的定义在地方几乎相同，如果有人为列表结构写了定义，我不会感到惊讶，然后将其复制为树结构，以使进行准确更改所需的最少更改次数最少.即使在实践中可能不会出现有关汽车的问题，但这也会留下一些关于汽车的信息.

For tree structure, I think that there's less ambiguity; cons in the car or the cdr is a subtree. The definitions of tree structure and list structure are almost identical in places, and I wouldn't be surprised if someone wrote the definition for list structure, and then copied it for tree structure, making the minimal number of changes necessary to be accurate. That would leave the bit about cars in there, even though the question that it answers probably wouldn't arise in practice.

让我们看一下列表结构的定义并进行比较:

Let's look at the definition of list structure and compare:

列表结构. (列表中的)构成列表的一组cons. 请注意，虽然每个这样的缺点的汽车组成部分是 列表结构，即作为列表元素的对象(即 列表中每个缺点的汽车的对象)不是 本身就是其列表结构的一部分，即使它们很简单，但 在(循环)情况下，列表实际上包含其中之一 尾巴作为元素. (列表的列表结构有时是 按顺序冗余地称为其``顶级列表结构'' 强调列表中的任何要素都不是 参与进来.)

list structure n. (of a list) the set of conses that make up the list. Note that while the car component of each such cons is part of the list structure, the objects that are elements of the list (i.e., the objects that are the cars of each cons in the list) are not themselves part of its list structure, even if they are conses, except in the (circular) case where the list actually contains one of its tails as an element. (The list structure of a list is sometimes redundantly referred to as its ``top-level list structure'' in order to emphasize that any conses that are elements of the list are not involved.)

请注意这些地方的不同之处:

Note the specific places where these differ:

(列表结构)请注意，尽管每个这样的缺点的汽车组成部分都是 列表结构，即作为列表元素的对象(即 列表中每个缺点的汽车的对象)不是 即使它们很简单，它们本身也是其列表结构的一部分.

(list structure) Note that while the car component of each such cons is part of the list structure, the objects that are elements of the list (i.e., the objects that are the cars of each cons in the list) are not themselves part of its list structure, even if they are conses.

(树形结构)请注意，尽管每个这样的缺点的汽车组成部分都是 树结构，是树中每个缺点的汽车的对象 本身不是树结构的一部分，除非它们也 简而言之.

(tree structure) Note that while the car component of each such cons is part of the tree structure, the objects that are the cars of each cons in the tree are not themselves part of its tree structure unless they are also conses.

这意味着在

(1 (2) 3) == (cons 1 (cons (cons 2 nil) (cons 3 nil)))

列表结构中有三个 cons单元，树结构中有四个 cons单元.

there are three cons cells in the list structure, and four cons cells in the tree structure.

这实际上有什么关系?准确定义这些术语非常重要，以便规范可以轻松定义特定功能遍历或修改列表或树的哪些部分.

Where does this actually matter? It becomes important to define these terms precisely so that the specification can easily define what parts of a list or tree are traversed or modified by particular functions.

例如，函数 nsubst 和朋友，其文档指出:

For instance, the functions nsubst and friends, whose documentation states:

nsubst，nsubst-if和nsubst-if-not可能会更改 树结构 树.

nsubst, nsubst-if, and nsubst-if-not might alter the tree structure of tree.

对树结构的特定定义使我们能够了解 nsubst 可能会和可能不会更改的事物.

A specific definition of tree structure allows us to understand what things may and may not be changed by nsubst.

树结构. (一棵树的)构成树的一组约束. 请注意，虽然每个这样的缺点的汽车组成部分是 树结构，是树中每个缺点的汽车的对象 本身不是树结构的一部分，除非它们也 简而言之.

tree structure n. (of a tree) the set of conses that make up the tree. Note that while the car component of each such cons is part of the tree structure, the objects that are the cars of each cons in the tree are not themselves part of its tree structure unless they are also conses.

所以，这告诉我们，对于树中的任何cons单元格 x ， nsubst 可能会做(setf(car x)…)，这样以后(car x)可能会有所不同，但是它不会修改(car x)返回的实际对象. (当然，除非有缺点).如果(car x)的值是其中可能有树的对象，则这可能很重要.因此，例如， nsubst 不会归入向量，但它将替换向量:

So, what this is telling us is that for any cons cell x in the tree, nsubst might do (setf (car x) …), so that the (car x) might be something different later on, but it won't modify the actual object that would be returned by (car x) (unless it's a cons, of course). This could be important in cases where the value of (car x) is an object that might have trees inside of it. So for instance, nsubst won't descend into vectors, but it will replace vectors:

(let* ((l (list 1 2 3))     ; a list
       (v (vector 0 l 4))   ; a vector that contains the list (and other elements)
       (tree (cons l v)))   ; a tree containing the list and the vector
  (nsubst 'x l tree))       ; replace the list in the tree with X
;=> (X . #(0 (1 2 3) 4))    ; nsubst doesn't descend into the vector, because it's
                            ; not tree structure

删除重复项可以修改列表结构

另一方面， 删除重复项 仅会修改列表结构:

delete-duplicates can modify list structure

On the other hand delete-duplicates will only modify list structure:

当序列是列表时，

删除重复项可以设置任何 按此顺序排列的顶级列表结构的一部分(汽车或cdr). 当序列是向量时，允许删除重复项 向量的尺寸并将其元素滑动到新的 位置而不会置换它们以产生结果向量.

delete-duplicates, when sequence is a list, is permitted to setf any part, car or cdr, of the top-level list structure in that sequence. When sequence is a vector, delete-duplicates is permitted to change the dimensions of the vector and to slide its elements into new positions without permuting them to produce the resulting vector.

这篇关于Lisp中树结构的定义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！