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 of "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!
When iterating over list of lists, the general idea for the cases to check is:
(null? lst)
, do something ...(not (pair? (car lst)))
, do something else ...(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))))))