these differences in jhc runtimes were the result of a single line change. < total time = 44.32 secs (2216 ticks @ 20 ms) < total alloc = 9,372,965,276 bytes (excludes profiling overheads) ---
total time = 36.74 secs (1837 ticks @ 20 ms) total alloc = 6,621,233,076 bytes (excludes profiling overheads)
the odd thing is, the change should not have changed the order of the algorithm at all. the change was (effectivly) Map.fromAscList . map f . Map.toAscList being changed to Map.map f both are O(n). but those constant factors matter. a lot. in any case, the reason I mention it is because if there were routines for converting between Set and Map that preserved the binary tree structure, I think their use could dramatically speed up many routines. In jhc (and other programs), I convert between them all the time and I'd hate to have to fall back on type Set a = Map a (). Map already has a keysSet, but it does the same inefficient thing building an intermediate list. all that is needed is a setToMap :: (a -> b) -> Set a -> Map a b the keysSet could be made more efficient in the next point release, but I guess adding setToMap would have to wait til the next major one. John -- John Meacham - ⑆repetae.net⑆john⑈