[Haskell] Design guidance sought for Ranged Sets
carette at mcmaster.ca
Wed Dec 21 13:53:42 EST 2005
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
Another way to achieve similar results is via type class encodings, see
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).
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
> 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?
> Haskell mailing list
> Haskell at haskell.org
More information about the Haskell