只使用“小小的Schemer”中的表格来展开列表

我正在通过The Little Schemer来学习Scheme（作为一名老C程序员），并且作为一个练习，我试图编写一个程序来使用The Little Schemer中的表单来压扁一个列表。 即， define ， lambda ， cond ， car ， cdr and ， or等等，但不能 append 。 我认为这很容易，但是我还没有能够提出解决scheme。 我该怎么做？

Answer 1

我有一个只使用“第一原则”操作的版本，并且效率很高（与append的解决scheme不同，不需要通过任何列表一次以上）。 🙂

这是通过定义两个简单的构build块（ fold和reverse ），然后定义flatten （和它的帮助者， reverse-flatten-into顶部（并注意每个函数是如何一两行）：

 ;; Similar to SRFI 1's fold (define (fold1 kons knil lst) (if (null? lst) knil (fold1 kons (kons (car lst) knil) (cdr lst)))) ;; Same as R5RS's reverse (define (reverse lst) (fold1 cons '() lst)) ;; Helper function (define (reverse-flatten-into x lst) (if (pair? x) (fold1 reverse-flatten-into lst x) (cons x lst))) (define (flatten . lst) (reverse (reverse-flatten-into lst '()))) 

唯一使用的外部函数是： cons ， car ， cdr ， null? ，和pair? 。

从这个function的关键洞察是fold是一个非常强大的操作，应该是任何Schemer的工具包的一部分。 而且，从上面的代码可以看出，从第一原则构build起来非常简单！

Answer 2

这是一个尝试。 它利用缺点避免了追加，因为它只是把第一个不成对的东西剔除掉，并且把它build立在一个新尾巴的扁平化上。 有时它重写列表，然后再次调用flatten。 不是最有效的方法。

固定代码：

 (define (flatten x) (cond ((null? x) x) ((and (pair? x) (not (pair? (car x)))) (cond ((null? (car x)) (flatten (cdr x))) (else (cons (car x) (flatten (cdr x)))))) ((and (pair? x) (pair? (car x))) (flatten (cons (caar x) (cons (cdar x) (cdr x))))) (else (cons x '())))) 

Answer 3

我不熟悉Little Schemer原语，所以您可能需要调整它以适应。

我不确定这是否是您想要的答案，但是您可以使用基元来编写append ：

 (define (append l1 l2) (cond ((null? l1) l2) (else (cons (car l1) (append (cdr l1) l2))))) 

然后可以用这个方式来写flatten函数。

不知道这是否超出规则或不:)