If you decide to continue working with infinite sets, then my advice would be to change your representation. For infinite sets, do not use an implicit representation (ie like a potentially infinite list) but switch to an explicit symbolic-generator representation. In other words, you need to use finite introspection to be able to do your computations. So you'd have something like RangeGen (Even "n") (BoundaryBelow "n") (BoundaryBelow $ Succ "n") RangeGen (Odd "n") (BoundaryBelow "n") (BoundaryBelow $ Succ "n") Then you can have rules on predicates such that Union (Even x) (Odd y) | x == y gives you the predicate True. For example, this is one of the ``trick'' that Yampa uses for optimization, see the first paper on http://www.cs.nott.ac.uk/~nhn/papers.html. See also the paper on Automatic Differentiation on the same page for another look at the same idea. Another way to achieve similar results is via type class encodings, see http://www.haskell.org/pipermail/haskell/2004-November/014939.html All of the above have one point in common: instead of encoding a lot of information in *functions*, you encode the information in *data*, whether it is normal constructors, GADTs or type classes. Because the information is visible, you can inspect it in finite time. The hard design decision is then, what information do you encode visibly? The upside is that you get to inspect all the information you need to make good decisions (in finite time). The downside is that you lose alpha-equivalence, and you must implement it yourself. [This is a non-trivial downside in a functional language!]. It is perhaps worthwhile noting that Computer Algebra abounds with such design decisions and encoding ``tricks'' of using data instead of functions (which is where I first learned of this, before I recognized the same ideas in functional programming, as cited above). Jacques Paul Johnson wrote:
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 Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell