如何通过索引获取子树? [英] How do I get a subtree by index?

问题描述

假设我有以下树:

在我的程序中，这棵树用一个列表表示:'(+ (* 5 6) (sqrt 3)).

In my program, this tree is represented using a list: '(+ (* 5 6) (sqrt 3)).

如何通过索引获取子树?

How do I get a subtree by its index?

索引应该从 0 开始并且深度优先.在上图中，我用索引标记了所有节点以显示这一点.

The index should start from 0 and be depth-first. In the picture above, I have labelled all the nodes with their index to show this.

例如:

(define tree '(+ (* 5 6) (sqrt 3)))

(subtree tree 0)  ; Returns: '(+ (* 5 6) (sqrt 3)))
(subtree tree 1)  ; Returns: '(* 5 6)
(subtree tree 2)  ; Returns: 5
(subtree tree 3)  ; Returns: 6
(subtree tree 4)  ; Returns: '(sqrt 3)
(subtree tree 5)  ; Returns: 3

我尝试像这样实现subtree:

(define (subtree tree index)
  (cond [(= index 0) tree]
        [else
         (subtree (cdr tree)
                  (- index 1))]))

然而，这不会遍历子列表.这是不正确的.

However, this does not traverse into sublists. It is incorrect.

我尝试使用延续传递风格实现subtree:

I tried to implement subtree using continuation-passing style:

(define (subtree& exp index counter f)
  (cond [(= counter index) exp]
        [(null? exp) (f counter)]
        [(list? exp)
         (let ((children (cdr exp)))
           (subtree& (car children)
                     index
                     (+ counter 1)
                     (lambda (counter2)
                       (if (null? (cdr children))
                           (f counter)
                           (subtree& (cadr children)
                                     index
                                     (+ counter2 1)
                                     f)))))]
        [else (f counter)]))

(define (subtree tree index)
  (subtree& tree
            index
            0
            (lambda (_)
              (error "Index out of bounds" index))))

这适用于如下树:

• '(+ 1 2)
• '(+ (* 5 6) (sqrt 3))

但是，它对于如下树失败了:

However, it fails for trees like:

• '(+ 1 2 3)

我的实现有什么问题?

推荐答案

无需繁琐的控制结构即可做到这一点的方法是制定议程.

The way to do this without hairy control constructs is with an agenda.

但在此之前，定义抽象.每次我看到正在行走的代码，它称为树"，并且充满了明确的car、cdr &c 我不得不阻止自己简单地冷-启动宇宙，希望我们能得到更好的.如果教你的人没有告诉你这个对他们说狠话.

But before you do that, define abstractions. Every time I look at code which is walking something it calls a 'tree' and is full of explicit car, cdr &c I have to stop myself from simply cold-booting the universe in the hope we get a better one. If whoever is teaching you is not telling you this have strong words with them.

这里是树结构的一些抽象.这些特别重要，因为树结构真的很不规则:我希望能够在任何节点上说给我这个节点的孩子":叶子只是没有孩子的节点，不是某种特殊的东西.

Here are some abstractions for the tree structure. These are particularly important because the tree structure is really irregular: I want to be able to say 'give me the children of this node' on any node: leaves are just nodes with no children, not some special kind of thing.

(define (make-node value . children)
  ;; make a tree node with value and children
  (if (null? children)
      value
      (cons value children)))

(define (node-value node)
  ;; the value of a node
  (if (cons? node)
      (car node)
      node))

(define (node-children node)
  ;; the children of a node as a list.
  (if (cons? node)
      (cdr node)
      '()))

现在对议程进行一些抽象.议程表示为列表，但当然没有其他人知道这一点，而且更具工业实力的实施可能不希望这样表示.

Now some abstractions for the agenda. Agendas are represented as lists, but nothing else knows this of course, and a more industrial-strength implementation might well not want to represent them like that.

(define empty-agenda
  ;; an empty agenda
  '())

(define agenda-empty?
  ;; is an agenda empty?
  empty?)

(define (agenda-next agenda)
  ;; return the next element of an agenda if it is not empty
  ;; error if it is
  (if (not (null? agenda))
      (car agenda)
      (error 'agenda-next "empty agenda")))

(define (agenda-rest agenda)
  ;; Return an agenda without the next element, or error if the
  ;; agenda is empty
  (if (not (null? agenda))
      (cdr agenda)
      (error 'agenda-rest "empty agenda")))

(define (agenda-prepend agenda things)
  ;; Prepend things to agenda: the first element of things will be
  ;; the next element of the new agenda
  (append things agenda))

(define (agenda-append agenda things)
  ;; append things to agenda: the elements of things will be after
  ;; all elements of agenda in the new agenda
  (append agenda things))

现在可以轻松编写函数的纯迭代版本(议程是维护堆栈)，无需各种繁琐的控制结构.

Now it's easy to write a purely iterative version of the function (the agenda is maintaining the stack), without all sorts of hairy control constructs.

(define (node-indexed root index)
  ;; find the node with index index in root.
  (let ni-loop ([idx 0]
                [agenda (agenda-prepend empty-agenda (list root))])
    (cond [(agenda-empty? agenda)
           ;; we're out of agenda: raise an exception
           (error 'node-indexed "no node with index ~A" index)]
          [(= idx index)
           ;; we've found it: it's whatever is next on the agenda
           (agenda-next agenda)]
          [else
           ;; carry on after adding all the children of this node
           ;; to the agenda
           (ni-loop (+ idx 1)
                    (agenda-prepend (agenda-rest agenda)
                                    (node-children
                                     (agenda-next agenda))))])))

---

需要考虑的事情:如果在上述函数中将 agenda-prepend 替换为 agenda-append 会发生什么?

---

A thing to think about: what happens if you replace agenda-prepend by agenda-append in the above function?

这篇关于如何通过索引获取子树?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！