lists/compound data

Question

how would you develop a function one that would consume a list of symbols and returns the same list but with every instance of 'cat doubled?

so for example

 (one (cons 'animal(cons 'table (cons 'cat (cons 'bread
    empty)))))

I would get (I suppose)

 (cons 'animal (cons 'table (cons 'cat (cons 'cat (cons 'bread 
    empty)))))

in return. I am getting frustrated reading the book and trying to figure this out.

Answer 1

This is one of the simplest examples of how to recursively traverse a list while building another list. You should write it yourself, because you're in the process of learning. I'll help you a bit with the general structure of the solution, fill in the blanks:

(define (copy lst)
  (if <???>                 ; is the list empty?
      <???>                 ; if so, return the empty list
      (cons <???>           ; otherwise `cons` the first element of the list (*)
            (copy <???>)))) ; and advance the recursion over the rest of the list

(*) ... but if the element is 'cat, then cons two copies of it.

Test it with the list in the question:

(copy (cons 'one (cons 'animal (cons 'table (cons 'cat (cons 'bread empty))))))

... Which happens to be equivalent to this:

(copy '(one animal table cat bread))

Either way, the result is a copy of the input list with the same elements (and two copies of each 'cat found), but residing inside new cons-cells.

Answer 2

Leppie (who told me to "go play with your mutation in the traffic ;p" in response to my set-car!/set-cdr! comment above ;-)) wanted me to write a fold-based solution, so here it is!

(define (fun lst)
  (fold-right (lambda (e r)
                (case e
                 ((cat) (cons* e e r))
                 (else (cons e r))))
              '() lst))