Scheme 以深度优先的方式遍历并打印一个DAG

Question

设 NODE 是一个在其闭包中带有 STORE 的函数。图表的所有叶子都有一个 STORE，它是一个单一值（常量或变量），所有内部节点都有一个 STORE，它是一个包含以下内容的列表：

代表函数的符号（'+'*'cos'sin等）
一个或多个 NODES 的列表，表示该 NODE 的子节点。
一个简化函数（与我的问题无关）。

假设 [[(NODE f)]] = [[(f STORE)]] 如果 f 是一个过程并且 STORE 是 NODE 闭包中的 STORE。

我正在尝试找到一种方法来遍历这棵树并打印一个可以用 (eval) 求值的表达式。我已经接近了，但我就是无法让它工作。

这是我的代码：

(define repr
  (lambda(store)
    (if (is_leaf? store)
        store
        (list (car store)
              (repr_helper (cadr store) repr)))))

(define repr_helper
  (lambda(f_list arg)
    (cond ((null? f_list) '())
          (else (cons ((car f_list) arg) (repr_helper (cdr f_list) arg))))))

简单的例子：假设一棵树添加了 4 个参数（创建一个 + 节点，有 4 个子节点，所有子节点都是叶子）。

((Add 10 'x 'y 'z) repr)

输出： '(+ (10 x y z))。

预期输出： '(+ 10 x y z)

如您所见，问题出在表达式中的额外括号。您可以想象，对于更复杂的示例，情况会更糟。我知道我在哪里创建列表以及为什么有括号，但我似乎找不到删除它的方法，正确打印值。

Answer 1

尝试修改构建列表的部分，如下所示：

(define repr
  (lambda (store)
    (if (is_leaf? store)
        store
        (cons (car store)
              (repr_helper (cadr store) repr)))))

我们只需要在 repr_helper 返回的列表的头部添加一个新项目，调用 cons 就可以了。

Scheme 以深度优先的方式遍历并打印一个DAG

Scheme Traverse and print a DAG in a depth first way

printing

scheme

functional-programming

tree-traversal

racket