Hi again,
yes, i decided to go with my first idea after all and represent
real-valued sets as a list of ranges. It went pretty ok for a while,
but then inevitably new questions come up... *sigh*. i'll get this to
work eventually... maybe. :-)
for anyone still interested in the topic, here's where i got :
so, define basic sets as a list of ranges, a range being defined as a pair
representing the lower and upper bound.
> type Range = (Float, Float)
> type BasicSet = [Range]
some test sets:
> a,b :: BasicSet
> b = [(0.0, 1.0), (3.1415, 5.8), (22.0, 54.8)]
> a = [(0.3, 0.1), (3.15000000, 3.99), (1.0,1.0), (4.0, 4.1)]
some helper functions for working with Ranges :
> inRange :: Float -> Range -> Bool
> inRange x y = (x >= (fst y) && x <= (snd y))
> intersectRange :: Range -> Range -> Range
> intersectRange x y = ((max (fst x) (fst y)), (min (snd x) (snd y)))
> subRange :: Range -> Range -> Bool
> subRange x y = (fst x) >= (fst y) && (snd x) <= (snd y)
this allows you do check for subsets pretty straightforwardly...
> subSet :: BasicSet -> BasicSet -> Bool
> subSet [] _ = True
> subSet (x:xs) ys = if or [x `subRange` y | y <- ys]
> then subSet xs ys
> else False
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...
I'll probably find a way to get around this eventually.
I just wanted to keep the conversation going a bit longer for those
that are still interested.
cheers,
stijn
On Thu, 28 Oct 2004 11:09:36 +0100, Keean Schupke
<[EMAIL PROTECTED]> wrote:
> Subsets can be done like this:
>
> myInterval = Interval {
> isin = \n -> case n of
> r | r == 0.3 -> True
> | r > 0.6 && r < 1.0 -> True
> | otherwise -> False,
> rangein = \(s,e) -> case (s,e) of
> (i,j) | i==0.3 && j==0.3 -> True
> | i>=0.6 && j<=1.0 -> True
> | otherwise -> False,
> subset = \s -> rangein s (0.3,0.3) && rangein s (0.6,1.0)
> }
>
> The problem now is how to calculate the union of two sets... you cannot
> efficiently union the two rangein functions of two sets. Its starting to
> look
> like you need to use a data representation to allow all the
> functionality you
> require. Something like a list of pairs:
>
> [(0.3,0.3),(0.6,1.0)]
>
> where each pair is the beginning and end of a range (or the same)... If you
> build your functions to order the components, then you may want to protect
> things with a type:
>
> newtype Interval = Interval [(Double,Double)]
>
> isin then becomes:
>
> contains :: Interval -> Double -> Bool
> contains (Interval ((i,j):rs)) n
> | i<=n && n<=j = True
> | otherwise = contains (Interval rs) n
> contains _ _ = False
>
> union :: Interval -> Interval -> Interval
> union (Interval i0) (Interval i1) = Interval (union' i0 i1)
>
> union' :: [(Double,Double)] -> [(Double,Double)] -> [(Double,Double)]
> union' i0@((s0,e0):r0) i1@((s1,e1):r1)
> | e0<e1 = (s0,e0):union' r0 i1 -- not overlapping
> | e1<e0 = (s1,e1):union' i0 r1
> | s0<s1 && e0>e1 = (s0,e0):union' i0 i1 -- complete overlap
> | s1<s0 && e1>e0 = (s1,e1):union' i0 i1
> | s1<s0 && e0>e1 = (s1,e0):union' i0 i1 -- partial overlap
> | s0<s1 && e1>e0 = (s0,e1):union' i0 i1
> | otherwise = union' i0 i1
>
> And subset can be defined similarly...
>
>
>
> Keean.
>
_______________________________________________
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
