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.
_______________________________________________
Haskell mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell
