[Haskell-cafe] Efficient Sets for Small Enumerations

David F. Place d at vidplace.com
Mon Apr 3 08:19:25 EDT 2006

Often when writing algorithms which involve set operations on small  
enumerations, I start off using Data.Set.  I soon find performance  
requires rewriting that code to use bitwise operations.  I miss the  
nice interface of Data.Set and the type checking of using a proper  
data type.

So, as an exercise in writing a library, I wrote out an  
implementation of bitwise set operations using the interface of  
Data.Set with a couple of extensions.  It provides an abstract  
interface and type checking.  Using GHC -O3, code compiles right down  
to the primitive bit-twiddling operators.  My example program (a  
sudoku solver) runs several times faster.

I'll be grateful for any feedback on this.  Perhaps something like it  
would be useful included in the standard libraries.

Cheers, David

-------------- next part --------------
A non-text attachment was scrubbed...
Name: EnumSet.hs
Type: application/octet-stream
Size: 11042 bytes
Desc: not available
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20060403/b93b642d/EnumSet.obj
-------------- next part --------------

David F. Place
mailto:d at vidplace.com

More information about the Haskell-Cafe mailing list