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

[Arnaud Bailly]

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.

Thanks,
Arnaud

On Wed, Apr 11, 2012 at 2:15 AM, Richard O'Keefe <ok at cs.otago.ac.nz> wrote:
>
> On 10/04/2012, at 7:55 PM, Arnaud Bailly wrote:
>> I am manipulating labeled multiway trees, some kind of "lightweight"
>> XML notation. One thing I would like to be able to do is manipulating
>> a tree as a list of (Path, Value). Generating such a list is easy but
>> I am a little bit surprised to find it harder to reconstruct a tree,
>> given such a list assuming some sensible properties (list is ordered,
>> for example).
>
>
> Given a tree, there is a unique set of (Path, Value) pairs.
> Given a set of (Path, Value) pairs, there might be no trees,
> one, or infinitely many.
>
> For example, suppose we have
>
>    data XM = XE String [XM] | XL String
>
> as a simplification of XML and
>
>    paths :: XM -> [([Int],String)]
>
>    paths (XL s)    = [([], s)]
>    paths (XE _ ks) = [(i:p,v) | (i,k) <- zip [1..] ks, (p,v) <- paths k]
>
> as the function to reduce a tree to a list of (path,value) pairs.
>
>
>    paths (XE "foo" [XE "bar" [XL "zabbo"], XE "ugh" [XL "troppo"]])
> ==>
>    [([1,1],"zabbo"),([2,1],"troppo")]
>
> in which "foo", "bar", and "ugh" have been irretrievably lost.
>
> So you need to be rather more explicit about your "sensible properties".
> (The list being ordered is not one of them; sorting is a solved problem.)
>
>
>