仅使用"The Little Schemer"中的表格来拼合列表. [英] Flatten a list using only the forms in "The Little Schemer"

问题描述

我正在通过Little Schemer学习Scheme(作为一名老C程序员)，并且作为练习，我尝试编写一个程序来使用The Little Schemer中的 only 形式来扁平化列表. ;即define，lambda，cond，car，cdr，and，or等，但不是 append.我以为这很容易，但我一直无法提出解决方案.我该怎么办?

I'm going through The LIttle Schemer to learn Scheme (as an old C programmer) and as an exercise I tried to write a procedure to flatten a list using only the forms in The Little Schemer; I.e., define, lambda, cond, car, cdr, and, or, etc., but not append. I thought it would be easy but I haven't been able to come up with a solution. How can I do this ?

推荐答案

我有一个仅使用第一原理"操作且效率很高的版本(与的解决方案). :-)

I have a version that uses only "first-principles" operations and is efficient (does not require more than one pass through any of the lists, unlike append-based solutions). :-)

它通过定义两个简单的构建块(fold和reverse)，然后在这些构建块的顶部定义flatten(及其辅助函数，reverse-flatten-into)来做到这一点(并注意每个函数是一个还是两个)行):

It does this by defining two simple building blocks (fold and reverse), and then defining flatten (and its helper, reverse-flatten-into) atop those (and notice how each function is just one or two lines long):

;; 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?.

The only external functions used are: cons, car, cdr, null?, and pair?.

此功能的主要见解是fold是非常的强大功能，应成为任何Schemer工具包的一部分.而且，如上面的代码所示，从第一原理构建起来是如此简单！

The key insight from this function is that fold is a very powerful operation, and should be part of any Schemer's toolkit. And, as seen in the code above, it's so simple to build from first principles!

这篇关于仅使用"The Little Schemer"中的表格来拼合列表.的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！