[Haskell-cafe] Set of reals...?
Keean Schupke
k.schupke at imperial.ac.uk
Fri Oct 29 04:58:28 EDT 2004
Stijn De Saeger wrote:
>Now, for unions I tried the following:
>to take the union of two BasicSets, just append them and contract the result.
>contracting meaning: merge overlapping intervals.
>
>
>
>>contract :: Range -> Range -> BasicSet
>>contract (x1,y1) (x2,y2)
>> | x2 <= y1 = if x2 >= x1 then [(x1, (max y1 y2))] else
>> if y2 >= x1 then [(x2, (max y1 y2))] else [(x2,y2), (x1,y1)]
>> | x1 <= y2 = if x1 >= x2 then [(x2, (max y1 y2))] else
>> if y1 >= x2 then [(x1, (max y1 y2))] else [(x1,y1), (x2,y2)]
>> | x1 <= x2 = [(x1,y1), (x2, y2)]
>>
>>
>
>
>Now generalizing this from Ranges to BasicSets is where i got stuck.
>In my limited grasp of haskell and FP, this contractSet function below
>is just crying for the use of a fold operation, but i can't for the
>life of me see how to do it.
>
>
>
>>contractSet :: BasicSet -> BasicSet
>>contractSet [] = []
>>contractSet (x:xs) = foldl contract x xs -- this doesn't work, though...
>>
>>
>
>
>
The problem is you need to compare each range in x with each
range in y... unless they are both ordered smallest real to largest,
in which case you need to use a 'merge-sort' technique, taking
the range with the lowest starting value from the head of either
x or y, unless the ranges at the top of x and y overlap in which case you
merge the ranges. This is not naturally represented by a fold.
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
Keean.
More information about the Haskell-Cafe
mailing list