Opened 11 years ago

Closed 10 years ago

Last modified 9 years ago

#996 closed proposal (wontfix)

Add ranged sets

Reported by: pauljohnson Owned by:
Priority: normal Milestone:
Component: libraries/base Version: 6.6
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

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).

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:

<= 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 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.

Attachments (1)

test.txt (78.4 KB) - added by pauljohnson 11 years ago.

Download all attachments as: .zip

Change History (5)

Changed 11 years ago by pauljohnson

Attachment: test.txt added

comment:1 Changed 11 years ago by simonmar

Is there a good reason this has to be in base rather than in a separate package?

comment:2 Changed 10 years ago by ross

Resolution: wontfix
Status: newclosed

This should be a separate package.

comment:3 Changed 9 years ago by simonmar

Architecture: UnknownUnknown/Multiple

comment:4 Changed 9 years ago by simonmar

Operating System: UnknownUnknown/Multiple
Note: See TracTickets for help on using tickets.