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

[Tom Pledger]

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