带子项的嵌套列表元素的Lisp位置 [英] Lisp position of nested list element with children

问题描述

说我们有以下列表：

(A B C D)

我们可以找到 C 的索引，其中包括：

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

该函数将产生 NIL 。

我们如何有效地定位嵌套列表中元素的 nth 位置，尤其是当原子为位于子列表中，例如 y ？

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?

－－－－－

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

推荐答案

在树的某个深层中发现元素时，位置尚不清楚

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

一种可能是返回第n个索引

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

另一种可能性是将索引的概念推广到树结构，例如通过返回一个列表，其中位置j处的元素是该元素的位置或包含其级别j的列表。例如：

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.

这篇关于带子项的嵌套列表元素的Lisp位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！