Racket Nested-Lists and applying functions to them

Question

I'm trying to teach myself Racket. I'm currently trying to write a function to help understand nested lists. The function takes a nested list and a procedure and applies the procedure to each element to produce a new list. An example:

(map-tree even? '(1 2 3 4)) => '(#f #t #f #t)

Here's what I've got so far:

(define (map-tree proc tree)
  (map-tree-aux tree proc '() ))

(define (map-tree-aux tree proc lst)
 (if (null? tree)
  lst
  (if (list? tree)
      (if (null? (cdr tree))
          (if (number? (car tree))
                  (map-tree-aux (car tree) proc (append-end (proc (car tree)) lst))
                  (map-tree-aux (car tree) proc lst))
          (if (number? (car tree))
                  (map-tree-aux (cdr tree) proc (append-end (proc (car tree)) (map-tree-aux (car tree) proc lst)))
                  (map-tree-aux (cdr tree) proc lst)))
      lst)))

(define (append-end elem lst)
  (append lst (list elem)))

While this works with the original example I supplied, a more complex example comes out incorrectly:

(map-tree even? '(1 (2 (3 (4))))) should be '(#f (#t (#f (#t)))), but is currently (#f #t #f #t).

I know it's just a matter is "listing" somewhere, but I'm having an issue finding out how to do it.

My first thought was to apply the list procedure to the lst if the tree is null and (car tree) is not a number, but I get the opposite of what I want (the resultant list is nested in the opposite direction). I'd really appreciate your help.

Thanks!

assefamaru assefamaru · Accepted Answer · 2017-09-23T16:14:15

When iterating over list of lists, the general idea for the cases to check is:

if list is empty (null? lst), do something ...
if the first item in list is atomic (not (pair? (car lst))), do something else ...
if the first item in list is a list itself (pair? (car lst)), else ...

Choosing the right construct is also important, ie. instead of nesting if statements, using cond or match etc. is preferred.

Also try and avoid using non-constant time procedures (such as append) in your recursive steps to improve efficiency.

With these in mind, one approach to create the function in question is by simply using cons to build a new list while preserving the structure of the old, as follows:

(define (my-map pred lst)
  (cond
    ((null? lst) '())
    ((not (pair? (car lst)))
     (cons (pred (car lst))
           (my-map pred (cdr lst))))
    (else
     (cons (my-map pred (car lst))
           (my-map pred (cdr lst))))))

You can write the same function using match instead of cond:

(define (my-map pred lst)
  (match lst
    ['() '()]
    [(cons (? pair?) b)
     (cons (my-map pred (car lst))
           (my-map pred (cdr lst)))]
    [(cons a b)
     (cons (pred (car lst))
           (my-map pred (cdr lst)))]))

You can also build a tail-recursive function that does this:

(define (my-map pred lst)
  (let loop ((lst lst)
             (acc '()))
    (cond
      ((null? lst)
       (reverse acc))
      ((not (pair? (car lst)))
       (loop (cdr lst) (cons (pred (car lst)) acc)))
      (else
       (loop (cdr lst) (cons (loop (car lst) '()) acc))))))

Notice that (reverse acc) is returned in the base case because the list being built in the accumulator acc is in reverse order from the original list lst. To avoid this, we can modify this function to accumulate a continuation instead:

(define (my-map pred lst)
  (let loop ((lst lst)
             (acc identity))
    (cond
      ((null? lst)
       (acc '()))
      ((not (pair? (car lst)))
       (loop (cdr lst) (lambda (r)
                         (acc (cons (pred (car lst)) r)))))
      (else
       (loop (cdr lst)
             (lambda (r)
               (acc (cons (loop (car lst) identity) r))))))))

For all cases, you will have:

(my-map even? '(1 2 3 4 5 7))
=> '(#f #t #f #t #f #f)
(my-map even? '(1 (2 (3 (4 (5 (7)))))))
=> '(#f (#t (#f (#t (#f (#f))))))

Racket Nested-Lists and applying functions to them

1 Answers