Space faults in HaXml

[Joe English]

Earlier, I wrote:

> [... modifying the test program ] to use mkElem' and +++
> instead of mkElem and cat finally fixes the problem.
> I'm still not sure *why* this does the trick --
> hopefully somebody smarter can explain that --
> but the modified program runs in bounded space,
> no matter how large the input file is.

Figured it out.  The 'cat' combinator:

	cat :: [a -> [b]] -> (a -> [b])
	cat fs = \e-> concat [ f e | f <- fs ]

holds on to the input 'e' just a *little* bit longer
than it needs to.  Here's a slightly modified version:

	cat [] = const []
	cat fs = foldr1 (lift (++)) fs
		 where lift f g h x = f (g x) (h x)


Since the test program is more or less a tree homomorphism,
this makes a big difference: using this version of 'cat'
lets it run in bounded space, instead of keeping the entire
input tree in the heap.


--Joe English

  jenglish@flightlab.com