list - 如何创建 n 维列表？

Question

作为初学者，我在嘴唇上苦苦挣扎，在我的程序中我有一个列表:
(((NIL (B) (C) (B)) (A)) (E) (G))

但我想要构建的是 n 维列表(在本例中为 3-dim):

((B C B)(A)(E G))

我试过将列表展平，但似乎不正确。我将不胜感激任何帮助。

Answer 1

由于您还没有真正给出您的程序要做什么的规范，这里有一些东西可以将您拥有的结构变成您想要的结构，假设其他东西正在为您提供这种结构。

你的结构是一个缺点，如果没有更多的结构，它的汽车要么是空的，要么是一个结构。单元素列表的结构列表的cdr，我们想要那些元素。

我将该结构称为 BLOB-TREE，每个 CDR 都是一个 BLOB。

(defun blob-to-list (blob)
  ;; a blob is a list of single-element lists, and we want the elements
  (mapcar (lambda (e)
            (assert (and (listp e) (null (rest e))))
            (first e))
          blob))

(defun blob-tree-to-list (blobs)
  ;; BLOB-TREE is some horrible tree: what we need to do is split it into
  ;; its car & cdr, and then convert the cdr to a list with
  ;; blob-to-list, then recurse on the car, until we get a null car.
  (labels ((extract-blobs (remains accum)
             (etypecase remains
               (null accum)
               (cons
                (extract-blobs (car remains) (cons (blob-to-list (cdr remains))
                                                   accum))))))
    (extract-blobs blobs '())))

现在

> (blob-tree-to-list '(((NIL (B) (C) (B)) (A)) (E) (G)))
((b c b) (a) (e g))

我很怀疑这实际上是您想要做的。

---

作为检查，我编写了一个函数，它采用您想要的形式的列表并将其转换为 blob 树。您可以使用它来检查是否正确往返。

(defun list-to-blob-tree (l)
  (labels ((list-to-blob (es)
             (mapcar #'list es))
           (build-blob-tree (tail accum)
             (if (null tail)
                 accum
               (build-blob-tree (rest tail)
                                (cons accum (list-to-blob (first tail)))))))
    (build-blob-tree l '())))

---

如果你真的想处理这样的事情(在现实生活中，你有时不得不这样做)，一个好的方法是编写一堆访问器函数，让你抽象出你一直在使用的糟糕数据结构给出。

在这种情况下，我们可以编写函数来处理 blob:

;;; Blobs are lists are lists where each element is wrapped in a
;;; single-element list

(defun blob->element-list (blob)
  ;; a blob is a list of single-element lists, and we want the elements
  (mapcar (lambda (e)
            (assert (and (listp e) (null (rest e))))
            (first e))
          blob))

(defun element-list->blob (list)
  ;; turn a list into a blob
  (mapcar #'list list))

还有一组处理 blob 树的函数，(事实证明)它们只是用他们的汽车和 cdr 交换的列表:

;;; Blob trees are lists, built backwards
;;;

(deftype blob-tree ()
  '(or cons null))

(defconstant null-blob-tree nil)

(defun blob-tree-car (blob-tree)
  (cdr blob-tree))

(defun blob-tree-cdr (blob-tree)
  (car blob-tree))

(defun blob-tree-cons (car cdr)
  (cons cdr car))

(defun blob-tree-null-p (blob-tree)
  (null blob-tree))

在这两种情况下，我只编写了我需要的功能:例如，有读者但没有作家。

现在我们可以根据这些抽象来编写我们需要的函数:

(defun blob-tree->element-list (blob-tree)
  (labels ((extract-blobs (tree accum)
             (assert (typep tree 'blob-tree))
             (if (blob-tree-null-p tree)
                 accum
               (extract-blobs (blob-tree-cdr tree)
                              (cons (blob->element-list (blob-tree-car tree))
                                    accum)))))
    (extract-blobs blob-tree '())))

(defun element-list->blob-tree (el)
  (labels ((build-blob-tree (elt accum)
             (if (null elt)
                 accum
               (build-blob-tree (rest elt)
                                (blob-tree-cons
                                 (element-list->blob (first elt))
                                 accum)))))
    (build-blob-tree el null-blob-tree)))

这意味着如果表示发生变化，这两个略显毛茸茸的函数不会。