scheme - 计算列表和子列表的元素

Question

我正在尝试创建一个函数来计算列表中的所有元素，包括其子列表的元素。最初，为了开始，我提出了一个基本函数 myList:

(define myLength 
  (lambda (L)
    (cond
      ((null? L) 0)
      (else (+ 1 (myLength (cdr L)))))))

但是，它无法帮助我解释函数调用，例如:

(numAtoms '())              "...should be 0"
(numAtoms '(()))            "...should be 0"
(numAtoms '(1 1))           "...should be 2"
(numAtoms '(1 (1 1) 1))     "...should be 4"
(numAtoms '(1 (1 (1 1)) 1)) "...should be 5"

我正在尝试使用基本函数，例如 length、null? 和 list?。

Answer 1

我认为这里的诀窍是想象如何将输入转换为要用来计算总和的代码。让我们根据 cons 和 '() 以及您的数据中出现的任何其他原子，以完全扩展的形式编写您的每个输入:

'()               == '()
'(())             == (cons '() '())
'(1 1)            == (cons 1 (cons 1 '()))
'(1 (1 1) 1)      == (cons 1 (cons 1 (cons 1 '())) (cons 1 '()))
'(1 (1 (1 1)) 1)  == ...

现在，如果将每次出现的 cons 替换为 +，并将每次出现的 '() 替换为 ，看看会发生什么>0，并且每次出现不是 '() 和 1 的内容。你会:

'()                                         => 0                           == 0
(cons '() '())                              => (+ 0 0)                     == 0
(cons 1 (cons 1 '()))                       => (+ 1 (+ 1 0))               == 2
(cons 1 (cons 1 (cons 1 '())) (cons 1 '())) => (+ 1 (+ 1 (+ 1 0)) (+ 1 0)) == 4
...                                         => ...                         == ...

请注意，那些总和 正是您想要的值!基于此，您可能不想将您的输入视为一个列表，而更像是一个由 cons 单元构建的树。通常，您可以通过指定一个函数来映射树，该函数应用于处理一对的递归结果，以及一个函数来处理树的原子:

(define (treeduce pair-fn atom-fn tree)
  (if (pair? tree)
      (pair-fn (treeduce pair-fn atom-fn (car tree))
               (treeduce pair-fn atom-fn (cdr tree)))
      (atom-fn tree)))

然后，您可以实现 cons 到 + 的映射，如果它是一个列表，则其他所有内容都到 1 和 0 如果不是:

(define (non-null-atoms tree)
  (treeduce +
            (lambda (atom) 
              (if (not (null? atom))
                  1
                  0))
            tree))

这会产生您期望的结果:

(non-null-atoms '())              ;=> 0
(non-null-atoms '(()))            ;=> 0
(non-null-atoms '(1 1))           ;=> 2
(non-null-atoms '(1 (1 1) 1))     ;=> 4
(non-null-atoms '(1 (1 (1 1)) 1)) ;=> 5