scheme - 仅使用“The Little Schemer”中的表格来展平列表

Question

我正在通过 The LIttle Schemer 学习 Scheme（作为一个老 C 程序员），作为一个练习，我尝试编写一个仅使用The Little Schemer 中的表单来展平列表的过程；即 , define, lambda, cond, car, cdr,等，and但不是。我认为这很容易，但我无法提出解决方案。我怎样才能做到这一点 ？or append

Answer 1

我有一个仅使用“第一原则”操作且高效的版本（与基于 - 的解决方案不同，不需要多次通过任何列表append）。:-)

它通过定义两个简单的构建块（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?。

这个函数的主要观点是这fold是一个非常强大的操作，应该是任何 Schemer 工具包的一部分。而且，如上面的代码所示，从第一原理构建起来非常简单！

Answer 2

我不熟悉 Little Schemer 原语，因此您可能需要对其进行调整以适应。

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

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

然后flatten可以根据 this 编写函数。

不确定这是否超出规则:)

Answer 3

这是一个尝试。它使用 cons 并避免追加，因为它只会切掉它可以到达的第一个非对，并将其限制为它已经建立的新尾巴的扁平化。有时它会重写列表，然后再次调用 flatten。Def不是最有效的方法。

固定代码：

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