[Haskell] Design guidance sought for Ranged Sets

[Paul Johnson]

When I started the Ranged Sets library "infinite" sets (i.e. sets based 
on infinite lists of ranges) looked easy.  The set primitives of union 
and intersection are simple merge algorithms, so they would work fine on 
infinite lists of ranges.  Set difference is implemented as a 
combination of intersection and negation, and negation is just a simple 
rearrangement of the range end points, so that works too.

However there are cases where this reasoning doesn't work.  Suppose I 
have two ranged sets based
on
   Range (BoundaryBelow n) (BoundaryBelow (n+1))

Set X contains these ranges for all even values of n>0

Set Y contains these ranges for all odd values of n>0

The union of these sets should be the single range

   Range (BoundaryBelow 1) BoundaryAboveAll

In practice however the naive merge algorithm will never terminate 
because it has to merge an
infinite number of ranges into the single range above.  A similar 
problem occurs with intersection.  The intersection of these sets should 
be empty, but again the merge algorithm will iterate forever looking for 
the first range in the set.

As a workaround in 0.0.2 I've put a counter in.  The intersection 
routine adds a null empty range after 10 empty iterations, and the union 
routine puts a break between touching ranges after 10 full iterations.  
Hence set membership tests are guaranteed to terminate in the presence 
of infinite lists.  However the same cannot be said of all the 
functions.  Set equality in particular has to evaluate the entire set in 
order to return True (although it does terminate at the first 
counter-example).  The question of whether a particular expression is 
guaranteed to terminate is not trivial if it contains even one infinite 
list.

So my question is this: are infinite sets worth bothering about?  Should 
I continue to put in fixes to ensure termination in at least some 
cases?  Or should I just declare that infinite lists of ranges are 
unsupported?

Thanks,

Paul.