[Haskell-cafe] Segment Tree based Set

Tony Morris tonymorris at gmail.com
Mon Oct 29 05:48:11 CET 2012

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

More information about the Haskell-Cafe mailing list