时间戳

首页 > 解决方案 > 如何在 lisp 中制作引用结构槽的符号？

binary-tree - 如何在 lisp 中制作引用结构槽的符号？

问题描述

我正在自学 lisp，并认为一个不错的非平凡程序是编写一组标准的树插入和操作例程。我认为它可以用 CONS 来完成，但想用一个结构来尝试它。

我整理了一个有效的版本：

(defstruct treenode data left right)

(defun tree-insert ( value tree )
"Insert data into tree"
(if tree
  (if (< value (treenode-data tree))
       (setf (treenode-left tree) (tree-insert value (treenode-left tree)))
       (setf (treenode-right tree) (tree-insert value (treenode-right tree))))
  (setf tree (make-treenode :data value)))
tree)

它在每一步都重建了这棵树，这似乎计算效率低下。低效是指每次进行另一级递归时都必须使用 setf 。所以我想尝试一个通过引用而不是通过值传递树的方案，这样我就可以在插入树的子例程中进行分配。

我将以下内容拼凑在一起，但不起作用（但请感谢我的评论）：

(defstruct treenode data left right)

(defun tree-insert ( value tree )
"Insert data value into tree, using pass by reference.

value  A datum to insert, in this version has to be a number.
tree   The tree passed as a symbol."  

(setq tval (symbol-value tree))
(if (eq tval nil)
  (set tree (make-treenode :data value))          ; Empty tree. Place data here.
  (if (< value (treenode-data tval))              ; Non-empty node.  Decide which subtree for insert.
      (tree-insert value (treenode-left tval))    ; Left side
      (tree-insert value (treenode-right tval)))) ; Right side.  This is a stable sort.   
nil)

? (setf tr nil)
NIL
? (tree-insert 10 'tr)
NIL
? tr
#S(TREENODE :DATA 10 :LEFT NIL :RIGHT NIL)
?

初始插入工作正常。传递一个符号，(set tree ...) 正确地插入了左右指针为零的结构。

当然，随之而来的问题是在递归调用 tree-insert 时我没有传递符号。

那就是挂机。我还没有找到一种方法将结构槽称为符号，然后我可以将其传递给树插入。

我已经环顾了几天，发现了一个关于 defstruct 宏的有趣评论：“defstruct 不仅为每个插槽定义了一个访问函数，而且还安排 setf 在此类访问函数上正常工作，定义了一个名为name-p，定义了一个名为 make-name 的构造函数，并定义了一个名为 copy-name 的复制器函数。所有自动创建的函数的名称都被保存在处理 defstruct 表单时当前的任何包中（参见包）。 , 所有这些函数都可以根据实现的自由裁量权声明为内联以提高效率；如果您不希望某些函数内联声明，请遵循带有 notinline 声明的 defstruct 形式来覆盖任何自动内联声明。”

那么，我能做些什么来发挥 setf 的魔力呢？我知道我可以使用 setf 对插槽进行分配，但由于词法范围规则，我还没有让 setf 在函数中工作。也许喜欢添加自动功能以允许生成符号，例如 (treenode-data-symbol tr)？

当然，在我的第一个 PDP-8/L 之前，lisp 程序员就已经处理过二叉树了。这样做的方式是什么？

这是一个已编辑的问题。用户 Rainer Joswig 给出了非常快速简洁的回复。我从他举的例子中学到了很多。我对直接修改树而不是使用函数的返回值的问题感兴趣。

从我在这里看到的评论和 Rainer Joswig 的一个答案中，我是否应该得出这样的结论：指针操作的计算成本很低，并且最好的 lisp 方法是使用返回树而不是依赖的函数关于修改论点的方法？

标签： binary-treecommon-lispsymbols

解决方案

为您提供灵感的简单版本：

(defstruct node a b v)

(defun insert-tree (tree value)
  (cond ((null tree)
         (setf tree (make-node :v value)))
        ((> (node-v tree)
            value)
         (setf (node-a tree)
               (insert-tree (node-a tree) value)))
        (t
         (setf (node-b tree)
               (insert-tree (node-b tree) value))))
  tree)

使用它：

CL-USER 171 > (let ((tree nil))
                (loop for i in '(4 7 3 5 9 10 11 8)
                      do (setf tree (insert-tree tree i)))
                (pprint tree)
                (values))

#S(NODE :A #S(NODE :A NIL :B NIL :V 3)
        :B #S(NODE :A #S(NODE :A NIL :B NIL :V 5)
                   :B #S(NODE :A #S(NODE :A NIL :B NIL :V 8)
                              :B #S(NODE :A NIL
                                         :B #S(NODE :A NIL
                                                    :B NIL
                                                    :V 11)
                                         :V 10)
                              :V 9)
                   :V 7)
        :V 4)

现在，如果想要做更少的setf操作，我们可以检查返回的子树是否与我们传递的相同。只有当我们创建一个新节点时才会出现这种情况。

(defun insert-tree (tree value)
  (cond ((null tree)
         (setf tree (make-node :v value)))
        ((> (node-v tree)
            value)
         (let ((new-tree (insert-tree (node-a tree) value)))
           (unless (eql new-tree (node-a tree))
             (setf (node-a tree) new-tree))))
        (t
         (setf (node-b tree)
               (insert-tree (node-b tree) value))))
  tree)

或使用本地宏隐藏部分代码：

(defun insert-tree (tree value)
  (macrolet ((insert (place call &aux (new-value-sym (gensym "new-value")))
               `(let ((,new-value-sym ,call))
                  (unless (eql ,place ,new-value-sym)
                    (setf ,place ,new-value-sym)))))
    (cond ((null tree)
           (setf tree (make-node :v value)))
          ((> (node-v tree)
              value)
           (insert (node-a tree) (insert-tree (node-a tree) value)))
          (t
           (insert (node-b tree) (insert-tree (node-b tree) value))))
    tree))

推荐阅读