Counting elements of a list and sublists

问题:

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"

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

回答1:

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

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
...                                         => ...                         == ...

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)))

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

回答2:

Here is a recursive template you can use:

(define (num-atoms lst)
  (cond ((pair? lst) (+ (num-atoms <??>) 
                        (num-atoms <??>)))
        ((null? lst) <??>) ; not an atom
        (else <??>)))      ; an atom

This next example uses a helper that has the accumulated value (num) as an argument.

(define (num-atoms lst)
  ;; locally defined helper
  (define (helper num lst)
    (cond ((pair? lst) (helper (helper <??> <??>) <??>)) ; recurse with the sum of elements from car
          ((null? lst) <??>)          ; return accumulated value
          (else (helper <??> <??>)))) ; recurse with add1 to num

  ;; procedure starts here
  (helper 0 lst))

Hope it helps

回答3:

Make my-length work for any argument type, list or 'atom'; then the recursive algorithm becomes almost trivial:

(define (my-length l)
  (cond ((null? l) 0)
        ((list? l) (+ (my-length (car l)) (my-length (cdr l))))
        (else 1)))  ; atom

> (my-length '(1 (1 (1 1)) 1)))
5