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