Re: Help with recursive destructive function

[Michael Heerdegen]

Clément Pit-Claudel <address@hidden> writes:

>     (defun deep-edit (f data)
>       (let ((cur `(car setcar ,data))
>             (stack `((cdr setcdr ,data))))
>         (while (or cur stack)
>           (pcase-let* ((`(,getter ,setter ,cell) cur)
>                        (subtree (funcall getter cell)))
>             (funcall setter cell (funcall f subtree))
>             (cond
>              ((consp subtree)
>               (push `(cdr setcdr ,subtree) stack)
>               (setq cur `(car setcar ,subtree)))
>              (t (setq cur (pop stack))))))))

Well done!

A random example and two corner cases seem to work ok:

(defun edit-elt (thing)
  (if (stringp thing) (upcase thing) thing))

(let ((tree '("c" (2 ("d" . 3)) (4 . "e") "f" (("g" . "h")))))
  (deep-edit #'edit-elt tree)
  tree)
==>
 ("C"
   (2
    ("D" . 3))
   (4 . "E")
   "F"
   (("G" . "H")))

(let ((huge-list (number-sequence 1 100000)))
  (setcdr (last huge-list) (cons "a" nil))
  (deep-edit #'edit-elt huge-list))
|-- no crash

(let ((deeply-nested-list (list nil)))
  (let ((pointer deeply-nested-list))
    (dotimes (_ 100000)
      (setf (car pointer) (list nil)
            pointer (car pointer)))
    (setf (car pointer) "a"))
  (deep-edit #'edit-elt deeply-nested-list))
|- no crash


Michael.