Keean Schupke wrote:
contractSet :: BasicSet -> BasticSet -> BasicSet contractSet x@(x0@(sx,ex):xs) y@(y0:(sy,ey):ys) | ex < sy = x0:contractSet xs y | sy < sx = y0:contractSet x ys | otherwise = contract x0 y0:contractSet xs ys
I think the last line needs to be something like | otherwise = contractSet (contract x0 y0:xs) ys I'm not sure that's correct, though. Another option is to represent a set as an unpaired list of switchover points, i.e. points which are at the beginning or end of an interval. Then binary set ops look just like a sorted list merge, except that you omit result values that don't change the membership property: setUnion = setOp 14 setIntersection = setOp 8 setDifference = setOp 2 setOp :: Int -> Int -> BasicSet -> BasicSet -> BasicSet setOp opTable = helper 0 where helper state (x:xs) (y:ys) = case compare x y of EQ -> stateSwitch state 3 x (helper xs ys) LT -> stateSwitch state 1 x (helper xs (y:ys)) EQ -> stateSwitch state 2 y (helper (x:xs) ys) helper (x:xs) [] = stateSwitch state 1 x (helper xs []) helper [] (y:ys) = stateSwitch state 2 x (helper [] ys) stateSwitch state mask xy xs ys = let newState = state `xor` mask tail = helper newState xs ys in if testBit opTable state == testBit opTable newState then tail else xy:tail This may be as simple as you're going to get for a range representation (especially given that it handles all three interesting binary set operations in one function). Unfortunately this technique will not handle endpoints correctly -- e.g. the intersection of the range (1,2) and (2,3) will be the empty set instead of (2,2). We can solve this elegantly by putting the crossover points *between* two real numbers: data Side = JustBefore | JustThere | JustAfter deriving Ord data Near r = Near !r !Side deriving Ord JustThere is included so that you can easily compare crossover points with actual numbers when testing for set membership. As an added benefit that you get open/closed interval support for free. You can also handle set complement easily, either by adding/removing an initial value that's JustBefore -infinity, or by adding a Bool to the set representation and using it to initialize the state parameter when you iterate through the list. -- Ben