holy frijoles: constant factors matter.

[John Meacham]

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⑈