[Haskell-cafe] Set of reals...?

[Keean Schupke]

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.


Stijn De Saeger wrote:

>Thank you, 
>I eventually tried to go with this approad, after a few people's
>recommendations.
>But, like you mentioned in your post, now I find myself needing a
>notion of subset relations, and since you obviously can't define
>equality over functions, i'm stuck again. Do you know any way around
>this problem, or have i hit a dead end...?
>
>stijn.
>
>
>On Wed, 27 Oct 2004 10:50:24 +0100, Ben Rudiak-Gould
><benjamin.rudiak-gould at cl.cam.ac.uk> wrote:
>  
>
>>One idea that might not occur to a newcomer is to represent each set by
>>a function with a type like (Double -> Bool), implementing the set
>>membership operation. This makes set-theoretic operations easy: the
>>complement of s is not.s (though watch out for NaNs!), the union of s
>>and t is (\x -> s x || t x), and so on. Open, closed, and half-open
>>intervals are easy too. The big limitation of this representation is
>>that there's no way to inspect a set except by testing particular values
>>for membership, but depending on your application this may not be a problem.
>>
>>-- Ben
>>
>>
>>    
>>
>_______________________________________________
>Haskell-Cafe mailing list
>Haskell-Cafe at haskell.org
>http://www.haskell.org/mailman/listinfo/haskell-cafe
>  
>