[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.
Regards,
Tom
More information about the Haskell-Cafe
mailing list