[Haskell-cafe] Segment Tree based Set
tonymorris at gmail.com
Mon Oct 29 09:43:11 CET 2012
It is not a Set, but a Map. Of course, I could use it to implement the
function I need with something like: type SSet a = STree [()] a, but
then I'd have to unnecessarily go beyond Haskell98.
Hoping there might be an interval tree or segment tree specifically for
On 29/10/12 18:36, Roman Cheplyaka wrote:
> If you searched hackage, you'd find
> * Tony Morris <tonymorris at gmail.com> [2012-10-29 15:38:07+1000]
>> Er, oops.
>> ...can be implemented as:
>> \a rs -> let s = Set.fromList (rs >>= \(a, b) -> [a..b]) in a `member` s
>> Something like that!
>> On Mon, Oct 29, 2012 at 2:48 PM, Tony Morris <tonymorris at gmail.com> wrote:
>>> I was wondering if anyone knows of a package implementing a fast lookup
>>> for an element in ranges.
>>> For example, this operation:
>>> Ord a => a -> [(a, a)] -> Bool
>>> ...can be implemented:
>>> \a rs -> let s = Set.fromList rs in a `member` s
>>> This is not particularly efficient. A segment tree seems like a more
>>> appropriate data structure to store the ranges. Does such a library exist?
More information about the Haskell-Cafe