在Scheme中的树数据结构算法？

Question

迄今为止我的知识水平已经能够毫不费力地完成《小小计算机》的阅读，并且我目前已经完成了《老手计算机》的70%。我脑海中已经有了一些想法，希望通过工作实践来学习Scheme语言，但是（也许是因为我在职业生涯中主要使用面向对象的语言），我仍然在思考如何用函数式的Scheme语言解决一些相当基本的问题，比如面向对象的语言。

与其在单个stackoverflow问题中提出所有问题，我宁愿分散在时间上逐个提出问题，并认为这些问题会自动落到位，所以我不需要其他问题的答案。

很明显，Scheme的特点是列表。无数的列表和列表中嵌套的列表。我习惯于能够存储包含“属性”的列表，可以快速检索（即散列表）并可以相互嵌套。

以传递文件系统中文件和目录的列表为例，如何在Scheme中处理类似的问题呢？我猜你可以传递一个类似这样的数据结构：

'(("foo" (("bar.txt")
          ("zip.txt")
          ("button.txt")))
  ("other.txt")
  ("one-more" (("time.txt"))))

每个节点都被表示为列表的汽车，它的子节点则表示为包含在其cdr的另一个列表中，因此上面的内容是一棵树的结构：

foo/
  bar.txt
  zip.txt
  button.txt
other.txt
one-more/
  time.txt

也许可以传递一个接受访问者的迭代函数来进行某种深度树遍历？（对于如何知道何时切换目录，我不是完全确定它的外观）。

在这种问题上是否存在一般模式，不仅是目录树，还包括带有附加元数据的树结构？

与面向对象的等效方法相比，这是否不可避免地变得非常棘手？

- d11wtq

Answer 1

“Scheme 的特点很明显是列表。”

“传统上，是的。但自 R6RS 以来，也有带有命名字段的记录（records），这使得处理其他类型的数据结构变得更加容易。实际的 Scheme 实现已经有了数十年，但它们从未被标准化，因此语法各不相同。”

“对于这种问题，不仅仅是目录树，而是树形结构（带有元数据）一般都有一个通用模式。”

“是的，你的“迭代器函数”的想法正中要害。（除了最好定义一个宏，这样你就可以说：”

(for-each-label (x tree 'in-order)
  (display x))

宏是使用define-syntax创建的。

- Fred Foo

Answer 2

我看到你的问题有两个部分。

第一部分：如何在Scheme中实现树。

在标准的R5RS中，大多数树的实现使用向量来表示树中的节点。对于一个二叉树，可以定义一些辅助函数：

(define (tree-left t) (vector-ref t 0))
(define (tree-right t) (vector-ref t 1))
(define (tree-value t) (vector-ref t 2))
(define (make-node l r v) (vector l r v))
(define (leaf? t) (eq? t #f))

在结构体/记录的Schemes中，上述内容被替换为>

(define-struct tree (left right value))
(define (leaf? t) (eq? t #f))

如果支持结构层次，则可以编写以下内容：

如果支持结构层次，则可以编写

(define-struct tree ())
(define-struct (leaf tree) ())
(define-struct (node tree) (left right value))

对于支持模式匹配代码的方案，操作树形结构的代码看起来很像ML和Haskell中的树处理代码。

我推荐阅读HtDP中关于二叉搜索树部分的内容： http://htdp.org/2003-09-26/Book/curriculum-Z-H-19.html#node_sec_14.2

第二部分：如何处理目录遍历

有几种方法。一种常见的方法是提供一个函数，给定一个目录，生成一个可以逐个产生一个元素（文件或子目录）的函数或序列。这样可以避免在内存中存储可能巨大的文件树。

在Racket中，可以使用序列：

#lang racket
(for ([file (in-directory "/users/me")])
   (displayln file))

R5RS中没有可用的目录遍历机制，但所有主要的实现都提供了一种或另一种方式来实现。

顺便说一下：虽然Scheme提供了非常好的单向链表支持，但在实现函数式数据结构时，使用向量甚至更好的结构通常更好，因为可以更快地随机访问元素。

- soegaard