Unusual definition of foldrBits and foldlBits

[meooow25]

foldrBits is defined in Data.IntSet.Internal as

containers/containers/src/Data/IntSet/Internal.hs

Lines 1649 to 1653 in f61b0c9

	foldrBits prefix f z bitmap = go (revNat bitmap) z
	where go 0 acc = acc
	go bm acc = go (bm `xor` bitmask) ((f $! (prefix+(WORD_SIZE_IN_BITS-1)-bi)) acc)
	where !bitmask = lowestBitMask bm
	!bi = indexOfTheOnlyBit bitmask

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 e076b33, 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]

Yes, I completely agree.

[meooow25]

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]

I just found #666 which describes this very issue.