[Haskell] Design guidance sought for Ranged Sets

[Jacques Carette]

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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell