If you searched hackage, you'd find http://hackage.haskell.org/package/SegmentTree Roman * Tony Morris [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 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?

On Mon, Oct 29, 2012 at 9:43 AM, Tony Morris wrote:

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.

Couldn't you just use :

instance Measured (Interval a) Bool where measure _ = True

Then the normal functions of SegmentTree would do what you wish for, no ? You don't need much beyond Haskell 98 (MPTC is used everywhere already). -- Jedaï

Yeah that looks useful indeed. I am surprised there isn't a DIET on hackage. On Tue, Oct 30, 2012 at 3:55 AM, Stephen Tetley wrote:

Are Martin Erwig's "diets" anything close?

http://web.engr.oregonstate.edu/~erwig/diet/

On 29 October 2012 04:48, Tony Morris 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