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

_______________________________________________
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply via email to