Re: [Haskell-cafe] Re: Lazy XML handling
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? 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.
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
participants (2)
-
Graham Klyne -
MR K P SCHUPKE