I can't get a Scheme function to recursively invoke f on a nested list for the correct result

Question

I didn't do too hot on a test I took recently in a class. However, since everyone else bombed it as well, our professor is willing to give us some "make up" points by proving to her that we know Scheme (not so great at it...). She'd ask different questions from what was on the test, though. So I'm working on the questions that were on the test to get better with Scheme, and I can't seem to get the following one to work.

Write a Scheme function reduce which takes two parameters: f, a function which takes a single parameter, and x, an arbitrary value. The reduce function recursively invokes f using each nested list contained in x and then replaces the original nested list with the result of invoking f.

For example, invoking (reduce (lambda(x) (cons 'list x)) '(3 7 9 z s (3 (78 2 3)))) should return:

'(list 3 7 9 z s (list 3 (list 78 2 3)))

Also, invoking (reduce (lambda (x) (cdr x)) '(3 7 9 z s (3 (78 2 3)))) should return:

'(7 9 z s ((2 3))), where the first element is removed from each nested list.

This is the code I came up with:

(define reduce
  (lambda (f x)
    (if (null? x)'()
    (let ((var (car x)))
    (cond
      ((cons? var) (cons (f var) (reduce f (cdr x))))
      ((symbol? var) (cons var (reduce f (cdr x))))
      ((number? var) (cons var (reduce f (cdr x)))))))))

If I enter the example inputs, these are my results:

(reduce (lambda(x) (cons 'list x)) '(3 7 9 z s (3 (78 2 3))))

(list 3 7 9 'z 's (list 'list 3 (list 78 2 3)))

there's an extra 'list coming from who knows where

;

(reduce (lambda(x) (cdr x)) '(3 7 9 z s (3 (78 2 3))))

(list 3 7 9 'z 's (list (list 78 2 3)))

it only removes the 3 in the 2nd nested loop. It should remove the 3 in the first one, 3 in the middle and the 78 in the 3rd. It also shouldn't have the word "list" in it

;

I'm assuming the problem is in the line ((cons? var), but I can't seem to figure out how to fix it.

We didn't go too far into the Scheme language, so we haven't learned a whole lot of special methods; it's mainly all just recursion.

Any help would be much appreciated.

Thanks.

Answer 1

Here's my implementation:

(define (reduce f x)
  (define (inner x)
    (if (list? x)
        (f (map inner x))
        x))
  (inner x))

Examples:

> (reduce (lambda (x) `(list ,@x)) '(3 7 9 z s (3 (78 2 3))))
(list 3 7 9 z s (list 3 (list 78 2 3)))
> (reduce cdr '(3 7 9 z s (3 (78 2 3))))
(7 9 z s ((2 3)))

---

Here's a version that doesn't use map directly, but basically reimplements map (albeit using a hardcoded transformer):

(define (reduce f x)
  (define (transform lst)
    (if (null? lst)
        '()
        (cons (process (car lst)) (transform (cdr lst)))))
  (define (process x)
    (if (list? x)
        (f (transform x))
        x))
  (process x))