CODEWITHSUNDEEP
listschemeracket
user7014623
user7014623

Reputation:

Counting number of zeroes in lists in scheme

(define (num-zeroes lst)
(define (helper lst sofar)
 (cond ((null? lst) sofar)
    ((list? (car lst)) (helper (car lst) sofar))
    ((eq? lst 0) (helper (cdr lst) (+ 1 sofar)))
    (else
     (helper (cdr lst) sofar))))
(helper lst 0))

This function is suppose to count the number of 0s in a list. However, it keeps giving me 0 when I input values. How would I be able to fix this?

Upvotes: 1

Views: 1862

Answers (1)

user2609980
user2609980

Reputation: 10474

In your third condition you are comparing lst to 0. This should be (car lst).

Because of your (list? (car lst)) condition it looks like you want to count nested lists. There is an issue with this in the current implementation (with the above check fixed) since the conditional does not add up separate parts of the list.

E.g.,

(num-zeroes '(0 0 (1 0) (1 0 0))) ; => 3

To fix this you can do something like this:

(define (num-zeroes lst)
  (define (helper lst sofar)
    (cond ((null? lst) sofar)
          ((list? (car lst)) (+ sofar                        ;; add sofar to
                                (helper (car lst) 0)         ;; branched out first part
                                (helper (cdr lst) 0)))       ;; and branched rest
          ((eq? (car lst) 0) (helper (cdr lst) (+ 1 sofar))) ;; (car lst), not lst
          (else
           (helper (cdr lst) sofar))))
  (helper lst 0))

This leads to:

(num-zeroes '(0 0 (1 (1 (0 0) 0)) (1 0 0)))  ;; => 7

Now, variations on your problem where you want to do something over a collection and keep an accumulated value happen a lot. fold is a higher-order function that is designed specifically for these problems.

Fold takes a function with two arguments (an element and an accumulator), a starting value and a collection. It successively applies the function to each element of the collection and at the end returns the accumulator.

In your case it's possible to only add 1 to the accumulator when the element is 0, and pass a flattened list (flatten removes the nesting from a list) to foldl (see https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28lib._racket%2Fprivate%2Flist..rkt%29._foldl%29%29) (the l means it walks the list from left to right) to deal with nesting:

(define (num-zeroes2 lst)
  (foldl (lambda (e acc)
           (if (= e 0)
               (+ acc 1)
               acc))
         0
         (flatten lst)))

This leads to the same result:

(num-zeroes2 '(0 0 (1 (1 (0 0) 0)) (1 0 0))) ;; => 7

Or, thinking about it, you can also flatten the list and filter out all values equal to 0 (there is a library method called zero? for that), and count the elements:

(define (num-zeroes3 lst)
  (length
   (filter zero? (flatten lst))))

Hope this helps.

Upvotes: 2

Related Questions