It is not a Set, but a Map. Of course, I could use it to implement the function I need with something like: type SSet a = STree [()] a, but then I'd have to unnecessarily go beyond Haskell98.
Hoping there might be an interval tree or segment tree specifically for this task. On 29/10/12 18:36, Roman Cheplyaka wrote: > If you searched hackage, you'd find > http://hackage.haskell.org/package/SegmentTree > > Roman > > * Tony Morris <tonymor...@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 <tonymor...@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/ _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
