4

到目前为止，我的知识水平足以让我顺利完成 The Little Schemer，而我目前通过 The Seasoned Schemer 完成了 70%。在我的脑海中，我有一些想法，我想从事一些项目，以获得一些使用 Scheme 的实际经验，但是（也许是因为我在整个职业生涯中主要使用 OO 语言）我仍然发现自己想知道如何可以使用像 Scheme 这样的函数式语言来解决面向 OO 语言的一些相当基本的问题。

我不会把我所有的问题都放在一个 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

或者也许有人会传递一个接受访问者的迭代器函数，而不是进行某种深度树遍历？（就知道何时切换目录而言，不完全确定它的外观）。

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

与面向对象的等价物相比，这是否不可避免地会变得相当繁琐？

4

2 回答 2

6

很明显，Scheme 的东西是列表。

传统上，是的。但是从 R6RS 开始，也有带有命名字段的记录，这使得使用其他类型的数据结构变得更加容易。实用的 Scheme 实现已经使用了几十年，但它们从未标准化，因此语法各不相同。

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

是的，并且根据您对“迭代器函数”的想法，您已经一针见血了。（除了定义一个宏会更优雅，所以你可以说：

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

宏是用 .) 创建的define-syntax。）

于 2012-06-22T10:15:58.030 回答
6

我在你的问题中看到了两个部分。

第一部分：如何在 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))

在具有结构/记录的方案中，以上内容替换为>

(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-ZH-19.html#node_sec_14.2

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

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

在球拍中，可以使用序列：

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

R5RS 中没有可用的目录遍历机制，但是所有主要的实现当然都提供了一些这样做的方法。

顺便说一句：Scheme 确实为单链表提供了非常好的支持，但是在实现函数式数据结构时，由于更快的随机元素访问，通常最好使用向量甚至更好的结构。

于 2012-06-22T13:54:23.373 回答