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

Tom Pledger tpledger at ihug.co.nz
Fri Oct 29 22:20:07 EDT 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.


More information about the Haskell-Cafe mailing list