I need to do transform a flat alist (car is the level, cdr the data)
into a sexp tree, i.e.

'((0 . a) (1 . b) (0 . c) (1 . d) (2 . e) (1 . f))

into

((a (b)) (c (d (e)) (f)) ; hope I got that right ;)

Anyone up for a neat solution?

* "Leslie P. Polzer" <f9d1d9bc-52e8-4cd1-a42b-59f1495a9...@c36g2000prc.googlegroups.com> :
Wrote on Wed, 19 Nov 2008 02:30:34 -0800 (PST):

| I need to do transform a flat alist (car is the level, cdr the data)
| into a sexp tree, i.e.
|
| '((0 . a) (1 . b) (0 . c) (1 . d) (2 . e) (1 . f))
|
| into
|
| ((a (b)) (c (d (e)) (f)) ; hope I got that right ;)
|
| Anyone up for a neat solution?

This looks suspiciously close to the "newbie homework" Kenny posted in
2007-04.

<URL:http://coding.derkeiler.com/Archive/Lisp/comp.lang.lisp/2007-04/msg01...>

See discussions in that thread. My solution was in
<News:m3647ntmcn....@robolove.meer.net>

 (a)

it must be at level -1.

 ((a) ((b)) ...)

Here, A is also at what you call level 0, and b is one level deeper at 1.
Yet the tree structure is different from ((a (b)) ...).

From the flat list, we can guess that the left-to-right order of the items
ought be preserved, and each should appear at the given depth.

But under these these two constraints, many different trees can be
computed from a given flat list.

* Kaz Kylheku <20081119133427....@gmail.com> :
Wrote on Wed, 19 Nov 2008 21:38:18 +0000 (UTC):
|> I need to do transform a flat alist (car is the level, cdr the data)
|> into a sexp tree, i.e.
|>
|> '((0 . a) (1 . b) (0 . c) (1 . d) (2 . e) (1 . f))
|>
|> ((a (b)) (c (d (e)) (f)) ; hope I got that right ;)
|

| But under these these two constraints, many different trees can be
| computed from a given flat list.
|
| Are they all acceptable solutions, or are there further rules?

As specified the representation is ambiguous.  I would have recommended
the `path representation' in the thread from 2007-04
Subject: "Another "gotta be a better way" from <gasp> The Real World of Lisp"

that the I cited from 2007-04 in my parallel reply.

My guess is that the OP is making assumptions that numbering is
consecutive and refers to the last [rooted] branch:

(defun polzer-flatten.3 (list &aux stack ret)
  (loop for (num . elem) in list finally (return ret) do
        (push (setq stack (if (zerop num)
                              (list elem)
                              (nconc (ldiff stack (nthcdr num stack))
                                     (list elem))))
              ret)))

Might convert it into the unambiguous flattened `path representation'
which can be elegantly converted to a tree.  Just guessing of course.

What matters is the parent-child relationship between
the nodes.

it is part of a general problem where given a list of elements and the
index for each, generate a nested list of it. In your case, each
element didn't come with a full index but only the level, and their
position within a level is implicit in the order of your list.

further, inherent in your problem is the concept of well-complete
index set. Namely, what happens if, for example, your given list
contains a element that has level 10, while none has level 9.

In short summary, associated with your problem is:

• a function that turns implicit position to full index. So that,
instead of the position being implict in the list order, you associate
with each element a full index that represent the position of the
element in a tree's node.

• given a index set, you want to be able to determine if it is “well-
complete”, i.e. whether there are missing indexes (such as having
element of level 10 but no 9, or having position of 3 but no element
has 2).

• the concept of minimal index set. i.e. a not well-complete index set
but is the minimal one that fully specify the tree's shape.

• given a random index set, or a minimal index set, you want to
generate its well-complete index set.

• given a “well-complete” index set, generate a nested list in a
particular lang.

With the above, you can write various list manipulation functions that
deals with index sets in a flat way instead of nest lists. Example of
such function include: general transposition by a permutation, map to
particular level or levels (e.g. all leaves, all 2nd level, all 2nd
and 5th level elements), map to particular positions across the tree
(e.g. 3rd, 5th elements in all levels).

These are the fundamental elemens of a lang that process list, and is
a core part of Mathematica.

for several articles on this, and a complete set of code in
Mathematica as well as some functions implementated in perl, see:

• Tree Functions in Perl, Python, Java
http://xahlee.org/tree/tree.html
(project defunct)

Also, in lisp, list processing is a major pain in the ass, because it
has just cons, which in a mathematical sense means its list can only
have 2 element max, and in order to have list of longer length you
basically hack it, to arrive at so-called proper list. For full
detail, see:

• Fundamental Problems of Lisp
http://xahlee.org/UnixResource_dir/writ/lisp_problems.html

bottom on the “cons business” section.

here's a short plain text excerpt:
------------------------------

The Cons Business

The above are some of the damages of irregularity in lisp's syntax.
The other fundamental problem in the language is its cons cells as its
list construction primitive.

Lisp at core is based on functional programing on lists. This is
comparatively a powerful paradigm. However, for historical reasons,
lisp's list is based on the hardware concept of “cons” cell. From a
mathematical point of view, what this means is that lisp's lists is
limited to a max of 2 elements. If you want a longer list, you must
nest it and interpret it in a special way. (i.e. effectively creating
a mini-protocol of nesting lists, known as proper lists.) The cons
fundamentally crippled the development of list processing.

Lisp being historically based the cons for like 2 or 3 decades. The
cons (and cdr, car, caadar etc) are fundamentally rooted in the lisp
langs, is thus not something that can be easily mended. This is
unfortunate. However, this situation could be improved. (by, for
example, exposing only higher-level list manipulation functions in all
newer literature, or even mark cons related functions as obsolete)

One of the myth that is quickly injected into budding lispers, is that
cons are powerful. It is powerful in the sense any assembly lang is
powerful. Lisp's cons is perhaps the greatest fuck up in the history
of computer languages.

The cons issue bugged me for 10 years, since i first tried to learn
scheme in ~1999. I've never worked with lisp (other than academic
reading) until in recent years with emacs lisp since 2005. Several
times i tried to explain to lispers this problem, but usually with
paragraphs and paragraphs of descriptions, analogies, examples,
frustrated by how hard it is to convey such a simple flaw (aided by
their blind, deep-seated, lisp fanaticism). Yesterday it hit on me.
The above mathematical aspect of lisp's cons is the first time i
formulated the cons problem concisely. (my previous verbose
explanation here: Lisp's List Problem )

  Xah
∑ http://xahlee.org/