[Haskell-cafe] Segment Tree based Set

[Tony Morris]

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
this task.

On 29/10/12 18:36, Roman Cheplyaka wrote:
> If you searched hackage, you'd find
> http://hackage.haskell.org/package/SegmentTree
>
> Roman
>
> * 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:
>>
>>> Hi,
>>> 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?


-- 
Tony Morris
http://tmorris.net/