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 <[email protected]> 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 [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
