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

Richard O'Keefe ok at cs.otago.ac.nz
Wed Apr 11 02:15:26 CEST 2012

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"]])

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

More information about the Haskell-Cafe mailing list