在方案中获取树的有序叶子
Getting the ordered leaves of a tree in scheme
我正在做一个练习来获取 scheme 中嵌套列表的 'leaves'（来自 SICP）。这是练习的输入输出：
(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)
现在，我对此提出了两种答案：一种是递归的，一种是迭代的。下面是我的两个实现：
(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
对我来说问题是，这个练习让我花了很长时间才弄明白，一路上我都在不停地抨击（而且我在写这篇文章时仍然很难'get it'）。以下是我遇到的一些问题，看看是否有任何关于如何在方案中处理这些问题的建议：
- 我最初认为有两种情况。 normal/scalar 案例和嵌套案例。不过，好像真的是三个！有正常情况、嵌套情况，然后是空情况——内部列表也有空情况！是否有一个很好的通用模式或一些东西来解释 null 情况？这是经常出现的事情吗？
- 在迭代的情况下，为什么最后要return
L？为什么 (iter lst) 不只是 return 那个（即，如果我删除了 iter 函数底部的独立 L）。
- 最后，有没有'cleaner'实现迭代案例的方法？看来我的代码太多了，有待改进的地方。
出现三种情况的原因是您从其他语言中导入了一些标量/向量的区别：Scheme 没有它并且没有帮助。相反，列表是一个递归定义的对象：列表要么是空列表，要么是一对 something 和一个列表。这意味着有两个区别，而不是一个：一个对象是一对，一个对象是空列表：
(define (lyst? o)
(or (null? o)
(and (pair? o) (lyst? (cdr o)))))
这与向量/标量的区别完全不同。我不知道你是从什么语言得到这个的，但只要想一想这个数学是如何工作的：向量是在 over 一些标量场上定义的，并且没有向量也是一个标量。但是对于列表来说 是 不是一对的列表。只是停止考虑向量和标量：考虑列表、对和空列表不是一个有用的方法。
迭代版本想想就惨不忍睹：SICP还没有推出set!是有原因的
首先，它实际上并不是迭代的：就像网上针对此问题的大多数 'iterative' 解决方案一样，它看起来好像是，但事实并非如此。不是的原因是 iter 函数的骨架看起来像
- 如果废话
- 在列表的第一个元素上递归
- 否则做点别的事情
- 如果其他废话
- 迭代 列表的其余部分
关键是 (1) 和 (2) 总是会发生，所以调用列表的 car 不是尾调用：它是一个完整的-成熟的递归调用。
也就是说你可以做得更好：做这种事情的绝对标准方法是使用累加器：
(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 ...)) 调用。但这次更清楚了。
它不是迭代的原因是搜索（树状，Lisp）列表的过程不是迭代的：这就是 SICP 所说的 'recursive process' 因为（Lisp 的树状）列表是递归的在他们的第一个和其余字段中定义。您无能为力会使过程迭代。
但是您可以通过显式管理堆栈从而将其变成尾递归，从而使 code 到 appear 在实现级别迭代版本。计算过程的性质并没有改变：
(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 '() '()))
这是否值得取决于您认为递归调用的成本有多高以及是否存在任何递归限制。但是，明确管理下一步要做什么的一般技巧通常很有用，因为它可以更轻松地控制搜索顺序。
（请注意，当然，您可以对任何程序执行这样的技巧！）
大约类型。有原则的发展遵循 类型 。然后就变成了easy.
Lisp 是一种无类型语言。这就像类固醇的汇编程序。没有 类型 ，对您能够编码的内容没有限制。
语言没有强制类型，但仍然有 类型，概念上。我们编码为类型，我们处理类型，我们根据给定的规范生成值，即根据需要为更大的系统的各个部分正确接口，为了我们编写的函数正确地协同工作等需要某些类型的值，等等
我们正在构建 fringe 的是什么？是“列表”吗？
什么是“列表”？是吗
(define (list? ls)
(or (null? ls)
(and (pair? ls)
(list? (cdr ls)))))
这是我们正在构建的fringe吗？为什么它对 car 的事情什么也没说，我们是否要忽略 car 中的任何内容？为什么，不，当然不是。我们不会转换 list。我们实际上是在转换一个 tree:
(define (tree? ls)
(or (null? ls)
(and (pair? ls)
(tree? (car ls))
(tree? (cdr ls)))))
里面只有()就够了吗？应该不是。
是吗
(define (tree? ls)
(or (null? ls)
(not (pair? ls)) ;; (atom? ls) is what we mean
(and ;; (pair? ls)
(tree? (car ls))
(tree? (cdr ls)))))
它1一个tree?显然是，但我们暂时把它放在一边。
我们这里有一种结构化的、有原则的方式来将一段数据视为属于某种类型。或者如某些人所说，数据类型.
那么我们只需遵循数据类型定义/谓词的相同框架，编写一个函数，以某种特定方式处理所述类型的值（这是 Sterling 和 Shapiro 提倡的方法 "Prolog 的艺术").
(define (tree-fringe ls)
那么，它生产什么？它的叶子中的原子列表，就是这样。
(cond
((null? ls)
一个()已经是一个list?.
ls)
((not (pair? ls)) ;; (atom? ls) is what we mean
(handle-atom-case ls))
让我们暂时搁置它。进入下一个案例，
(else
;; (tree? (car ls))
;; (tree? (cdr ls))
ls 的 car 和 cdr 都是 tree?。如何处理它们，我们已经知道了。这是
(let ((a (tree-fringe (car ls)))
(b (tree-fringe (cdr ls)))
我们要用这两块来做什么？我们把它们拼凑起来。首先从左边开始边缘，然后从右边开始。简单：
(append a b )))))
(define (handle-atom-case ls)
;; bad name, inline its code inside
;; the `tree-fringe` later, when we have it
那么，append 在其两个参数中期望什么类型的数据？又是一个list?.
这就是我们必须生成的原子“树”。这样的“树”是它自己的边缘。除了，
;; tree: 1 2
;; fringe: ( 1 ) ( 2 )
它必须是 list?。将一个原子数据（任何数据）转换为包含该数据的 list? 实际上非常简单。
........ )
这是我们在这里必须想出的唯一重要的事情，才能找到解决方案。
递归是将事物分解成与整个事物相似的子部分，用相同的过程转换那些我们正在尝试编写，然后以一些简单直接的方式组合结果。
如果一个 tree? 包含两个 更小的 trees?，那么，我们中奖了——我们已经知道如何处理它们了！
当我们拥有结构数据类型时，我们已经有办法将它们分开。这就是它们的定义方式。
也许我稍后会回答你的第二个问题。
我正在做一个练习来获取 scheme 中嵌套列表的 'leaves'（来自 SICP）。这是练习的输入输出：
(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)
现在，我对此提出了两种答案：一种是递归的，一种是迭代的。下面是我的两个实现：
(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
对我来说问题是，这个练习让我花了很长时间才弄明白，一路上我都在不停地抨击（而且我在写这篇文章时仍然很难'get it'）。以下是我遇到的一些问题，看看是否有任何关于如何在方案中处理这些问题的建议：
- 我最初认为有两种情况。 normal/scalar 案例和嵌套案例。不过，好像真的是三个！有正常情况、嵌套情况，然后是空情况——内部列表也有空情况！是否有一个很好的通用模式或一些东西来解释 null 情况？这是经常出现的事情吗？
- 在迭代的情况下，为什么最后要return
L？为什么(iter lst)不只是 return 那个（即，如果我删除了iter函数底部的独立L）。 - 最后，有没有'cleaner'实现迭代案例的方法？看来我的代码太多了，有待改进的地方。
出现三种情况的原因是您从其他语言中导入了一些标量/向量的区别：Scheme 没有它并且没有帮助。相反，列表是一个递归定义的对象：列表要么是空列表，要么是一对 something 和一个列表。这意味着有两个区别，而不是一个：一个对象是一对，一个对象是空列表：
(define (lyst? o)
(or (null? o)
(and (pair? o) (lyst? (cdr o)))))
这与向量/标量的区别完全不同。我不知道你是从什么语言得到这个的，但只要想一想这个数学是如何工作的：向量是在 over 一些标量场上定义的，并且没有向量也是一个标量。但是对于列表来说 是 不是一对的列表。只是停止考虑向量和标量：考虑列表、对和空列表不是一个有用的方法。
迭代版本想想就惨不忍睹：SICP还没有推出set!是有原因的
首先，它实际上并不是迭代的：就像网上针对此问题的大多数 'iterative' 解决方案一样，它看起来好像是，但事实并非如此。不是的原因是 iter 函数的骨架看起来像
- 如果废话
- 在列表的第一个元素上递归
- 否则做点别的事情
- 如果其他废话
- 迭代 列表的其余部分
关键是 (1) 和 (2) 总是会发生，所以调用列表的 car 不是尾调用：它是一个完整的-成熟的递归调用。
也就是说你可以做得更好：做这种事情的绝对标准方法是使用累加器：
(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 ...)) 调用。但这次更清楚了。
它不是迭代的原因是搜索（树状，Lisp）列表的过程不是迭代的：这就是 SICP 所说的 'recursive process' 因为（Lisp 的树状）列表是递归的在他们的第一个和其余字段中定义。您无能为力会使过程迭代。
但是您可以通过显式管理堆栈从而将其变成尾递归，从而使 code 到 appear 在实现级别迭代版本。计算过程的性质并没有改变：
(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 '() '()))
这是否值得取决于您认为递归调用的成本有多高以及是否存在任何递归限制。但是，明确管理下一步要做什么的一般技巧通常很有用，因为它可以更轻松地控制搜索顺序。
（请注意，当然，您可以对任何程序执行这样的技巧！）
大约类型。有原则的发展遵循 类型 。然后就变成了easy.
Lisp 是一种无类型语言。这就像类固醇的汇编程序。没有 类型 ，对您能够编码的内容没有限制。
语言没有强制类型，但仍然有 类型，概念上。我们编码为类型，我们处理类型，我们根据给定的规范生成值，即根据需要为更大的系统的各个部分正确接口，为了我们编写的函数正确地协同工作等需要某些类型的值，等等
我们正在构建 fringe 的是什么？是“列表”吗？
什么是“列表”？是吗
(define (list? ls)
(or (null? ls)
(and (pair? ls)
(list? (cdr ls)))))
这是我们正在构建的fringe吗？为什么它对 car 的事情什么也没说，我们是否要忽略 car 中的任何内容？为什么，不，当然不是。我们不会转换 list。我们实际上是在转换一个 tree:
(define (tree? ls)
(or (null? ls)
(and (pair? ls)
(tree? (car ls))
(tree? (cdr ls)))))
里面只有()就够了吗？应该不是。
是吗
(define (tree? ls)
(or (null? ls)
(not (pair? ls)) ;; (atom? ls) is what we mean
(and ;; (pair? ls)
(tree? (car ls))
(tree? (cdr ls)))))
它1一个tree?显然是，但我们暂时把它放在一边。
我们这里有一种结构化的、有原则的方式来将一段数据视为属于某种类型。或者如某些人所说，数据类型.
那么我们只需遵循数据类型定义/谓词的相同框架，编写一个函数，以某种特定方式处理所述类型的值（这是 Sterling 和 Shapiro 提倡的方法 "Prolog 的艺术").
(define (tree-fringe ls)
那么，它生产什么？它的叶子中的原子列表，就是这样。
(cond
((null? ls)
一个()已经是一个list?.
ls)
((not (pair? ls)) ;; (atom? ls) is what we mean
(handle-atom-case ls))
让我们暂时搁置它。进入下一个案例，
(else
;; (tree? (car ls))
;; (tree? (cdr ls))
ls 的 car 和 cdr 都是 tree?。如何处理它们，我们已经知道了。这是
(let ((a (tree-fringe (car ls)))
(b (tree-fringe (cdr ls)))
我们要用这两块来做什么？我们把它们拼凑起来。首先从左边开始边缘，然后从右边开始。简单：
(append a b )))))
(define (handle-atom-case ls)
;; bad name, inline its code inside
;; the `tree-fringe` later, when we have it
那么，append 在其两个参数中期望什么类型的数据？又是一个list?.
这就是我们必须生成的原子“树”。这样的“树”是它自己的边缘。除了，
;; tree: 1 2
;; fringe: ( 1 ) ( 2 )
它必须是 list?。将一个原子数据（任何数据）转换为包含该数据的 list? 实际上非常简单。
........ )
这是我们在这里必须想出的唯一重要的事情，才能找到解决方案。
递归是将事物分解成与整个事物相似的子部分，用相同的过程转换那些我们正在尝试编写，然后以一些简单直接的方式组合结果。
如果一个 tree? 包含两个 更小的 trees?，那么，我们中奖了——我们已经知道如何处理它们了！
当我们拥有结构数据类型时，我们已经有办法将它们分开。这就是它们的定义方式。
也许我稍后会回答你的第二个问题。