[Haskell-cafe] Segment Tree based Set
roma at ro-che.info
Mon Oct 29 09:36:52 CET 2012
If you searched hackage, you'd find
* 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?
More information about the Haskell-Cafe