Topic: Apply function to all numbers in lists within list

[ribarm]

Here is a little puzzle for solving in case of extra free time...

I have nested lists within list...
Assuming that the most nested element is number, I want to apply function to each of these elements,
and returning result of evaluation should be list exactly in the same form as original but with elements changed
according to applied function :

Example :
List : '((((1 3)) (2 4) (((5 7))) (6) (() 8 7 6 5 4 3 2 1))
(f (lambda ( x ) (* x 5)) '((((1 3)) (2 4) (((5 7))) (6) (() 8 7 6 5 4 3 2 1)) )
=> ((((5 15)) (10 20) (((25 35))) (30) ((40)) 40 35 30 25 20 15 10 5))

I know how to solve this one, but it's to simple :
List : '((1 2) (3 4))
Solution :
(defun f ( func lst )
  (mapcar '(lambda ( x ) (mapcar '(lambda ( y ) (func y)) x)) lst)
)

(f (lambda ( x ) (* x 5)) '((1 2) (3 4)) )
=> ((5 10) (15 20))

Ok, I have solution with help of Lee's subfunction :

Code: [Select]

(defun f ( func lst / LM:Flatten lstf lstfn lsts lstfs lstfns lstfsa lstsn pos )

  (defun LM:Flatten ( l )
    (if (atom l) (list l)
      (append (LM:Flatten (car l)) (if (cdr l) (LM:Flatten (cdr l))))
    )
  )
 
  (setq lstf (LM:Flatten lst))
  (setq lstfn (mapcar 'func lstf))
  (setq lsts (vl-prin1-to-string lst))
  (setq lstfs (mapcar '(lambda ( x ) (vl-prin1-to-string x)) lstf))
  (setq lstfns (mapcar '(lambda ( x ) (vl-prin1-to-string x)) lstfn))
  (setq lstfsa (mapcar '(lambda ( a b ) (list a b)) lstfs lstfns))
  (setq lstsn lsts)
  (setq pos 0)
  (foreach el lstfsa
    (setq lstsn (vl-string-subst (cadr el) (car el) lstsn pos))
    (setq pos (1+ (vl-string-search (cadr el) lstsn pos)))
  )
  (read lstsn)
)

So far so good :
(f (lambda ( x ) (* x 5)) '((((1 3)) (2 4) (((5 7))) (6) (() 8 7 6 5 4 3 2 1)) )
=> ((((5 15)) (10 20) (((25 35))) (30) ((40)) 40 35 30 25 20 15 10 5))

But what if elements are some other type of data instead of numbers (symbols, strings)... I want to keep them unchanged... :

Code - Auto/Visual Lisp: [Select]

1. (defun f ( func lst / LM:Flatten lstf lstfn lsts lstfs lstfns lstfsa lstsn pos )
2.  
3.   (defun LM:Flatten ( l )
4.     (if (atom l) (list l)
5.       (append (LM:Flatten (car l)) (if (cdr l) (LM:Flatten (cdr l))))
6.     )
7.   )
8.  
9.   (setq lstf (LM:Flatten lst))
10.   (setq lstfn (mapcar '(lambda ( x ) (if (numberp x) (func x) x)) lstf))
11.   (setq lsts (vl-prin1-to-string lst))
12.   (setq lstfs (mapcar '(lambda ( x ) (vl-prin1-to-string x)) lstf))
13.   (setq lstfns (mapcar '(lambda ( x ) (vl-prin1-to-string x)) lstfn))
14.   (setq lstfsa (mapcar '(lambda ( a b ) (list a b)) lstfs lstfns))
15.   (setq lstsn lsts)
16.   (setq pos 0)
17.   (foreach el lstfsa
18.     (setq lstsn (vl-string-subst (cadr el) (car el) lstsn pos))
19.     (setq pos (1+ (vl-string-search (cadr el) lstsn pos)))
20.   )
21.   (read lstsn)
22. )
23.  

(f (lambda ( x ) (* x 5)) '((((1 3)) (2 4) (((5 7))) (6) (() 8 7 6 5 "A" "B" C D T nil ("E") ('F) 'G "Marko")) )
=> ((((5 15)) (10 20) (((25 35))) (30) ((40)) 40 35 30 25 "A" "B" C D T nil ("E") ((QUOTE F)) (QUOTE G) "Marko"))

I wonder have I missed something, or is there any better way to achieve the same result...

M.R.

[irneb]

Why not just go with something like this

Code - Auto/Visual Lisp: [Select]

1. (defun map-nested (func lst)
2.   (mapcar (function (lambda (item)
3.                       (if (atom item)
4.                         (apply func (list item))
5.                         (map-nested func item))))
6.           lst))

E.g. incrementing each item in the list and all nested lists

Code: [Select]

_$ (map-nested '1+ '((((1 3)) (2 4) (((5 7))) (6) ((8)) 8 7 6 5 4 3 2 1)))
((((2 4)) (3 5) (((6 8))) (7) ((9)) 9 8 7 6 5 4 3 2))If elements are some other type of data, then the function you send to mapcar / this map-nested should check for such eventuality. Say you've got a situation where you want all integers incremented by 5, all strings changed to uppercase, and all reals left as is:

Code: [Select]

_$ (map-nested '(lambda (item) (cond ((= (type item) 'Str) (strcase item))
                                  ((= (type item) 'Int) (+ item 5))
                                  (t item)))
  '((((1 "test")) (2 4) (((5.0 7))) (6) ((8)) 8 7 6 5 4 3 2 1)))
((((6 "TEST")) (7 9) (((5.0 12))) (11) ((13)) 13 12 11 10 9 8 7 6))

[Lee Mac]

Or, to account for dotted pairs:

Code - Auto/Visual Lisp: [Select]

1. (defun fnest ( f l )
2.     (cond ((null l) l)
3.           ((atom l) ((eval f) l))
4.           ((cons (fnest f (car l)) (fnest f (cdr l))))
5.     )
6. )

Code - Auto/Visual Lisp: [Select]

1. _$ (fnest '1+ '((((1 3)) (2 . 4) (((5 . 7))) (6) ((8)) 8 7 6 5 4 3 2 1)))
2. ((((2 4)) (3 . 5) (((6 . 8))) (7) ((9)) 9 8 7 6 5 4 3 2))

[irneb]

Or, to account for dotted pairs:

That's a good point, just one question: Why do you skip nil values? I was thinking of this, but figured, since mapcar doesn't do so, why should others?

My 2nd variation. Uses the eval instead of apply (like yours), but also uses pre-made defuns instead of a lambda each time the recursion happens (should be more efficient on deeply nested lists):

Code - Auto/Visual Lisp: [Select]

1. (defun map-nested1 (func lst / runMap doItem)
2.   (defun runMap (lst) (mapcar 'doItem lst))
3.   (defun doItem (item)
4.     (cond ((atom item) ((eval func) item))
5.           ((cdr item) (cons (doItem (car item)) (doItem (cdr item))))
6.           ((runMap item))))
7.   (runMap lst))

Actually Edit:

Code - Auto/Visual Lisp: [Select]

1. (defun map-nested2 (func lst / runMap doItem)
2.   (defun runMap (lst) (mapcar 'doItem lst))
3.   (defun doItem (item)
4.     (cond ((atom item) ((eval func) item))
5.           ((and (cdr item) (atom (cdr item))) (cons (doItem (car item)) (doItem (cdr item))))
6.           ((runMap item))))
7.   (runMap lst))

Though I'm not sure if it's that much use to try and "force" the mapcar idea. Will need to benchmark to check if it's actually faster than simply using the more succinct cons-only method of your fnest function.

Edit: renamed to differenciate versions

[irneb]

Here's what I mean about the nil values

Code - Auto/Visual Lisp: [Select]

1. (defun fnest2 (f l)
2.   (cond ((atom l) ((eval f) l))
3.         ((cdr l) (cons (fnest2 f (car l)) (fnest2 f (cdr l))))
4.         ((cons (fnest2 f (car l)) nil))))

[irneb]

Code: [Select]

_$ (quickbench '((map-nested1 f l) (map-nested2 f l) (fnest f l) (fnest2 f l)))
Benchmarking .... done for 8192 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(FNEST2 F L)                                  8192      1264      1264      1.30
(FNEST F L)                                   8192      1435      1435      1.14
(MAP-NESTED2 F L)                             8192      1544      1544      1.06
(MAP-NESTED1 F L)                             8192      1638      1638      1.00
--------------------------------------------------------------------------------Seems my idea of forcing mapcar improves on my defun, but the overhead of making and calling extra functions is less efficient (should have figured this on my own  ).

What is surprising is the fnest2. It's not as if it does much different from your fnest

[irneb]

What is surprising is the fnest2. It's not as if it does much different from your fnest

Ah! Just realized: kind of logical if you think about it.

Yours does an extra recursion at the end of each nested list - passing a nil value. The fnest2, doesn't need the extra recursion to stop. That must be the reason it's slightly faster. I definitely don't thunk a call to null should be much slower than a call to cdr.

[roy_043]

@ irneb: Try:
(mapcar '1+ nil)
(fnest2 '1+ nil)

[irneb]

Yes, exactly. But also:

Code: [Select]

_$ (fnest '1+ nil)
nil
_$ (map-nested1 '1+ nil)
nil
_$ (mapcar 'not '(t nil t nil))
(nil T nil T)
_$ (fnest 'not '(t nil t nil))
(nil nil nil nil)
_$ (fnest2 'not '(t nil t nil))
(nil T nil T)
_$ (mapcar '1+ '(1 2 nil 4))
; error: bad argument type: numberp: nil
_$ (fnest '1+ '(1 2 nil 4))
(2 3 nil 5)
_$ (fnest2 '1+ '(1 2 nil 4))
; error: bad argument type: numberp: nil
_$ (map-nested1 '1+ '(1 2 nil 4))
; error: bad argument type: numberp: nil
_$ (map-nested1 'not '(t nil t nil))
(nil T nil T)
_$ (map-nested1 'not nil)
nilSo, which are the most consistent as compared to mapcar?

[roy_043]

So, which are the most consistent as compared to mapcar?

That is a very good point. The problem is of course that nil is inconsistent since it is both an atom and a list.
But...
Since I want this:
(fnest '1+ nil) => nil
And...
Since the function 'expects' nested lists,
I think interpreting nil as an empty list makes more sense.

[irneb]

The point I'm trying to make is that the only ones which work the exact same way as mapcar does is the map-nested1 & 2. Because they actually use mapcar instead of rolling their own iterations.

Also note, there's one further issue with fnest / fnest2: Recursion stack space is used more. The map-nested only recurses into the depth of the list, mapcar'ing siblings instead of cdr'ing and then recursing. What this means is in AutoLisp you'll error if there's more than (around) 15000 items in the entire nested list structure with the fnest's, but erroring only when the structure is around 15000 levels deep with the map-nested.

I'd say the fnest's are good if your structure is something like a binary tree or not enormous. Otherwise the map-nested's is the safest to use.

The only way to avoid this would be to go with a strictly iterative approach, i.e. no recursion. But that is a bit complex seeing as you need to recreate the list in the same structure as it was input - this is where recursion is 100's of times easier than iteration.

[roy_043]

On a fundamental level it is strange that your map-nested functions treat the 'top-level' nil as a list and any nested nil as an atom. And a list with 15000 items or levels seems unlikely as input for a map-nested function.

Note:
(map-nested2 '1+ '(1 2 . 3 )) => (2 3)
(fnest '1+ '(1 2 . 3 )) => (2 3 . 4)

[irneb]

On a fundamental level it is strange that your map-nested functions treat the 'top-level' nil as a list and any nested nil as an atom.

That's due to them working much more in line with the same way as mapcar does. In fact that is exactly what mapcar does. But the last 2 variants have moved away from mapcar's method in order to accommodate the dotted pairs, which mapcar disallows.

And a list with 15000 items or levels seems unlikely as input for a map-nested function.

True chances of that happening is extremely slim in theory, but I've run into them and I've seen some of them on these forums. So they're not something which "never" happens. I'm just stating you should keep note that they could happen.

Note:
(map-nested2 '1+ '(1 2 . 3 )) => (2 3)
(fnest '1+ '(1 2 . 3 )) => (2 3 . 4)

Yes, that is a bit confusing. In that sense my original map-nested is probably much closer to mapcar:

Code: [Select]

Command: (mapcar '1+ '(1 2 . 3))
; error: bad list: 3

[reltro]

Aloha....

I tried to build a iterative method to solve the problem, but at the Moment the Routine can not handle dottedPairs.
Maybe someone have an idea to include them.

Here the routine:

Code: [Select]

(defun Iter_fNest (Expr Lst / Stack Result Dim)
   (while (or Lst Stack)
      (cond
         ((null Lst)
            (setq Lst (car Stack))
            (setq Stack (cdr Stack))
            (setq Result
               (cons
                  (   (lambda ( / O)
                        (repeat (car Dim)
                           (setq O (cons (car Result) O))
                           (setq Result (cdr Result))
                        )
                        (setq Dim (cdr Dim))
                        O
                     )
                  )
                  Result
               )
            )
         )
         ((atom (car Lst))
            (setq Result (cons ((eval Expr) (car Lst)) Result))
            (setq Lst (cdr Lst))
         )
         ((listp (car Lst))
            (setq Stack (cons (cdr Lst) Stack))
            (setq Lst (car Lst))
            (setq Dim (cons (length Lst) Dim))
         )
      )
   )
   (reverse Result)
)


Code: [Select]

(Iter_Fnest '(lambda (a / ) (print a) (1+ a)) '((1 2) 3 4 5 (6 (7 (8) 9) 10 (11 (12 (13 14) 15) 16) 17) 18 (19 20)))


Its not as nice as the recursiv one, but it seems to work...

Greets

[reltro]

Irneb,
can u test this with ur bench-thing?

Im wondering if it makes any difference:
I picked up fnest2 and have made the recursion 'anonym'... the recursion is calling a compiled lambda-expr...

Code: [Select]

(   (lambda (fnest2 / )
      (eval (list 'defun 'anon_fnest2 '(f l / ) (list fnest2 fnest2 'f 'l)))
   )
   (lambda (fnest2 f l / )
      (cond ((atom l) ((eval f) l))
         ((cdr l) (cons (fnest2 fnest2 f (car l)) (fnest2 fnest2 f (cdr l))))
         ((cons (fnest2 fnest2 f (car l)) nil))
      )
   )
)
(anon_fnest2 '1+ '((1 2) (3 . 4) (5 6 (7 8 ((((9)) 10 11))))))

Greets Reltro

[irneb]

Irneb,
can u test this with ur bench-thing?

Im wondering if it makes any difference:
I picked up fnest2 and have made the recursion 'anonym'... the recursion is calling a compiled lambda-expr...

Code: [Select]

(   (lambda (fnest2 / )
      (eval (list 'defun 'anon_fnest2 '(f l / ) (list fnest2 fnest2 'f 'l)))
   )
   (lambda (fnest2 f l / )
      (cond ((atom l) ((eval f) l))
         ((cdr l) (cons (fnest2 fnest2 f (car l)) (fnest2 fnest2 f (cdr l))))
         ((cons (fnest2 fnest2 f (car l)) nil))
      )
   )
)
(anon_fnest2 '1+ '((1 2) (3 . 4) (5 6 (7 8 ((((9)) 10 11))))))

Greets Reltro

If you want you can use it yourself. It's one I derived from this one: http://www.theswamp.org/lilly_pond/mp/lisp/benchmark.txt
I changed it so it tries to never take longer than 1 sec per item to bench, because I've found many a poorly thought-out algorithm might take ages to complete a benchmark. Attached is my version.

As for your code, I'm not sure you need to do that anon_fnest2 inside of a lambda. It doesn't actually do anything different than doing the defun normally. Remember AutoLisp has a Dynamic Symbol Scoping, which means that the anon_fnest is a normal defun after the lambda is run. I'll have to check what you've actually done inside though.

As for the iterative fnest, good code! I knew something like a stack/queue would be needed for it to work. Similar to the breadth-first traversal for the tree structure.
Though it's a lot slower than the others. Test code

Code - Auto/Visual Lisp: [Select]

1. (setq lst  '((((1 "test")) (2 4) (((5.0 7))) (6) (() 8 nil 6 5 nil 3 2 1)))
2. (defun test (n) (cond ((member (type n) '(Int Real)) (1+ n)) (n)))

And the result

Code: [Select]

_$ (quickbench '((fNest 'test lst) (fNest2 'test lst) (Iter_fNest 'test lst) (map-nested 'test lst) (map-nested1 'test lst) (map-nested2 'test lst)))
Benchmarking ...... done for 8192 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(FNEST2 (QUOTE TEST) LST)                     8192      1265      1265      1.70
(FNEST (QUOTE TEST) LST)                      8192      1341      1341      1.60
(MAP-NESTED2 (QUOTE TEST) LST)                8192      1482      1482      1.45
(MAP-NESTED1 (QUOTE TEST) LST)                8192      1623      1623      1.33
(MAP-NESTED (QUOTE TEST) LST)                 8192      1716      1716      1.25
(ITER_FNEST (QUOTE TEST) LST)                 4096      1076      2152      1.00
--------------------------------------------------------------------------------It does work on nils inside the list, but not dotted pairs. So it's comparable to my first map-nested function as well as the built-in mapcar. But it's not comparable to Lee's fnest and those which were derived from it. I suppose it depends on what you want to achieve from this code:

• If you want a nested version of mapcar, then map-nested is fine (though recursive) or iter_fnest is iterative (though slower).
• If you want to have an exact structure as the input, only having each atom run through your function, then the others do come closer. Especially the fnest2. FNest does handle dotted paiirs, but ignores all nil items, the map-nested1 & 2 seem to still have issues with dotted pairs.

[irneb]

As for the anon_fnest2, it does show you've got a lot of understanding about lambda and the dynamic scope of AutoLisp. Quite tricky code on an advanced level.

Though it has no benefit over the straight forward fnest2 - actually slightly slower:

Code: [Select]

_$ (quickbench '((fNest 'test lst) (fNest2 'test lst) (anon_fNest2 'test lst)))
Benchmarking ... done for 8192 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(FNEST2 (QUOTE TEST) LST)                     8192      1294      1294      1.05
(ANON_FNEST2 (QUOTE TEST) LST)                8192      1327      1327      1.02
(FNEST (QUOTE TEST) LST)                      8192      1358      1358      1.00
--------------------------------------------------------------------------------AFAICT it's needlessly complicating the code. What was your reasoning in generating a labda function which generates your defun function to use your generated lambda function which then calls itself using a parameter passed into itself so it has a reference to itself? See how convoluted it even sounds?

And even if I use your method and generate an optimized version using the function optimization on a lambda like this:

Code - Auto/Visual Lisp: [Select]

1. ((lambda (fnest2 / ) (eval (list 'defun 'anon_fnest2a '(f l / ) (list fnest2 fnest2 'f 'l))))
2.   (eval (function (lambda (fnest2 f l / )
3.                     (cond ((atom l) ((eval f) l))
4.                           ((cdr l) (cons (fnest2 fnest2 f (car l)) (fnest2 fnest2 f (cdr l))))
5.                           ((cons (fnest2 fnest2 f (car l)) nil)))))))

It's not enough to surpass the straight-forward fnest2 defun itself:

Code: [Select]

_$ (quickbench '((fnest 'test lst) (anon_fNest2a 'test lst) (fNest2 'test lst) (anon_fNest2 'test lst)))
Benchmarking .... done for 8192 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(FNEST2 (QUOTE TEST) LST)                     8192      1294      1294      1.05
(ANON_FNEST2A (QUOTE TEST) LST)               8192      1311      1311      1.04
(FNEST (QUOTE TEST) LST)                      8192      1327      1327      1.02
(ANON_FNEST2 (QUOTE TEST) LST)                8192      1358      1358      1.00
--------------------------------------------------------------------------------It might have improved something on the reciprocal recursion of the map-nested2 if the definition was the slowing factor. But I've even tested that version using premade defuns for the runMap & doItem nested functions. It makes no difference at all

Code - Auto/Visual Lisp: [Select]

1. (defun runMap (lst) (mapcar 'doItem lst))
2. (defun doItem (item)
3.   (cond ((atom item) ((eval func) item))
4.         ((and (cdr item) (atom (cdr item))) (cons (doItem (car item)) (doItem (cdr item))))
5.         ((runMap item))))
6.  
7. (defun map-nested3 (func lst / )
8.   (runMap lst))

It's actually slower

Code: [Select]

_$ (quickbench '((map-nested2 'test lst) (map-nested3 'test lst)))
Benchmarking .. done for 8192 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(MAP-NESTED2 (QUOTE TEST) LST)                8192      1434      1434      1.11
(MAP-NESTED3 (QUOTE TEST) LST)                8192      1590      1590      1.00
--------------------------------------------------------------------------------So you see the major time taken seems to be the overhead of calling the function, not the time taken to generate the function.

[reltro]

Hey...

Here is  a complete iterative solution. handles all sort of data I tested since now
But now, its a bit slower, because each nested List hast to run trough twice.

Code: [Select]

(defun Iter_fNest (Expr Lst / Stack Result Dim)
   (while (or Lst Stack)
      (cond
         ((null Lst)
            (setq Lst (car Stack))
            (setq Stack (cdr Stack))
            (setq Result
               (cons
                  (   (lambda ( / O)
                        (repeat (caar Dim)
                           (setq O (cons (car Result) O))
                           (setq Result (cdr Result))
                        )
                        (if (cdar Dim)
                           (apply 'vl-list* O)
                           O
                        )
                     )
                  )
                  Result
               )
            )
            (setq Dim (cdr Dim))
         )
         ((atom (car Lst))
            (setq Result (cons ((eval Expr) (car Lst)) Result))
            (setq Lst (cdr Lst))
         )
         ('T
            (setq Stack (cons (cdr Lst) Stack))
            (apply
               '(lambda (L D / )
                  (setq Lst L)
                  (setq Dim (cons (cons (length Lst) D) Dim))
               )
               (   (lambda (a / lst s)
                     (setq s a)
                     (while (not (atom (cdr a)))
                        (setq lst (cons (car a) lst))
                        (setq a   (cdr a))
                     )
                     (cond
                        ((cdr a)
                           (list
                              (setq lst (reverse (vl-list* (cdr a) (car a) lst)))
                              'dP
                           )
                        )
                        ('T (list s nil))
                     )
                  )
                  (car Lst)
               )
            )
         )
      )
   )
   (reverse Result)
)


Code: [Select]

(iter_fnest '1+ '(((1 (3 . 4) 5) . 3) (1 . 20) 2 3 (1 2 (3 4) . 5) 4))
I think it was foreseeable that the iterative method is slower then the recursiv one

greets reltro

[reltro]

AFAICT it's needlessly complicating the code. What was your reasoning in generating a labda function which generates your defun function to use your generated lambda function which then calls itself using a parameter passed into itself so it has a reference to itself? See how convoluted it even sounds?

I know, its a complicated thinking, but i don't think its needless. In this special case its really needless .
I borned this idea when I tought about to build a function wich can also store some data, like an 'Object' in OOP-language.
(if u are interessted in, I can send u some code )
normally I don't name the anon-recursion with a 'defun-statment...

to build them in the Runtime I use this one:

Code: [Select]

(setq anonRec
   (   (lambda (rec / )
         (eval
            (list 'lambda '(expr / in)
               (list rec rec
                  'expr
                  '((lambda (a b / ) (if a (reverse (cdr a)) b))
                     (member '/ (reverse (cdr (cadr expr))))
                     (cdr (cadr expr))
                  )
               )
            )
         )
      )
      (eval
         (function
            (lambda (rec expr in / )
               (eval
                  (eval
                     (list 'function
                        (list 'lambda in
                           (vl-list*
                              expr
                              (list rec rec (list 'quote expr) (list 'quote in))
                              in
                           )
                        )
                     )
                  )
               )
            )
         )
      )
   )
)

Use it like this:

Code: [Select]

(  (anonRec
      '(lambda (ME a / c)
        (print a)
        (if (> a 0)
          (ME (1- a))
        )
      )
   )
   200
)

Greets reltro

@Irneb ... PS.: Thanks for the Quickbench.lsp

[irneb]

Yep, it could be a good way in some instances. But for this particular I don't think it needs to be done like that. Nothing wrong with it, I just can't see (in this case) that it brings anything better than a much simpler method.

Good one with the iterative! You're correct since for this (and other nested structures like trees & networks) it's usually simpler and quicker to use recursion. The problem with iteration in these cases is that you always need one or more temporary lists which grows and shrinks constantly as you run through different levels, this itself takes time. Then as you've found, sometimes you need to iterate over the entire structure twice if you don't want to recurse. You'll see nearly all samples of coding pertaining to trees are using some sort of recursion, there are very few iterative samples (even through google) because it's so much more complex and usually slower AND usually uses a lot more RAM.

That's not to say iterative is always like this, it's just the "nested" which causes this issue. In general recursion tends to be slower than iterative if you only run through a normal list, and could even use more ram as well. E.g. testing my own rolled foreach loop doing it through recursion and another through while:

Code - Auto/Visual Lisp: [Select]

1. (defun foreach-recursive (var lst code)
2.   (if (set var (car lst))
3.     (progn (eval code)
4.            (foreach-recursive var (cdr lst) code))))
5.  
6. (defun foreach-iterative (var lst code)
7.   (while (set var (car lst))
8.     (eval code)
9.     (setq lst (cdr lst))))

The benchmark

Code: [Select]

$ (setq test '(1 2 3 4 5 6 7 8 9))
(1 2 3 4 5 6 7 8 9)
_$ (quickbench '((foreach-recursive 'x test '(1+ x)) (foreach-iterative 'x test '(1+ x)) (foreach x test (1+ x))))
Benchmarking ... done for 16384 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(FOREACH X TEST (1+ X))                      16384      1187      1187      5.20
(FOREACH-ITERATIVE (QUOTE X) TEST (Q...)      4096      1264      5056      1.22
(FOREACH-RECURSIVE (QUOTE X) TEST (Q...)      4096      1543      6172      1.00
--------------------------------------------------------------------------------Of course using the built-in foreach is a lot quicker as it's fully compiled (probably written in C as well).

Anyhoo! You're welcome to the QuickBench. It's not perfect though, there are some others which are slightly more accurate. I just use it as the 1st benchmark to weed out the really slow code before I use one of the other benchmark routines to figure out exactly which code is fractionally faster than the other. Though more often than not I don't bother too much if there's only a 1% (or so) difference.