Space faults in HaXml
Thu, 08 Nov 2001 10:07:48 -0800
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.