[Haskell-cafe] Re: Lazy XML handling

Graham Klyne gk at ninebynine.org
Tue May 18 00:59:24 EDT 2004


At 11:37 17/05/04 +0100, MR K P SCHUPKE wrote:
> >I'd say it's still less easy (through clearly possible) for an application
> >to adopt alternative traversal patterns.
>
>Yes, thats true, but thats the order in which the tokenizer outputs
>tags... This is the order tags must be processed if you wish to
>stream - otherwise you need a heap of tags to keep the ones you are
>not ready to process from the tokenizer. In effect we can transform
>an algorithm that requires a different traversal into one that uses
>this traversal, at a possible slight increase in complexity. The gain
>is sequential stream based processing.
>
>Can you give me an example where processing HAS to be in a different order?

Well, for some value of "HAS", a program that is tasked to process a tree 
of values expressed in XML in breadth-first, right-to-left order.

But this is clearly an artificial response.  I acknowledge the broad 
equivalence of your list representation with the more explicit tree 
representation.  I think it's just that it is sometimes easier to see 
what's happening with the more explicit form.

#g
--

>In effect HaXml's representation actually simplifies to the above
>anyway... if you think about...
>
>[ A [B,C,D [E,F], G] H [I,J] ] => 
>[(0,A),(1,B),(1,C),(1,D),(2,E),(2,F),(1,G),(0,H),(1,I),(1,J)]
>
>The nested lists does not allow any extra flexibility in traversal, at the 
>cost of
>greater complexity. The one case it is simpler is if you want to look up a 
>single
>node by its 'tree address' - This is more complex with the list-rep, as you
>have to count nodes at a given level, skipping irrelevent nodes...
>
>The list rep is very good at data extraction, if you want to extract a 
>sub-tree
>of a given type you just ignore all tags until you find one of the correct
>type, then output all tags until the depth returns to the level of the initial
>tag.
>
>Regards,
>Keean.

------------
Graham Klyne
For email:
http://www.ninebynine.org/#Contact



More information about the Haskell-Cafe mailing list