Ticket 996: Add ranged sets
Paul Johnson
paul at cogito.org.uk
Sat Nov 11 05:59:41 EST 2006
The ticket is at http://hackage.haskell.org/trac/ghc/ticket/996
Ranged sets represent sets of ordered values as lists of ranges. Each
range has a lower and upper boundary, and for any value and boundary the
value is either above or below the boundary: no value can ever sit on a
boundary. There are also boundaries for +/- infinity (BoundaryBelowAll?
<http://hackage.haskell.org/trac/ghc/wiki/BoundaryBelowAll> and
BoundaryAboveAll?
<http://hackage.haskell.org/trac/ghc/wiki/BoundaryAboveAll>).
The upshot is that you can represent a set of reals such as
[ 2.0 < x <= 3.4, 6.7 < x]
or a couple of encyclopedia volumes as:
["a" <= x < "blob", "goo" <= x < "hun"]
The usual set operators are provided. The library also does the Right
Thing with adjacent values:
[2 < x <= 3] Union [4 <= x < 5] == [2 < x < 5]
[2.0 < x <= 3.0] Union [4.0 <= x < 5.0] == [2.0 < x <= 3.0, 4.0
<= x < 5.0]
I've needed something like this more than once over the years, in
various languages. Haskell is the first one that can actually do the
Right Thing efficiently for a polymorphic type.
The source contains Haddock comments and a comprehensive set of
QuickCheck? <http://hackage.haskell.org/trac/ghc/wiki/QuickCheck>
properties. I've integrated these into the documentation. So far I've
tested this on GHC 6.4.1, although this patch is against the HEAD of the
current libraries.
If this patch is accepted I'll also add patches for ranged sets of times
(e.g. the set of all times within the first Tuesday of each month), and
to filter finite maps against ranged sets.
More information about the Libraries
mailing list