[Haskell-cafe] Reconstructing a tree from a list of its paths (to leaves)

[Richard O'Keefe]

On 11/04/2012, at 4:23 PM, Arnaud Bailly wrote:

> You are right, of course. By "sensible properties" I simply meant the
> list of (Path, Value) is assumed to represent a tree (eg. it has been
> generated by a traversal of some original tree). By "ordered" I meant
> Path(s) segments are lexicographically ordered and (Path, Value) are
> enumerated from a tree using depth-first traversal.

My main point was that there is a "sensible property" that you did not
mention, and you still have not mentioned it, namely that
*ALL* non-structural information about a node must be represented in
the Value that corresponds to it (and of course, that all the nodes
are actually listed somewhere).

Given your constraints, the sequence of (Path,Value) pairs must begin
with a ([],Value) representing the non-structural information about the
root, then a sequence of (1:x11,v11) ... (1:x1k,v1k) .... (n:xn1,vn1)
... (n:xnm,vnm) pairs which you partition as
<(x11,v11) ... (x1k,v1k)> ... <(xn1,vn1) ... (xnm,vnm)>
and then process recursively to make the children.

The initial lexicographic ordering is _not_ an important property because
you can ensure that by sorting.  As long as the paths are numbered correctly,
the kind of traversal that was used to generate the initial list is not
important either.  But the no-missing-nodes and no-missing-non-structural-
information properties are crucial.