[Haskell-cafe] Segment Tree based Set
tonymorris at gmail.com
Mon Oct 29 06:38:07 CET 2012
...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?
> Tony Morris
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe