在Lisp中展平树结构 [英] Flattening a tree structure in Lisp

问题描述

我一直在努力压扁树形结构.我通过将每个原子符号与树中的其余原子符号进行比较来递归地执行此操作，但是我的一个朋友建议使用以下代码，我认为它看起来更干净.我只是不明白这行:

I was struggling with flattening a tree structure. I was doing it recursively by comparing each atomic symbol to the rest in the tree but, a friend of mine suggested the following code which I think looks cleaner. I just don't understand the line:

((atom tree)(list tree))

我了解他们每个人各自做的事情，我也知道下面的循环需要一个列表，否则会导致错误，我怀疑这有很多原因，因为如果我们将原子转换为一个列表，则会将其变成一个列表返回true.但是我仍然不觉得我完全理解代码.

I understand what each of them do individually, I also know that the loop below takes a list or it causes an error, which I suspect has a lot to due with the reason we're turning the symbol into a list if atom returns true. But I still don't feel like I fully understand the code.

(defun flatten (tree)
(cond ((null tree)
     nil
     )
    ((atom tree)(list tree))
    (t
     (loop for a in tree appending (flatten a)))))

如果有人可以节省时间，那么解释会很棒吗?谢谢！

An explanation would terrific if anyone could spare the time? Thanks!

推荐答案

代码格式不正确.在问题的第一部分，我们还不清楚为什么

The code is rather poorly formatted. In the first part of your question, it's not at all clear why

((atom tree) (list tree))

将出现在 any 通用Lisp代码中，因为它看起来像是试图调用(atom tree)，取回函数并使用(list tree)调用该函数的尝试.在上下文中，使用正确的格式会更清楚:

would appear in any Common Lisp code, since it looks like an attempt to call (atom tree), get a function back, and call that function with (list tree). In context, with proper formatting, it's clearer:

(defun flatten (tree)
  (cond 
   ((null tree) nil)
   ((atom tree)(list tree))
   (t (loop for a in tree
            appending (flatten a)))))

这是cond中的一个子句.它说 if tree是一个原子(可以是符号，数字，向量等，不是cons的其他任何东西)，然后返回(list tree) .正如 larsmans解释一样，flatten应该始终返回列表，这样可以确保例如(flatten 3)将返回(3).由于(loop for a in tree ...)适用于列表中的任何tree，因此实际上没有必要使用(null tree)的情况，因为nil/() 是是列表.该定义可以简化为:

It's one clause in a cond. It says that if tree is an atom (which could be a symbol, a number, a vector, etc., anything else that isn't a cons), then return (list tree). As larsmans explained, flatten should always return a list, and this ensures that (flatten 3), for instance, will return (3). Since the (loop for a in tree ...) will work for any tree that is a list, there's really no need to have a case for (null tree), since nil/() is a list. This definition could be simplified to:

(defun flatten (tree)
  (if (atom tree)
      (list tree)
      (loop for a in tree
            appending (flatten a)))))

在Stack Overflow上有一些类似的问题，有些问题与您发布的代码几乎完全相同(以格式为模).朋友是根据其中一个提出建议吗?无论如何，为了完整起见，您可以看一下:

There are some similar questions out there on Stack Overflow, and some have almost identical code to what you posted (modulo the formatting). Did the friend was basing a suggestion on one of those. At any rate, for the sake of completeness, you might have a look at:

• 在Lisp中展开列表
• Lisp中的Flats Nests函数-需要帮助理解(几乎相同的代码)
• 通用Lisp-整理可能包含符号的列表(相似代码)

• flatten list in lisp
• Flatten Nests Function in Lisp - need help understanding (almost identical code)
• Common Lisp - flatting a list that may contain symbols (similar code)

这篇关于在Lisp中展平树结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！