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 工具包的一部分。而且，如上面的代码所示，从第一原则构建非常简单!