search

twanvl / multiset

multiset haskell package
Other
19 stars 14 forks source link

Convenience functions elemAt and deleteAt #46

Open tysonzero opened 2 years ago

tysonzero commented 2 years ago

Data.Set has:

elemAt :: Int -> Set a -> a  -- O(log n)
deleteAt :: Int -> Set a -> Set a  -- O(log n)

It would be nice to have similar functions for MultiSet: 

elemAt :: Int -> MultiSet a -> a  -- O(n)
distinctElemAt :: Int -> MultiSet a -> a  -- O(log n)
deleteAt :: Int -> MultiSet a -> MultiSet a  -- O(n)
distinctDeleteAt :: Int -> MultiSet a -> MultiSet a  -- O(log n)
distinctDeleteManyAt :: Int -> Occur -> MultiSet a -> MultiSet a  -- O(log n)
distinctDeleteAllAt :: Int -> MultiSet a -> MultiSet a  -- O(log n)

I'm mostly interested in elemAt for my purposes (using MultiSet as a bag to randomly take from).

You could theoretically bring down all the complexities to O(log n) but it would require changing the internal structure.

twanvl commented 2 years ago

I am not sure about elemAt and deleteAt, since they would have linear complexity, which users probably wouldn't expect. At that point you should probably use a different data structure. Adding that bookkeeping to MultiSet is not worth the cost for other use-cases.

For weighted random sampling there are specific data structures that can give you a sample in O(1), although I don't know if there are Haskell implementations.