GHC: Ticket #996: Add ranged sets
http://ghc.haskell.org/trac/ghc/ticket/996
<p>
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 and BoundaryAboveAll).
</p>
<p>
The upshot is that you can represent a set of reals such as
</p>
<blockquote>
<p>
[ 2.0 < x <= 3.4, 6.7 < x]
</p>
</blockquote>
<p>
or a couple of encyclopedia volumes as:
</p>
<blockquote>
<p>
<a class="missing wiki"><= x < "blob", "goo" <= x < "hun"?</a>
</p>
</blockquote>
<p>
The usual set operators are provided. The library also does the Right Thing with adjacent values:
</p>
<blockquote>
<p>
[2 < x <= 3] Union [4 <= x < 5] == [2 < x < 5]
</p>
</blockquote>
<blockquote>
<p>
[2.0 < x <= 3.0] Union [4.0 <= x < 5.0] == [2.0 < x <= 3.0, 4.0 <= x < 5.0]
</p>
</blockquote>
<p>
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.
</p>
<p>
The source contains Haddock comments and a comprehensive set of 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.
</p>
<p>
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.
</p>
en-usGHChttp://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://ghc.haskell.org/trac/ghc/ticket/996
Trac 1.0.1pauljohnsonFri, 10 Nov 2006 20:11:21 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/996
http://ghc.haskell.org/trac/ghc/ticket/996
<ul>
<li><strong>attachment</strong>
set to <em>test.txt</em>
</li>
</ul>
TicketsimonmarMon, 13 Nov 2006 12:43:58 GMT
http://ghc.haskell.org/trac/ghc/ticket/996#comment:1
http://ghc.haskell.org/trac/ghc/ticket/996#comment:1
<p>
Is there a good reason this has to be in base rather than in a separate package?
</p>
TicketrossTue, 19 Dec 2006 08:53:45 GMTstatus changed; resolution set
http://ghc.haskell.org/trac/ghc/ticket/996#comment:2
http://ghc.haskell.org/trac/ghc/ticket/996#comment:2
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>wontfix</em>
</li>
</ul>
<p>
This should be a separate package.
</p>
TicketsimonmarTue, 30 Sep 2008 15:40:04 GMTarchitecture changed
http://ghc.haskell.org/trac/ghc/ticket/996#comment:3
http://ghc.haskell.org/trac/ghc/ticket/996#comment:3
<ul>
<li><strong>architecture</strong>
changed from <em>Unknown</em> to <em>Unknown/Multiple</em>
</li>
</ul>
TicketsimonmarTue, 30 Sep 2008 15:51:10 GMTos changed
http://ghc.haskell.org/trac/ghc/ticket/996#comment:4
http://ghc.haskell.org/trac/ghc/ticket/996#comment:4
<ul>
<li><strong>os</strong>
changed from <em>Unknown</em> to <em>Unknown/Multiple</em>
</li>
</ul>
Ticket