Geek Answers Handbook

How to convert a flat list to a nested tree structure?

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

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

Now, what if the nested structure is arbitrarily complex? For example, I want to convert '(1 2 3 4 5 6 7 8)to '(1 (2 3) (4 (5 6) 7) 8). How to write a generic function that can convert a flat list to any such nested structure? I might consider creating a template with dummy values. For instance:

* (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 the recursion search function and user tree:

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

+2
2

(1 2 3 4) (1 (2 (3 (4)))) , , . : 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 , . :

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

:

(defun mimicry (source pattern)
  (labels ((rec (pattern)
             (mapcar (lambda (x)
                       (if (atom x)
                           (pop source)
                           (rec x)))
               pattern)))
    (rec pattern)))

:

CL-USER> (mimicry '(1 2 3 4 5) '(t (u (v)) (w x)))
(1 (2 (3)) (4 5))
+2

More articles:


All Articles