仅使用"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工具包的一部分.而且,正如上面的代码所示,从第一原理构建起来非常简单!