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