如何将平面列表转换为嵌套的树状结构？

Question

如何将平面列表转换为任意复杂的树状结构？首先,一个简单的例子,转换'(1 2 3 4)成'(1 (2 (3 (4)))).我知道如何用经典递归来做到这一点:

(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).如何编写能够在任何此类嵌套结构中转换平面列表的通用函数？我可以考虑给出一个带虚拟值的模板.例如:

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

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

(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或一些其他高级功能？

Answer 1

将(1 2 3 4)转换为(1(2(3(4))))实际上并不像你希望的那样简单,如果你正在使用reduce.你需要指定:from-end t如果你想先处理4,减少函数要么用3和4调用,如果没有:指定初始值,或者用4和初始值(如果有).这意味着你可以使用这样的东西,函数检查特殊的初始情况:

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

在我看来,涉及模板的解决方案更有趣.定义一个maptree函数很容易,该函数将函数映射到树上并返回一个带有函数结果的新树:

(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函数,使用从元素列表中提供元素的函数调用它并不困难,直到该元素列表用完为止.这提供了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 over a tree.在这种情况下,您可以使用我对该问题的答案中的树减少函数:

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

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