[Haskell-cafe] Segment Tree based Set

[Roman Cheplyaka]

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?