Scheme中的树数据结构算法？

Question

到目前为止,我的知识水平是这样的,我已经完成了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

或者也许会传递一个接受访问者的迭代器函数,而不是进行某种深树遍历？(在知道何时切换目录方面,并不完全确定外观如何).

当涉及到这类问题时,是否存在一般模式,而不仅仅是目录树,而是树结构(附带元数据)？

与面向对象的等价物相比,这不可避免地完成得非常繁琐吗？

Answer 1

很明显,Scheme的东西就是列表.

传统上,是的.但由于R6RS,也有记录与命名字段,这使得与其他类型的数据结构的工作很多更加容易.实际的Scheme实现已经有了几十年,但它们从未标准化,因此语法各不相同.

当涉及到这类问题时,是否存在一般模式,而不仅仅是目录树,而是树结构(附带元数据)？

是的,并且凭借你对"迭代器功能"的想法,你已经击中了头部.(除了定义一个宏会更优雅,所以你可以说:

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

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

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))

在具有结构/记录的方案中,上面用>替换

(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

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

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

在Racket中,可以使用序列:

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

R5RS中没有可用的目录遍历机制,但当然所有主要实现都提供了某种方式.

BTW:这是真的,该计划提供了非常单链表很好的支持,但实现的功能的数据结构时,它往往是更好地使用矢量甚至更好的结构,由于更快的随机元素访问.