基于自定义树实现的Scheme CPS过程equal-tree$的bug修复求助
关于CPS风格Scheme树结构一致性判断过程的bug修复请求
背景:Scheme树的列表实现方式
以下是用列表实现Scheme树的新方式:
(define make-tree list) (define add-subtree cons) (define make-leaf (lambda (x) x)) (define empty-tree? empty?) (define first-subtree car) (define rest-tree cdr) (define composite-tree? list?) (define leaf? (lambda (x) (not (composite-tree? x))))
需求:实现CPS风格的equal-tree$过程
需要实现CPS风格的过程equal-tree$,该过程接收两棵叶子节点带值的树t1、t2,以及两个续延succ和fail,按以下规则判断它们的结构一致性:
- 若
t1和t2结构相同,则返回一棵结构一致的树,其中每个叶子节点包含原两棵树对应位置的叶子节点组成的序对(无论叶子值是否相等); - 若结构不同,则返回深度优先遍历中首次出现冲突的子树组成的序对。
示例
(define id (lambda (x) x)) (equal-trees$ '(1 (2) (3 9)) '(7 (2) (3 5)) id id) → '((1 . 7) ((2 . 2)) ((3 . 3) (9 . 5)))
我的错误实现及问题
我尝试实现该过程,但遇到了bug,针对上述示例,我的代码输出结果为'(1 . 7),而非预期的结果,不清楚原因所在,请求帮助排查并修复。我的实现代码如下:
(define equal-tree$ (lambda (tree1 tree2 succ fail) (if (and (empty? tree1) (empty? tree2)) '() (if (or (empty? tree1) (empty? tree2)) (fail '()) (if (and (leaf? tree1) (leaf? tree2)) (succ (cons tree1 tree2)) (if (or (leaf? tree1) (leaf? tree2)) (fail (cons (car tree1) (car tree2))) (equal-tree$ (car tree1) (car tree2) (lambda (X) cons(cons (car tree1) (car tree2)) x) fail))))))
内容的提问来源于stack exchange,提问作者Tariq Ganem
相关产品推荐
相关产品推荐

