Map function onto nested list?

Question

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?

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 '18 at 13:24
@Basil: interesting point. Do you know of an iterative solution to avoid recursion? — Dan, Dec 19 '18 at 13:42

score 5 · Accepted Answer · answered Dec 19 '18 at 12:40

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"))

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 '18 at 13:40

score 4 · Answer 2 · answered Dec 19 '18 at 12:42

4

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

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

(("KITTENS" "PUPPIES") ("OTTERS" "BUNNIES"))

answered Dec 19 '18 at 12:42

Tobias

32,569
1
34
75

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 '18 at 13:40

Tobias · Answer 3 · 2018-12-23T13:18:15.873

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))

"Note that I did not care about execution speed" and yet you are using `define-inline` and `defmacro`. :) — Basil, Dec 23 '18 at 14:03

score 0 · Answer 4 · answered Dec 19 '18 at 20:45

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"))

answered Dec 19 '18 at 20:45

user3414663

235
1
8

2

That only works for the rigid structure of a list of lists. The expression [nested list](https://en.wikipedia.org/wiki/Nested_set_model) actually stands for a tree structure. Your approach does not work for a more complicated tree. – Tobias Dec 19 '18 at 21:02

Map function onto nested list?

4 Answers4