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 |
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 |
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 |
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 |
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 |
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 |
Free forum by Nabble | Edit this page |