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
_______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
