CODEWITHSUNDEEP
recursionscheme
Bernardo Ortiz
Bernardo Ortiz

Reputation: 95

Count occurrences of an atom in a nested list in Scheme

Hello, I'm new to Scheme.

I'm reading tutorials on the web, and I wonder how I could count occurrences of atoms in nested lists in Scheme. I found some tutorials mentioning bagify and flatten; I tried to mix them but I got an error. What could be wrong?

Here's the code:

(define (bagify lst)
  (foldl (lambda (key ht)
         (hash-update ht key add1 0))
       #hash() lst))

(define (flatten mylist)
  (cond ((null? mylist) '())
        ((list? (car mylist)) (append (flatten (car mylist)) (flatten (cdr mylist))))
        (else (cons (car mylist) (flatten (cdr mylist))) (bagify(mylist)))))

Upvotes: 1

Views: 2356

Answers (1)

acfoltzer
acfoltzer

Reputation: 5608

I think bagify and flatten are red herrings for this kind of problem. Sure, you could use flatten, and then count the occurrences in the resulting flattened list. However, it's much more efficient and straightforward to just traverse the nested list.

For simplicity, let's start by implementing the function for the non-nested case. Here's a version that counts occurrences of '?, for even more simplicity:

(define count-?s
  (lambda (ls)
    (cond
      [(null? ls) 0]
      [(eq? (car ls) '?) (add1 (count-?s (cdr ls)))]
      [else (count-?s (cdr ls))])))

Changing this to work on nested lists just requires adding one cond line. The implementation of flatten you found contains a hint here: we want to check at each step of the recursion whether the car of the list is itself a list (However, using list? is more power than we need; we can use pair? instead, as long as our input is always a proper, nested list).

Once we know the car is also a (potentially-nested) list, we need to pass it to a function that knows how to handle lists. Fortunately, we're in the middle of defining one!

(define count-?s*
  (lambda (ls)
    (cond
      [(null? ls) 0]
      [(pair? (car ls)) (+ (count-?s* (car ls)) (count-?s* (cdr ls)))]
      [(eq? (car ls) '?) (add1 (count-?s* (cdr ls)))]
      [else (count-?s* (cdr ls))])))

And that's all there is to it. Very little thought involved, no? So little, in fact, that you can just replace a couple expressions and wind up with a function that does something completely different to the nested list:

(define remove-?s*
  (lambda (ls)
    (cond
      [(null? ls) '()]
      [(pair? (car ls)) (cons (remove-?s* (car ls)) (remove-?s* (cdr ls)))]
      [(eq? (car ls) '?) (remove-?s* (cdr ls))]
      [else (cons (car ls) (remove-?s* (cdr ls)))])))

Solving a problem for a nested list is really easy once you've solved it for a flat list.

  1. Start with the flat list solution.
  2. Check for a pair in the car.
  3. Do the natural recursion on both the car and the cdr.
  4. Combine the answers with a binary operator that makes sense with the left-hand side of the null? case, e.g., +/0, */1, cons/'(), and/#t, or/#f.

Upvotes: 4

Related Questions