仅使用“The Little Planer”中的表格来展平列表

Question

我正在通过《The LIttle Schemer》来学习Scheme（作为一名老C程序员），作为练习，我尝试编写一个过程来仅使用《Little Schemer》中的表单来展平列表；即，define、lambda、cond、car、cdr、和、或等，但不是附加。我认为这很容易，但我一直无法想出解决方案。我该怎么做？

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 是一个非常强大的操作，并且应该成为任何计划者工具包的一部分。而且，如上面的代码所示，从第一原理构建起来非常简单！

Answer 2

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

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

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

然后可以据此编写 flatten 函数。

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

Answer 3

这是一个尝试。它可以避免使用 cons 并避免追加，因为它只会削掉它可以到达的第一个非对，并将其压平它所构建的新尾部。有时它会重写列表，然后再次调用展平。绝对不是最有效的方法。

固定代码：

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