[Haskell-cafe] Segment Tree based Set

[Tony Morris]

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?
>
> --
> Tony Morris
> http://tmorris.net/
>
>
>


-- 
Tony Morris
http://tmorris.net/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20121029/3aade4db/attachment.htm>