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

28 Oct 2004

      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)
       | e0e1 = (s0,e0):union' i0 i1 -- complete overlap
       | s1e0 = (s1,e1):union' i0 i1
       | s1e1 = (s1,e0):union' i0 i1 -- partial overlap
       | s0e0 = (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
 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@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

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

Keean Schupke