William James
11/12/2015 3:30:00 PM
Ken Tilton wrote:
> Mattias Nilsson wrote:
> > On Apr 22, 6:10 am, Ken Tilton <k...@theoryyalgebra.com> wrote:
> > [...]
> >
> >>Your mission, should you blah blah blah, is to take a list of field
> >>outputs (again, a list whose last element is data, the rest a path) and
> >>collapse them into the implied tree(s):
> >>
> >>#+test
> >>(time (tree-ify '((x one a 1)(x two a 2)(x three 42)(y two b 3)(x one b 4))))
> >>;; 39 cons cells
> >>;; -> ((Y (TWO (B 3))) (X (THREE 42) (TWO (A 2)) (ONE (B 4) (A 1))))
> >
> > [...]
> >
> > If I have understood the problem specification correctly, here's my
> > suggested solution:
> >
> > (defun leaf-tree (leaf)
> > (reduce #'list leaf :from-end t))
> >
> > (defun insert-leaf (leaf tree)
> > (let ((subtree (assoc (first leaf) (rest tree))))
> > (if subtree
> > (insert-leaf (second leaf) subtree)
> > (push leaf (rest tree)))))
> >
> > (defun tree-ify (data)
> > (let ((tree (list 'root)))
> > (dolist (d data tree)
> > (insert-leaf (leaf-tree d) tree))))
> >
> > I took the liberty of adding an extra root, since it made the code
> > nicer
> > (without it, INSERT-LEAF was split into two functions...).
> >
> > I don't actually know if it's any better than your solution, but it
> > was a
> > fun excercise nonetheless.
>
> Nice. I collapsed it into one and eliminated the root at the last second:
>
> (defun tree-ify3 (data)
> (labels ((insert-leaf (leaf tree)
> (bif (subtree (assoc (first leaf) (rest tree)))
> (insert-leaf (second leaf) subtree)
> (push leaf (rest tree)))))
> (loop with tree = (cons nil nil)
> for path in data
> for leaf = (reduce #'list path :from-end t)
> for subtree = (assoc (first leaf) (rest tree))
> if subtree do (insert-leaf (second leaf) subtree)
> else do (push leaf (rest tree))
> finally (return (cdr tree)))))
> But that bumps the cons count from 39 to 54 with the otherwise nifty
> trick of making each flat list a tree at the get-go. Can we lose that?
>
> (defun tree-ify4 (data)
> (labels ((list-tree (list)
> (reduce #'list list :from-end t))
> (insert-leaf (leaf tree)
> (bif (subtree (assoc (first leaf) (rest tree)))
> (insert-leaf (cdr leaf) subtree)
> (push (list-tree leaf) (rest tree)))))
> (loop with tree
> for leaf in data
> do (bif (subtree (assoc (first leaf) tree))
> (insert-leaf (cdr leaf) subtree)
> (setf tree (push (list-tree leaf) tree)))
> finally (return tree))))
>
> Still consing 44 over 39. and it looks like we do not need the extra
> root cons even temporarily.
>
> btw, your use of reduce to convert a list to a tree was slick.
MatzLisp (Ruby):
def merge tree, x
if y = tree.assoc(x[0])
merge y, x[1]
else
tree.push x
end
end
def tree_ify array
tree = []
array.each{|x| merge tree, x.reverse.reduce{|a,b| [b,a]}}
tree
end
tree_ify [[:x,:one,:a,1],[:x,:two,:a,2],[:x,:three,42],
[:y,:two,:b,3],[:x,:one,:b,4]]
===>[[:x, [:one, [:a, 1], [:b, 4]], [:two, [:a, 2]], [:three, 42]],
[:y, [:two, [:b, 3]]]]
--
As more and more power gravitates in the capital, the more vital it becomes for
the corporate America to secure its interests by corrupting that seat of power.
www.kolumbus.fi/aquilon/america-middle-class-and-the-end-of-growth.htm