Reconstructing a tree from a list of its paths (to leaves)

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Reconstructing a tree from a list of its paths (to leaves)

Arnaud Bailly-2
Hello,
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).

I got the intuition this has already been tackled in one way or
another in a functional setting in Haskell (I code in Java but using
mostly functional constructs), but don't know where to look.

Thanks for your pointers and help,

Regards,
Arnaud

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Reconstructing a tree from a list of its paths (to leaves)

Twan van Laarhoven
On 10/04/12 09:55, Arnaud Bailly wrote:

> Hello,
> 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).
>
> I got the intuition this has already been tackled in one way or
> another in a functional setting in Haskell (I code in Java but using
> mostly functional constructs), but don't know where to look.

The haskell solution would be to consider first how to turn a single
(Path,Value) into a tree. Then you just combine these trees for all the
paths by taking their union. I attached some code.



Twan

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

2012-04-10 from-to-tree.hs (875 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Reconstructing a tree from a list of its paths (to leaves)

Arnaud Bailly-2
Hello Twan,
I have a rather clear idea of how I would do it (in Haskell or in
Java), but I feel this is something quite common that should have
already been handled in other contexts (eg. XML/XPath stuff, JSon, CSS
?), hence my question which was admittedly not clear enough.

Anyway, thanks a lot for your detailed answer and your code.

Best regards,
Arnaud

On Tue, Apr 10, 2012 at 12:26 PM, Twan van Laarhoven <[hidden email]> wrote:

> On 10/04/12 09:55, Arnaud Bailly wrote:
>>
>> Hello,
>> 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).
>>
>> I got the intuition this has already been tackled in one way or
>> another in a functional setting in Haskell (I code in Java but using
>> mostly functional constructs), but don't know where to look.
>
>
>
> The haskell solution would be to consider first how to turn a single
> (Path,Value) into a tree. Then you just combine these trees for all the
> paths by taking their union. I attached some code.
>
>
>
> Twan
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Reconstructing a tree from a list of its paths (to leaves)

Richard A. O'Keefe
In reply to this post by Arnaud Bailly-2

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.)




_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Reconstructing a tree from a list of its paths (to leaves)

Arnaud Bailly-2
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 <[hidden email]> 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.)
>
>
>

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Reconstructing a tree from a list of its paths (to leaves)

Richard A. 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.



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe