如何将平面列表转换为嵌套的树状结构? [英] How to convert a flat list into a nested tree-like structure?

问题描述

如何将平面列表转换为任意复杂的树状结构?首先，举一个简单的例子，将'(1 2 3 4)转换为'(1 (2 (3 (4)))).我知道如何使用经典递归:

How to convert a flat list into an arbitrarily complex tree-like structure? First, a simple example, convert '(1 2 3 4) into '(1 (2 (3 (4)))). I know how to do it with classical recursion:

(defun nestify (xs)
  (if (null xs)
      (list)
    (list (car xs) (nestify (cdr xs)))))

现在，如果嵌套结构任意复杂怎么办?例如，我想将'(1 2 3 4 5 6 7 8)转换为'(1 (2 3) (4 (5 6) 7) 8).如何编写能够在任何此类嵌套结构中转换平面列表的通用函数?我可以考虑提供一个带有虚拟值的模板.例如:

Now, what if the nested structure is arbitrarily complex? For example, I want to convert '(1 2 3 4 5 6 7 8) into '(1 (2 3) (4 (5 6) 7) 8). How can I write a general function that is able to convert a flat list in any such nested structure? I can think of giving a template with dummy values. For example:

* (nestify '(1 2 3 4 5 6 7 8) '(t (t t) (t (t t) t) t))
'(1 (2 3) (4 (5 6) 7) 8)

我第一次尝试使用递归和自定义树大小查找功能:

My first attempt using recursion and custom tree size finding function:

(defun length* (tr)
  "Count number of elements in a tree."
  (cond ((null tr) 0)
        ((atom tr) 1)
        (t (+ (length* (car tr))
              (length* (cdr tr))))))

(defun tree-substitute (xs tpl)
  "(tree-substitute '(1 2 3) '(t (t) t)) -> '(1 (2) 3)"
  (cond ((null tpl) nil)
        ((atom (car tpl))
         (cons (car xs) (tree (cdr xs) (cdr tpl))))
        (t (cons (tree xs (car tpl))
              (tree (nthcdr (length* (car tpl)) xs) (cdr tpl))))))

有什么方法可以以一种更优雅，更简洁的方式来更好地做到这一点?例如，将列表转换为树的函数可能不使用模板，尽管我无法想到该方法.我可以抽象出递归和其他详细信息并拥有简洁的reduce或其他一些高级功能吗?

Is there any way to do this better, in a more elegant and concise way? For example, the function converting a list into a tree might not use the template, although I can't think of the method. Can I abstract away recursion and other details and have a neat reduce or some other high-level function?

推荐答案

将(1 2 3 4)转换为(1(2(3(4))))实际上并不像您希望的那么简单您正在使用 reduce .如果要先处理4，则需要指定:from-end t ；如果没有:initial-value ，则用3和4调用归约函数.指定的值，如果是，则使用4和初始值.这意味着您可以使用类似以下内容的函数，其中该函数检查特殊的首字母大写:

Turning (1 2 3 4) into (1 (2 (3 (4)))) actually isn't quite as simple as you might hope, if you're using reduce. You need to specify :from-end t if you want to process 4 first, and the reduction function is either called with 3 and 4, if no :initial-value is specified, or with 4 and the initial value, if one is. That means you can use something like this, where the function checks for the special initial case:

(reduce (lambda (x y)
          (if y
            (list x y)
            (list x)))
        '(1 2 3 4)
        :from-end t
        :initial-value nil)
;=> (1 (2 (3 (4))))

在我看来，涉及 template 的解决方案要有趣得多.定义 maptree 函数很容易，该函数将函数映射到树上并返回带有函数结果的新树:

A solution that involves a template is much more interesting, in my opinion. It's easy enough to define a maptree function that maps a function over a tree and returns a new tree with the function results:

(defun maptree (function tree)
  "Return a tree with the same structure as TREE, but
whose elements are the result of calling FUNCTION with
the element from TREE.  Because TREE is treated as an 
arbitrarily nested structure, any occurrence of NIL is 
treated as an empty tree."
  (cond 
    ((null tree) tree)
    ((atom tree) (funcall function tree))
    ((cons (maptree function (car tree))
           (maptree function (cdr tree))))))

(maptree '1+ '(1 2 (3 (4 5)) (6 7)))
;=> (2 3 (4 (5 6)) (7 8))

鉴于 maptree 函数，使用提供了元素列表中的元素的函数调用它并不难，直到该元素列表用完为止.这提供了替代的定义:

Given the maptree function, it's not hard to call it with a function that provides an element from a list of elements, until that list of element is exhausted. This provides a definition of substitute-into:

(defun substitute-into (items tree)
  "Return a tree like TREE, but in which the elements
of TREE are replaced with elements drawn from ITEMS.  
If there are more elements in TREE than there are in 
ITEMS, the original elements of TREE remain in the result,
but a new tree structure is still constructed."
  (maptree #'(lambda (x)
               (if (endp items) x
                   (pop items)))
           tree))

(substitute-into '(1 2 3 4 5) '(t (u (v)) (w x)))
;=> (1 (2 (3)) (4 5))

(substitute-into '(1 2 3 4 5) '(t u (v w x) y z))
;=> (1 2 (3 4 5) Y Z)

另请参见

上面的 maptree 实际上只是树的更一般的减少或折叠功能的特例.请参阅在Lisp中使用reduce在一棵树上，以获取有关如何在树上折叠的更多信息.在这种情况下，您可以通过我的答案使用我的 tree-reduce 函数:

See Also

The maptree above is actually just a special case of a more general reduce, or fold, function for trees. Have a look at Using reduce over a tree in Lisp for some more information about how you can fold over trees. In this case, you could use my tree-reduce function from my answer to that question:

(defun tree-reduce (node-fn leaf-fn tree)
  (if (consp tree)
      (funcall node-fn 
               (tree-reduce node-fn leaf-fn (car tree))
               (tree-reduce node-fn leaf-fn (cdr tree)))
      (funcall leaf-fn 
               tree)))

并根据它定义maptree:

and define maptree in terms of it:

(defun maptree (function tree)
  (tree-reduce 'cons function tree))

这篇关于如何将平面列表转换为嵌套的树状结构?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！