double in scheme

Question

How to write a program in scheme that takes an arbitrary sexpression consisting of integers and which returns an sexpression that is identical to the original but with all the integers doubled?

Answer 1

(define double
    (lambda (x)
      (cond ((null? x) (list))
        ((list? (car x)) (cons (double (car x)) (double (cdr x))))
        (else (cons (* 2 (car x)) (double (cdr x)))))))

EDIT Fixed this. Thanks to Nathan Sanders for pointing out my initial oversight concerning nested lists.

Answer 2

It sounds like what you want is to find each integer in the s-expression, then double it, while keeping the rest of it the same.

If you're not aware, s-expressions are just lists that may happen to contain other lists, and it makes sense to deal with them in levels. For instance, here's a way to print all the values on level one of an s-expression:

(define (print-level-one sexp)
  (display (car sexp))
  (print-level-one (cdr sexp)))

This will end up calling display on the car of every part of the s-expression.

You could do something similar. You'll need the functions integer? and pair? to check whether something is an integer, which should be doubled, or another list, which should be treated just like the top-level list.

(Note: I'm being deliberately vague because of the comment about homework above. If you just want the answer, rather than help figuring out the answer, say so and I'll change this.)

Answer 3

An Sexp of numbers is one of  
-- Number  
-- ListOfSexp  

A ListOfSexp is one of  
-- empty  
-- (cons Sexp ListOfSexp)  

So, you'll need one function to handle both of those data definitions. Since the data definitions cross-reference each other, the functions will do the same. Each individual function is pretty straight forward.

Answer 4

(define (double E)
  (cond ((null? E) '()) 
        ((list? (car E)) (cons (double (car E)) (double (cdr E))))
        ((number? E) (list E))
        (else (cons (* 2 (car E)) (double (cdr E))))
        ))

Answer 5

(map (lambda (x) (* x 2)) '(1 2 3 4 5)) => '(2 4 6 8 10)

What does it do? (lambda (x) (* x 2)) takes a number and doubles it, and map applies that function to every element of a list.

Edit: Oh, but it won't go into trees.

Answer 6

We want a procedure that takes an S-expression as input, and outputs an S-expression with the same structure, but where each integer is doubled; generally, a procedure to map S-expressions:

(define (double x)
  (if (number? x)
      (* x 2)
      x)))

(define (sexp-map op sexp)
  ...)

(sexp-map double some-sexpression)

The S-expression we get (SEXP) is going to be either an atom, in which case the result is (OP SEXP), or a list of S-expressions. We might think to map OP across SEXP in this case, but S-expressions nest arbitrarily deep. What we should actually do is map a procedure that will transform each element in the smaller S-expression with OP. Well would you look at that, that's just another way to describe of the goal of the procedure we're currently trying to write. So we can map SEXP-MAP across SEXP.

Well, no we can't actually, because SEXP-MAP needs to be called with two arguments, and MAP will only give it the one. To get around that, we use a helper procedure F of one argument:

(define (sexp-map op sexp)
  (define (f x)
    (if (list? x)
        (map f x)
        (op x)))
  (f sexp))

F winds up doing all the real work. SEXP-MAP is reduced to being a facade that's easier to use for the programmer.