4

Q: how can I map a function onto elements of nested lists?

For flat lists, we can use mapcar to apply a function to each element of the list:

(setq flat '("kittens" "puppies" "otters" "bunnies"))
(mapcar #'upcase flat)                  ; => ("KITTENS" "PUPPIES" "OTTERS" "BUNNIES")

But mapcar doesn't work on nested lists:

(setq nested '(("kittens" "puppies")
               ("otters" "bunnies")))
(mapcar #'upcase nested)                ; => ERROR

How can I map a function onto each element of a nested list, and get back a new list with the same structure as the old one?

Improve this question
2
  • 3
    One thing to note about recursive solutions using e.g. cl-labels or -tree-map is that Emacs doesn't handle recursion very efficiently and can easily blow the max-specpdl-size stack. So, they may be fine for personal use, but Elisp libraries should generally strive for iterative solutions with an explicit stack.
    – Basil
    Dec 19, 2018 at 13:24
  • @Basil: interesting point. Do you know of an iterative solution to avoid recursion?
    – Dan ♦
    Dec 19, 2018 at 13:42

4 Answers 4

Reset to default
5

You want to apply the solution recursively. For example:

(cl-labels ((upcase-nested
             (x)
             (cond ((consp x) (mapcar #'upcase-nested x))
                   ((stringp x) (upcase x))
                   (t x))))
  (mapcar #'upcase-nested
          '(("kittens" ("spam") "puppies")
            ("otters" "bunnies" ("spam" ("spam" ("spam" ("spam" "and" "spam")))) "gnu"))))

=> (("KITTENS" ("SPAM") "PUPPIES")
    ("OTTERS" "BUNNIES" ("SPAM" ("SPAM" ("SPAM" ("SPAM" "AND" "SPAM")))) "GNU"))
Improve this answer
1
  • 1
    Thank you! I benchmarked this solution and the -tree-map answer that @Tobias posted. It turns out this solution runs about twice as quickly as -tree-map.
    – Dan ♦
    Dec 19, 2018 at 13:40
4

The function -tree-map from the dash package does that:

(-tree-map #'upcase '(("kittens" "puppies")
              ("otters" "bunnies")))

(("KITTENS" "PUPPIES") ("OTTERS" "BUNNIES"))
Improve this answer
1
  • Great! Thank you. The advantage of this option is that it's a simple function call. The (minor) disadvantage is that it requires the use of a non-built in package. The bigger disadvantage is that it turns out that it's about twice as slow as the answer @phils posted, which is why I accepted that one over this one.
    – Dan ♦
    Dec 19, 2018 at 13:40
2

Following up Basils comment on the problems with recursive solutions I give here an iterative solution.

It exploits a breadth first search and therefore needs a queue. My first attempt with a depths-first search caused me some trouble with creating the structure and setting the values of the return tree.

The queue impl comes with the answer but you can also use other libraries like elib for that purpose.

The tree argument of map-tree-iter must be a list. Atoms and dotted lists are not allowed.

Note that I did not care about execution speed for this proof of concept implementation.

(defun make-queue (&rest elements)
  "Return queue structure.
A queue is a cons.
Its `cdr' is the actual data list and its `car' contains the last link
of the data list for fast tail update.
If (cdr QUEUE) is nil so is (car QUEUE)."
  (cons (last elements) elements))

(defun queue-push-back (queue &rest new-elements)
  "Append NEW-ELEMENT to QUEUE."
  (if (car queue)
      (setcar queue
          (last (setcdr (car queue) new-elements)))
    (setcar queue (last (setcdr queue new-elements)))))

(defmacro queue-front (queue)
  "Return first element of QUEUE.
The returned value is a place setable with setf."
  `(cadr ,queue))

(defmacro queue-pop-front (queue)
  "Pop the first element of QUEUE.
The return value is nil if there is no first element."
  `(prog1
       (pop (cdr ,queue))
     (unless (cdr ,queue)
       (setcar ,queue nil))))

(define-inline queue-not-empty-p (queue)
  "Return non-nil if QUEUE is not empty."
  (inline-letevals
      (queue)
    (inline-quote (car ,queue))))

(define-inline queue-to-list (queue)
  "Convert QUEUE to a list.
Note that QUEUE and the returned list
share content and structure.
If you want to modify the structure of the returned list
you should consider (copy-list (queue-to-list QUEUE))."
  (inline-letevals (queue)
    (inline-quote (cdr ,queue))))

(defun queue-empty-p (queue)
  "Return non-nil if QUEUE is empty."
  (null (queue-not-empty-p queue)))

(defun map-tree-iter (fun tree)
  "Map FUN over TREE."
  (let* ((queue (make-queue tree))
     (ret (list nil))
     (queue-ret (make-queue ret)))
    (while (queue-not-empty-p queue)
      (let ((front (queue-pop-front queue))
        (front-ret (queue-pop-front queue-ret)))
    (while front
      (cond
       ((consp (car front))
        (queue-push-back queue (car front))
        (let ((list-ret (list nil)))
          (queue-push-back queue-ret list-ret)
          (setcar front-ret list-ret)))
       ((car front)
        (setcar front-ret (funcall fun (car front))))
       )
      (setq front (cdr front))
      (when front
        (setcdr front-ret (list nil))
        (setq front-ret (cdr front-ret))))))
    ret))
Improve this answer
1
  • "Note that I did not care about execution speed" and yet you are using define-inline and defmacro. :)
    – Basil
    Dec 23, 2018 at 14:03
0

Since you have a list of lists, you have to mapcar over mapcar:

(defun mapmap (f lol)
  (mapcar (lambda (l) (mapcar f l)) lol))

(mapmap #'upcase nested)
;; => (("KITTENS" "PUPPIES") ("OTTERS" "BUNNIES"))
Improve this answer
1
  • 2
    That only works for the rigid structure of a list of lists. The expression nested list actually stands for a tree structure. Your approach does not work for a more complicated tree.
    – Tobias
    Dec 19, 2018 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.