search

haskell / containers

Assorted concrete container types
https://hackage.haskell.org/package/containers
315 stars 178 forks source link

Unusual definition of foldrBits and foldlBits #966

Closed meooow25 closed 1 year ago

meooow25 commented 1 year ago

foldrBits is defined in Data.IntSet.Internal as https://github.com/haskell/containers/blob/f61b0c9104a3c436361f56a0974c5eeef40c1b89/containers/src/Data/IntSet/Internal.hs#L1649-L1653

This is unusual because go traverses the full word, building up thunks, before returning a result. I would expect a foldr to be defined as

go 0 = z
go bm = f x (go bm')
  where x = ...
        bm' = ...

I don't think this has an effect on correctness, but it might have an effect on performance.

The implementation was introduced in https://github.com/haskell/containers/commit/e076b33f4cee3f657b5bdc5bf6f5a4c9e249d00c, which says

Foldr implementations bit-reverse the word and then iterate from the LSB to MSB using accumulator. That is faster then either not using accumulator or iterating from MSB to LSB.

Which seems a bit odd and worth rechecking in my opinion. Thoughts?

treeowl commented 1 year ago

Yes, I completely agree.

meooow25 commented 1 year ago

Great, happy to take a look at it after I'm done with some of the other PRs here. Don't want to take on too much at once.

meooow25 commented 1 year ago

I just found #666 which describes this very issue.