Nested Map

I was in the #lisp chat room at Freenode when someone posed a question about performing a map function over a nested lists. This was an interesting problem, so I thought that I would cover it here.

Suppose there was a complex tree of numbers:

((1 2) (3 4))

And you want to map each to a function (let’s say a squaring function) and maintain its structure. This is where a good utility function would be in order. The function must be able to handle trees of an unknown structure. So, the only solution that I know would be to use recursion:

(defun nested-map (fn item)
    (cond ((null item) nil)
          ((atom item)   (funcall fn item))
          ((consp item) (cons (nested-map fn (car item))
                                 (nested-map fn (cdr item))))))

Even though it looks complex, the function seems correct:

CL-USER> (nested-map #'(lambda (x) (* x x))
           '((1 2) (3 4)))
((1 4) (9 16))
CL-USER> (nested-map #'(lambda (x) (* x x))
           '(1 2 (3 4 (5 6 7))))
(1 4 (9 16 (25 36 49)))

I think I’ll keep this in my utility toolkit. I am concerned about the performance, but I won’t worry too much about it until it becomes a problem.

%d bloggers like this: