Re: [Haskell-cafe] Set of reals...?

29 Oct 2004

      Keith Wansbrough wrote:
[...]
...
Your data structure should be something like:
data Interval = Interval {
  left :: Double,
       leftopen :: Bool,
       right :: Double,
       rightopen :: Bool
}
data Set = Set [Interval]
If you want more efficiency, you probably want a bintree datastructure 
(search Google for "quadtree" and "octree", and make the obvious 
dimension shift).
An easy-ish special case, if you're only dealing with intervals in one 
dimension, is (untested):

    import Data.FiniteMap

    type IntervalSet k = FiniteMap k (k, Bool, Bool)

    isin :: (Ord k) => k -> IntervalSet k -> Bool
    k `isin` s
        = case fmToList_GE k s of
            [] -> False
            ((k2, (k1, open1, open2)):_) ->
                (if open1 then k > k1 else k >= k1) &&
                (if open2 then k < k2 else k <= k2)

where each key in the finite map is the upper end of a range, and each 
element of the finite map contains the lower end of the range and the 
open/closed flags. This sort of thing seems to be the intended use of 
the _GE functions in Data.FiniteMap.

Regards,
Tom

Re: [Haskell-cafe] Set of reals...?

Tom Pledger