[Haskell-cafe] Understanding allocation behavior

[David F. Place]

After reading Daniel Fischer's message about trying to use EnumSet in  
his Sudoku.hs and finding that it was slower when processing a large  
data set, I decided to do some profiling.  I rewrote his solver to  
use EnumSets and profiled it.  The culprit turns out to be the  
following function which is responsible for 22% of the allocating in  
the run.  Is there a more efficient way to write this function?

foldBits :: Bits c => (a -> Int -> a) -> a -> c -> a
foldbits _ z 0  = z
foldBits f z bs = foldBits' f 0 bs z

foldBits' :: Bits c => (a -> Int -> a) -> Int -> c -> a -> a
foldBits' f i bs z
     | bs == 0 = z
     | otherwise = z' `seq` foldBits' f i' bs' z'
     where z' | 1 == bs .&. 1 = f z i
                     | otherwise =  z
                 i' = i + 1
                bs' = bs `shiftR` 1

ps.  I was impressed with how hairy DF's algorithm is and I am not  
really enough interested in Sudoku to spend the  time needed to grok  
it.  So, I decided to try an experiment to see if I could restructure  
it without understanding it very deeply.

Step 1. comment out all the type signatures.
Step 2. find the main place that I wanted to change from [Int]  to  
(Set Int)
Step 3. compile; make obvious edits; repeat until 0 errors

I had it running in a few minutes.  I can't imagine doing that in any  
other programming environment!

Cheers, David

--------------------------------
David F. Place
mailto:d at vidplace.com