在方案中获取一棵树的有序叶子 [英] Getting the ordered leaves of a tree in scheme

问题描述

我正在做一个练习，以获取方案中嵌套列表的叶子"(来自 SICP).这是练习的输入输出:

I'm going through an exercise to grab the 'leaves' of a nested list in scheme (from SICP). Here is the exercise input-output:

(define x (list (lis 1 2) (list 3 4)))
(fringe x)
; (1 2 3 4)

(fringe (list x x))
; (1 2 3 4 1 2 3 4)

现在，我为此提出了两个答案:一个是递归的，一个是迭代的.下面是我的两个实现:

Now, I've come up with two answers for this: one recursive and one iterative. Here are my two implementations below:

(define (fr lst)
  (cond ((null? lst) '())
        ((not (pair? (car lst))) (cons (car lst) (fr (cdr lst))))
        (else (append (fr (car lst)) (fr (cdr lst))))))

(define (add-element-to-list lst elem)
  (if (null? lst)
      (list elem)
      (cons (car lst) (add-element-to-list (cdr lst) elem))))

(define (fringe lst)
 (define L '())
  (define (iter lst)
    (if (not (pair? (car lst)))
        (set! L (add-element-to-list L (car lst))) ; update the list if it's a leaf
        (iter (car lst)))                          ; otherwise recurse
    (if (not (null? (cdr lst))) (iter (cdr lst)))  ; and if we have a cdr, recurse on that
    L
    )
  (iter lst)
)

(fringe x)
(fr x)
(fr (list x x))
(fringe (list x x))
; (1 2 3 4)
; (1 2 3 4)
; (1 2 3 4 1 2 3 4)
; (1 2 3 4 1 2 3 4)
; OK

对我来说，问题是，这个练习让我在整个过程中花了很多时间才弄明白(而且在我写这篇文章的时候，我仍然很难明白").以下是我遇到的一些问题，看看是否有任何关于如何在方案中处理这些问题的建议:

The problem for me is, this exercise took me forever to figure out with a ton of head-bashing along the way (and it's still difficult for me to 'get it' as I write this up). Here are a few things I struggled with and seeing if there are any suggestions on ways to deal with these issues in scheme:

1. 我最初认为有两种情况.正常/标量情况和嵌套情况.不过，好像真的是三个！有正常情况，嵌套情况，然后是空情况——内部列表也有空情况！是否有一个很好的通用模式或其他东西来解释 null 情况?这是经常出现的事情吗?
2. 在迭代的情况下，为什么最后必须返回L?为什么 (iter lst) 不直接返回(即，如果我删除了 iter 函数底部的 standalone-L ).
3. 最后，是否有一种更干净"的方式来实现迭代案例?我的代码似乎太多了，可能还有待改进.

1. I thought initially that there are two cases. The normal/scalar case and the nested case. However, it seems like there are actually three! There's the normal case, the nested case, and then the null case -- and inner-lists also have the null case! Is there a good general pattern or something to account for the null case? Is this something that comes up a lot?
2. In the iterative case, why do I have to return L at the end? Why doesn't (iter lst) just return that (i.e., if I removed the standalone-L at the bottom of the iter function).
3. Finally, is there a 'cleaner' way to implement the iterative case? It seems like I have so much code, where it could probably be improved on.

推荐答案

出现三种情况的原因是您从其他语言中导入了一些标量/向量区别:Scheme 没有它，也没有帮助.相反，列表是一个递归定义的对象:列表要么是空列表，要么是一对事物和一个列表.这意味着有两个区别，而不是一个:一个对象是一对，一个对象是空列表:

The reason there are three cases is that you are importing some scalar / vector distinction from some other language: Scheme doesn't have it and it is not helpful. Instead a list is a recursively-defined object: a list is either the empty list, or it is a pair of something and a list. That means there are two distinctions to make, not one: is an object a pair, and is an object the empty list:

(define (lyst? o)
  (or (null? o)
      (and (pair? o) (lyst? (cdr o)))))

这与向量/标量的区别完全不同.我不知道你是从什么语言得到这个的，但是想想它的数学是如何工作的:向量是在一些标量场上定义的，并且没有向量也是一个标量.但是对于列表，是一个不是一对的列表.停止考虑向量和标量:这不是考虑列表、对和空列表的有用方法.

That's completely different than a vector / scalar distinction. I don't know what language you're getting this from, but just think about how the maths of this would work: vectors are defined over some scalar field, and there is no vector which is also a scalar. But for lists there is a list which is not a pair. Just stop thinking about vectors and scalars: it is not a helpful way to think about lists, pairs and the empty list.

迭代版本太可怕了:SICP 还没有引入 set! 是有原因的.

The iterative version is too horrible to think about: there's a reason why SICP hasn't introduced set! yet.

首先，它实际上并不是迭代的:就像网络上针对这个问题的大多数迭代"解决方案一样，它看起来好像是这样，但事实并非如此.不是的原因是 iter 函数的骨架看起来像

First of all it's not actually iterative: like most of the 'iterative' solutions to this problem on the net it looks as if it is, but it's not. The reason it's not is that the skeleton of the iter function looks like

1. 如果等等
   • 递归对列表的第一个元素
   • 否则做别的事情

• 迭代列表的其余部分

• iterate on the rest of the list

关键是 (1) 和 (2) 总是发生，所以调用列表的 car 不是尾调用:它是一个成熟的递归调用.

And the critical thing is that both (1) and (2) always happen, so the call into the car of the list is not a tail call: it's a fully-fledged recursive call.

话虽如此，您可以做得更好:做这种事情的绝对标准方法是使用累加器:

That being said you can make this much better: the absolutely standard way of doing this sort of thing is to use an accumulator:

(define (fringe l)
  (define (fringe-loop thing accum)
    (cond
      ((null? thing)
       ;; we're at the end of the list or an element which is empty list
       accum)
      ((pair? thing)
       ;; we need to look at both the first of the list and the rest of the list
       ;; Note that the order is rest then first which means the accumulator
       ;; comes back in a good order
       (fringe-loop (car thing)
                    (fringe-loop (cdr thing) accum)))
      (else
       ;; not a list at all: collect this "atomic" thing
       (cons thing accum))))
  (fringe-loop l '()))

请注意，这是自下而上构建边缘(线性)列表，这是使用递归构建线性列表的自然方式.为了实现这一点，它稍微有点狡猾地排列它看待事物的方式，以便结果以正确的顺序出现.还要注意，这也不是迭代的:它是递归的，因为 (fringe-loop ... (fringe-loop ...)) 调用.但这一次要清楚得多.

Note that this builds the fringe (linear) list from the bottom up, which is the natural way of building linear lists with recursion. To achieve this it slightly deviously orders the way it looks at things so the results come out in the right order. Note also that this is also not iterative: it's recursive, because of the (fringe-loop ... (fringe-loop ...)) call. But this time that's much clearer.

它不是迭代的原因是搜索(树状，Lisp)列表的过程不是迭代的:这就是 SICP 所说的递归过程"，因为(Lisp 的树状)列表在两者中递归定义他们的第一场和休息场.您所做的任何事情都不会使过程迭代.

The reason it's not iterative is that the process of searching a (tree-like, Lisp) list is not iterative: it's what SICP would call a 'recursive process' because (Lisp's tree-like) lists are recursively defined in both their first and rest field. Nothing you can do will make the process iterative.

但是您可以通过显式管理堆栈使代码在实现级别出现迭代，从而将其转换为尾递归版本.计算过程的性质并没有改变:

But you can make the code to appear iterative at the implementation level by managing the stack explicitly thus turning it into a tail recursive version. The nature of the computational process doesn't change though:

(define (fringe l)
  (define (fringe-loop thing accum stack)
    (cond
      ((null? thing)
       ;; ignore the () sentinel or () element
       (if (null? stack)
           ;; nothing more to do
           accum
           ;; continue with the thing most recently put aside
           (fringe-loop (car stack) accum (cdr stack))))
      ((pair? thing)
       ;; carry on to the right, remembering to look to the left later
       (fringe-loop (cdr thing) accum (cons (car thing) stack)))
      (else
       ;; we're going to collect this atomic thing but we also need 
       ;; to check the stack
       (if (null? stack)
           ;; we're done
           (cons thing accum)
           ;; collect this and continue with what was put aside
           (fringe-loop (car stack) (cons thing accum) (cdr stack))))))
  (fringe-loop l '() '()))

这是否值得取决于您认为递归调用的成本以及是否有任何递归限制.然而，明确管理您接下来要执行的操作的一般技巧通常很有用，因为它可以更轻松地控制搜索顺序.

Whether that's worth it depends on how expensive you think recursive calls are and whether there is any recursion limit. However the general trick of explicitly managing what you are going to do next is useful in general as it can make it much easier to control search order.

(当然，请注意，您可以对任何程序执行这样的技巧！)

(Note, of course, that you can do a trick like this for any program at all!)

这篇关于在方案中获取一棵树的有序叶子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！