how many elements on list with scheme

Question

i need to write a function which calculates how many elements on list with scheme language.

for example

(howMany 'a) returns 0
(howMany '(a b)) returns 1
(howMany '(a (b c))) returns 2

how can i do that? i did not want a working code, just only an idea for do that. so maybe you should consider to remove working codes. :) thank you

Answer 1

This will most likely get down-voted for this phrase, but, I don't know scheme. I am, however, familiar with functional programming.

If there is no built-in for this, start by 'folding' the list with start value of 0 and add 1 on every additional fold.

Answer 2

The fold answers will work. However, if this is homework, you may be trying to do this using only simple built-in functions. There are two possible answers.

Here's the naive way:

(define (howMany list)
  (if (null? list)
      0
      (+ 1 (howMany (cdr list)))))

(Your implementation of Scheme may have a function empty? instead of null?.)

However, this algorithm will take an amount of space linearly proportional to the number of elements in the list, because it will store (+ 1 ...) for each element of the list before doing any of the additions. Intuitively, you shouldn't need this. Here's a better algorithm that avoids that issue:

(define (howMany list)
   (define (iter numSoFar restOfList)
      (if (null? list)  
          numSoFar
          (iter (+ numSoFar 1) (cdr list))))
   (iter 0 list))

(Bonus points: use Scheme's (let iter ...) syntax to write this more succinctly. I used this style because it's more clear if you only know a few Scheme primitives.)

Answer 3

It is simply counting the number of elements in the list.

(define howMany
   (lambda (list)
      (cond
         [(not (list? list)) 0]
         [(null? list) 0]
         [else (+ 1 (howMany (cdr list)))])))