时间戳

首页 > 解决方案 > 带有子元素的嵌套列表元素的 Lisp 位置

tree - 带有子元素的嵌套列表元素的 Lisp 位置

问题描述

假设我们有以下列表：

(A B C D)

我们可以找到Cwith 的索引：

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

但是，如果列表元素之一与其自己的子元素嵌套：

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

该函数将产生NIL.

我们如何在这样nth的嵌套列表中有效地定位元素的位置，特别是如果原子位于子列表中，例如，y？

－－－－－</p>

到目前为止，这是我的尝试：

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

标签： treecommon-lispindexof

解决方案

当元素在树的某个深层中找到时，它的位置应该是什么并不是很清楚。

一种可能性是返回与元素对应的第 n 个叶子的索引。

在这种情况下，例如，给定一个flatten 函数，您可以编写如下函数：

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

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

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

在这种情况下，递归函数可以是：

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

最后说明：要编写一个更“专业”的函数，应该添加预定义position函数的关键字参数。

推荐阅读