[Haskell-cafe] Re: Lazy XML handling

[Niklas Broberg]

MR K P Shupke wrote:
>Can you give me an example where processing HAS to be in a different order?

No, but I can give an example where a list based encoding is less 
sufficient.

I'm coming from a completely different view here, namely that of using 
Haskell not to query or transform but to create XML. I'm currently in a 
project[1] trying to fix a working implementation of Haskell Server 
Pages[2], i.e. using Haskell as a server-side scripting language for dynamic 
webpages. Clearly the most used mode of operation in this setting is 
constructing an XML tree rather than querying or transforming an existing 
one.

With this in mind, the list based encoding would be less efficient than a 
treelike datatype. Building the XML tree is likely to be done bottom-up, and 
adding a parent to a subtree would be O(n) with a list, but O(1) with a tree 
datatype. Building a whole tree from the bottom up is O(n^2) for a list, but 
O(n) for the tree datatype.

MR K P Shupke wrote:
>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 fact that the list based representation is indeed more complex is in my 
opinion a clear indication that it should not be the standard. Compare this 
to Haskell strings where the standard is the simple but ineffective [Char], 
but where there is another more efficient representation, PackedString, if 
you really need it. Simplicity and ease of understanding is not to be taken 
lightly.
By using a tree datatype representation you also get pattern matching 
directly on the structure of the tree, a very useful feature to have.

MR K P Shupke wrote:
>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.

That might possibly be a programmatic advantage, though I don't see how it 
would be more difficult with a tree datatype. In any case it is no more 
efficient, both are O(n).
As far as I can tell there is no single area where the list representation 
would outperform a tree datatype, other than the special case of lazy 
streaming.

My suggestions are thus:
The standard representation should be a tree datatype, both because it is 
more general and efficiently supports a wide range of operation modes 
(construction, querying, transformation, rendering), and also because that 
is what lies closest to the intuition of XML.
However, the ability to stream large XML structures lazily is clearly useful 
and is difficult to achieve using a tree datatype. Why not add it as a 
specialisation?
The standard representation would be a datatype XML living in Data.XML (or 
similar), and the specialized would be a type XMLStream living in 
Data.XML.Stream. There should of course also be functions to convert between 
the types.

Comment away,

/Niklas

[1] http://www.dtek.chalmers.se/~d00nibro/hsp/
[2] http://www.research.microsoft.com/~emeijer/Papers/HSP.pdf

_________________________________________________________________
Protect your PC - get McAfee.com VirusScan Online 
http://clinic.mcafee.com/clinic/ibuy/campaign.asp?cid=3963