Hi there I wanted to share sparse-set for the first time, an efficient vector-based sparse set for Haskell. This package provides lazy, strict, mutable, and unboxed variants, each wrapping their respective counterparts in vector.
Game engines, especially ones with an ECS, often make heavy use of sparse sets for their efficient iteration and lookup. For example, ECS queries can be done with Data.SparseSet.intersection:
import qualified Data.SparseSet as S
main :: IO ()
main = print $ S.intersection as bs
where
as = S.insert (10 :: Int) "B" $ S.insert 0 "A" S.empty
bs = S.insert (10 :: Int) "B" S.empty
It’s cool that there are mutable and unboxed variants, but it’s unclear where the boxed immutable sets stand relative to the standard (also sparse) sets provided by [unordered-]containers. I would guess that they’re more compactly represented with worse asymptotics for certain operations, but this could do to be documented.
Actually, taking a look at the implementation, it’s using
newtype SparseVector a = SparseVector {unSparseVector :: Vector (Bool, a)}
which, contrary to its name, looks pretty dense to me? I expected something like
data SparseVector a = SparseVector
{ entries :: !(V.Vector a)
, indices :: !(U.Vector Int) -- Invariant: sorted
}
If it’s intended that these “sparse” vectors and sets are not sparsely represented but only sparse on some semantic level, then that absolutely merits big warnings somewhere.
Hmm that’s an interesting point as far as memory layout goes but I think this is close to the inspirations I got from Bevy and ECS back and forth to have this sparse set structure:
data SparseSet i a = SparseSet
{ dense :: Vector a,
sparse :: SparseVector i -- Invariant: sorted
}
EDIT: This will i.e. allocate slots for all elements up to index 1,000 in inserting there, which is good for game engines but probably not typical behavior so I should definitely note that in the docs
As far as the containers packages go I think the closest structures I found were Map or HashMap since this would probably be closer to Maps than Sets
is there a reasonable union operation on sparse sets? this looks fairly useful for a project I’m working on but I need to be able to union as part of monoidal accumulation. I’ve noticed none of the sparse set libraries I can find provide union so I’m guessing it’s not a sensible operation.
I wanted to share 