holy frijoles: constant factors matter.

[Ross Paterson]

On Wed, Oct 12, 2005 at 07:22:07PM -0700, John Meacham wrote:
> 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 

Note that fromAscList is misnamed: it actually assumes a non-descending
list and checks for duplicates.  It's fromDistinctAscList that assumes
an ascending list.

> 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.

The old Data.Set was a wrapper around the finite map type, which made
that sort of thing easy to do.  The new one is a specialized copy
for efficiency, at the cost of extra code.  It's possible, but messy.
Will keysSet and setToMap be enough, or will we want intersection and
two versions each of difference and isSubmapOf too?

> 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

This would be a useful abstraction even with the simplistic definition

setToMap :: (a -> b) -> Set a -> Map a b
setToMap f s =
	Data.Map.fromDistinctAscList [(k, f k) | k <- Data.Set.toAscList s]