0

Say we have the following list: 

(A B C D)

We can find the index of C with: 

(position 'C '(A B C D))

If, however one of the list elements is nested with its own children: 

(position 'B '(A (B 1 2 (3 x y z)) C D))

The function would yield NIL.

How do we effectively locate the nth position of elements within a nested list like this, especially if the atom is located within a sub-list like, for example, y?

－－－－－

Here's my attempt thus far:

(setq lst (A (B 1 2 (3 x y z)) C D))

(defun top-level-elm (lst)
  (loop for x from 0 to (- (length lst) 1)
     collect (car (nth x lst))))

(defun elm-id (elm lst)
  (position elm (top-level-elm lst)))

(defun child-of (elm lst)
  (cdr (nth (elm-id elm lst) lst)))

(defun child-id (lst)
(loop for x from 0 to (- (length lst) 1)
     collect (child-of (nth x (top-level-elm lst)))))
Sati
  • 716
  • 6
  • 27
  • 2
    There is no built-in function to do it. You would need to write one. – Rainer Joswig Oct 30 '19 at 04:48
  • 1
    What should be the result in case of a inner object, like y in the example above? There could be several different possibilities. – Renzo Oct 30 '19 at 06:06
  • Hmm... maybe a cons cell containing its `id` within the sublist and the parent in that list. So, for the example of `y`, it will be: `(2·3)` – Sati Oct 30 '19 at 06:19

1 Answers1

1

It is not really clear what should be the position when the element is found in some deep level of the tree.

One possibility is to return the index of the n-th leaf corresponding to the element.

In this case, for instance, given a flatten function, you could write a function like this:

(defun my-position (elm tree)
  (position elm (flatten tree))

Another possibility is to generalize the concept of index to a tree structure, for instance by returning a list in which the element in position j is the position of the element or the list containing it at level j. For instance:

(my-position 'A '(A (B 1 2 (3 x y z)) C D)) => (0)
(my-position 'B '(A (B 1 2 (3 x y z)) C D)) => (1 0)
(my-position 'y '(A (B 1 2 (3 x y z)) C D)) => (1 3 2)

In this case, a recursive function could be:

(defun my-position (elm tree &optional (start 0))
  "find the generalized position of elm inside tree.
   Parameters: elm - element to be found
               tree - a list of atoms and lists in which to search the element
               start - the tentative position"      
  (cond ((null tree) nil)       ; element not present => nil
        ((atom (first tree))    ; if the first element is an atom, then
         (if (eql elm (first tree)) ; if equal to element, found
             (list start)           ; return position start
             ;; otherwise, recur on rest of list incrementing the tentative position
             (my-position elm (rest tree) (1+ start))))
        ;; otherwise, the first element is a list,
        ;; try to find it inside, with a recursive call
        (t (let ((pos (my-position elm (first tree) 0)))
             (if pos ; if not nil the element has been found
                 (cons start pos) ; return the current position followed by the position inside the list
                 ; otherwise recur on rest of list incrementing the tentative position
                 (my-position elm (rest tree) (1+ start)))))))

Final note: to write a more “professional” function one should add the keyword parameters of the predefined position function.

Renzo
  • 26,848
  • 5
  • 49
  • 61
  • Cool! Could you explain your code a bit? I cannot really follow the conditionals. – Sati Oct 30 '19 at 09:11
  • @Sati, I modified the answer. – Renzo Oct 30 '19 at 09:21
  • Thank you! The explanation is quite clear. One question: What does `t` and `pos` do in `(t (let ((pos (my-position elm (first tree) 0)))`? You are setting the position of the first element in the list to `0` with the `let`, if I am not wrong? – Sati Oct 30 '19 at 09:30
  • `t` is the third condition of the outer `cond`. The local variable `pos` will contain, if found, the generalized position of the element if it is present in the list `(first tree)`. Note that, since we are “entering” in that list from the beginning, we need to reset the tentative position at 0. What I call “tentative position” is in effect the index of the element of the list that will be checked next, and that, if the check is ok, is the value returned by the function. – Renzo Oct 30 '19 at 09:35
  • Is `t` a condition that checks if what follows is _true_? What has `t`got to do with entering a list and matching `elm` with an item inside that list? – Sati Oct 30 '19 at 09:40
  • 1
    No, look at the external `cond`, it has three branches: `(cond ((null tree) ... return nil ...) ((atom (first tree)) ... manage the list when its first element is not a list ...) (t (..otherwise...) ... manage the list when its first element is a list ..))`. In other words, `t` here means: when the first two cases are false, and corresponds to the "otherwise" (or final else in a chain of if-then-elsif...) in other languages. – Renzo Oct 30 '19 at 09:46
  • Oh, I see! So `t` always comes up on the last branch of a `cond` loop? – Sati Oct 30 '19 at 10:02
  • 1
    Very often, yes. Unless all the other conditions cover all the possible cases. – Renzo Oct 30 '19 at 10:17