计数列表和子列表的元素 [英] Counting elements of a list and sublists

问题描述

我正在尝试创建一个函数来计算列表中的所有元素，包括其子列表的元素.首先，我想出了一个基本功能myList:

I'm trying to create a function to count all the elements in a list, including the elements of its sublists. initially, to get started, i came up with a basic function myList:

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

但是，这并不能帮助我解释以下函数调用:

However, it doesn't help me account for function calls like:

(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?之类的基本功能.

I'm trying to use basic functions like length, null?, and list?.

推荐答案

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

I think the trick here is to imagine how you can transform your input into the code that you'd want to use to compute the sum. Let's write each of your inputs in the fully expanded form, in terms of cons and '() and whatever other atoms appear in your data:

'()               == '()
'(())             == (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替换每次出现的不是'()的东西，将会发生什么.您将拥有:

Now, look what would happen if you replaced each occurrence of cons with +, and each occurrence of '() with 0, and each occurrence of something that's not '() with 1. You'd have:

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

请注意，这些 sum 正是您想要的值！基于此，似乎您可能不想将输入作为 list 对待，就像将其作为由cons单元构建的 tree 一样.通常，您可以通过指定用于处理一对的递归结果的函数和用于处理树的原子的函数来映射到树上:

Notice that those sums are exactly the values that you want! Based on this, it seems like you might not want to treat your input as a list so much as a tree built from cons cells. In general, you can map over a tree by specifying a function to apply to the recursive results of processing a pair, and a function to process the atoms of the tree:

(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的映射，而不是通过:

You could then implement that mapping of cons to + and everything else to 1 if it's a list and 0 if it's not by:

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

这会产生您期望的结果:

This yields the kinds of results you'd expect:

(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

这篇关于计数列表和子列表的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！