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