Hi.
Joe English writes:
> [...] ought to run in space bounded by the depth of the tree
> (which for XML documents is typically not very deep).
>
> This turns out not to be the case; testing with Hugs
> invariably fails with a "Garbage collection fails to
> reclaim sufficient space" on even moderately sized
> documents (5000 nodes or so).
>
> Is there something obviously wrong with the above formulation?
> If so, what can I do to fix it?
Beyond the two static errors ("Node a:siblings" should be "Node a
[]:siblings", and "(Tree a c)" should be "(Node a c)"), it's fine for
space use. I tested it with Hugs 98 (Nov 1999), and didn't find any
sign of lurking strictness:
Main> :t eventList
eventList :: Int -> [Event Char]
Main> :set +s
Main> length . fst . build . eventList $ 1000000
100000
(22700039 reductions, 38600096 cells, 161 garbage collections)
Main> length . preorderTree . Node '*' . fst . build . eventList $ 1000000
700001
(29900051 reductions, 47600115 cells, 198 garbage collections)
Main> :set
...
Current settings: +sfewui -tgl.qk -h250000 -p"%s> " -r$$ -c40
...
Compatibility : Haskell 98 (+98)
(The eventList function generates an Event list of the given length,
which will result in a very shallow tree.)
> I haven't by any means ruled out the possibility that the
> space leak is elsewhere in the code [...]
AFAICS it must be.
Regards,
Tom
