Using Scheme, how to keep a variable's value during recursive calls (nested lists)?

Question

I'm trying to remove the last occurrence of a value from a list, and my program is failing during the recursive call with nested lists.

I have a function that counts the number of occurrences of the symbol:

(define (countOccurrences lst elem count)
  (cond
    [(empty? lst)            count]
    [(list? (car lst))       (countOccurrences (cdr lst) elem
                                         (countOccurrences (car lst) elem count))]
    [(equal? (car lst) elem) (countOccurrences (cdr lst) elem (add1 count))]
    [else                    (countOccurrences (cdr lst) elem count)]))

And the main body is here:

(define (lastLess lst elem)
  (let ((count (countOccurrences lst elem 0)))
    (if (< 0 count)
        (lastLessHelper lst elem count)
        lst)))

Helper function:

(define (lastLessHelper lst elem count)
  (cond
    [(empty? lst)         empty]
    [(eq? count 0)        (cdr lst)]
    [(eq? (car lst) elem) (set! count (sub1 count))
                          (cond
                            [(eq? count 0) (cdr lst)]
                            [else          (cons (car lst)
                                                 (lastLessHelper (cdr lst) elem count))])]
    [(list? (car lst))    (cons (lastLessHelper (car lst) elem count)
                                (lastLessHelper (cdr lst) elem count))]
    [else                 (cons (car lst) (lastLessHelper (cdr lst) elem count))]))

The problem is this line:

[(list? (car lst)) (cons (lastLessHelper (car lst) elem count) (lastLessHelper (cdr lst) elem count))]

I decrement the 'count' variable whenever the (car lst) is equal to elem, and during the first recursive call (lastLessHelper (car lst) elem count) it decrements correctly, but when that call returns and it recurses on the cdr lst: (lastLessHelper (cdr lst) elem count))] the value of 'count' returns to its original value.

It works for a normal list input, such as (lastLess '(1 2 3 2 4 5) '2)) I correctly get (1 2 3 4 5), but when using nested lists as input, such as (lastLess '(1 (2 3) 4 2 5) '2) it returns (1 (2 3) 4 2 5).

How to keep the value of 'count' during the recursive calls? I should note, there is probably easier ways to do this, but this is a homework exercise and we are forbidden to use the 'reverse' call.

EDIT: Sylwester's comment helped me understand. My problem wasn't counting the occurrences of an item, the problem was to remove the last occurrence of an item. My thought was to first count the occurrences of that item, then traverse the list and decrement that count until it was 0, then I would know to remove that item, and then just cons the rest of the list.

Sylwester · Accepted Answer · 2015-09-13 18:21:06Z

2

You never need to use set!

(define (count-matches needle haystack)
  ;; helper
  (define (count-matches count haystack)
    (cond ((equal? needle haystack) (+ count 1))
          ((pair? haystack)
           (count-matches (count-matches count (car haystack))
                          (cdr haystack)))
          (else count)))

  ;; call helper
  (count-matches 0 haystack))

(count-matches 2 '(1 (2 3) 4 2 5)) ; ==> 2

As you see we use the count towards the recursion in car and use the return value as the count in the recursion of cdr.

answered Sep 13, 2015 at 18:21

Sylwester

48.9k4 gold badges52 silver badges83 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Al5678 Over a year ago

Thanks, this makes sense, however I'm still lost on how to decrement this count as the list is traversed. When I step through the debugger using DrRacket, I can see the value of count go from '1' back up to '2' when executing the two recursive calls [(list? (car lst)) (cons (lastLessHelper (car lst) elem count) (lastLessHelper (cdr lst) elem count))]

Sylwester Over a year ago

@Al5678 It's not the same variable. You recurse and give the same named variable in the next round a new value. In your example you are cons-ing the recursion of the car and cdr, thus you can expect it to be a pair? and not a number. You could use + and then it would add the two together but both uses count so if it is 2 you'll get 2 more than you wat at each round. One of them needs to have 0 as count. Or you could do as I did using count against the car recursion and using the result in the cdr recursion.

Óscar López · Accepted Answer · 2015-09-13 18:55:35Z

2

You don't even need a counter variable or a helper procedure, just return each partial result as you go and accumulate the subresults of the recursive calls. Try this, using the standard template for traversing a list of lists:

(define (count-matches ele lst)
  (cond ((null? lst)                ; if the list is empty
         0)                         ; return default value
        ((not (pair? lst))          ; if this is a single element
         (if (equal? lst ele) 1 0)) ; check if it matches
        (else                       ; otherwise accumulate results of
         (+ (count-matches ele (car lst))     ; the `car` part
            (count-matches ele (cdr lst)))))) ; and the `cdr` part

For example:

(count-matches 'x '(1 (x 2) 3 x (4 (5 x)) 6 (x)))
=> 4

edited Sep 13, 2015 at 18:55

answered Sep 13, 2015 at 18:50

Óscar López

237k38 gold badges321 silver badges391 bronze badges

Collectives™ on Stack Overflow

Using Scheme, how to keep a variable's value during recursive calls (nested lists)?

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related