From the README: Ranged sets allow programming with sets of values that are described by a list of ranges. A value is a member of the set if it lies within one of the ranges. The ranges in a set are ordered and non-overlapping, so the standard set operations can be implemented by merge algorithms in O(n) time. Obviously you can use this for sets of numbers, including things like Double that tend not to fit well into the enumerated membership model of conventional set implementations. But you can also have ranges of strings (or any other list of ordered types). So for example the set of all strings from "bar" to "foo" and "BAR" to "FOO" inclusive would be: strSet = rangedSet [ Range (BoundaryBelow "bar") (BoundaryAbove "foo"), Range (BoundaryBelow "BAR") (BoundaryAbove "FOO")] Note that this set includes "bar1" but not "foo1". I've created a SourceForge project for this, although I hope that once the library matures it will be included in the Base library package. The home page is at https://sourceforge.net/projects/ranged-sets/ I *think* I've also put the source in CVS, although at present the CVS web browser on SourceForge has not caught up with it. Paul.
On Sun, Dec 11, 2005 at 11:14:46PM +0000, Paul Johnson wrote:
From the README:
Ranged sets allow programming with sets of values that are described by a list of ranges. A value is a member of the set if it lies within one of the ranges. The ranges in a set are ordered and non-overlapping, so the standard set operations can be implemented by merge algorithms in O(n) time.
I was thinking about writing such a library myself. Now I won't have to :-) Best regards Tomasz -- I am searching for a programmer who is good at least in some of [Haskell, ML, C++, Linux, FreeBSD, math] for work in Warsaw, Poland
On Dec 12, 2005, at 12:06 PM, Tomasz Zielonka wrote:
On Sun, Dec 11, 2005 at 11:14:46PM +0000, Paul Johnson wrote:
From the README:
Ranged sets allow programming with sets of values that are described by a list of ranges. A value is a member of the set if it lies within one of the ranges. The ranges in a set are ordered and non- overlapping, so the standard set operations can be implemented by merge algorithms in O(n) time.
I was thinking about writing such a library myself. Now I won't have to :-)
For discrete value domains, you might also want to take a look at: http://eecs.oregonstate.edu/~erwig/diet/ http://eecs.oregonstate.edu/~erwig/papers/abstracts.html#JFP98 -- Martin
Martin Erwig wrote:
For discrete value domains, you might also want to take a look at:
http://eecs.oregonstate.edu/~erwig/diet/ http://eecs.oregonstate.edu/~erwig/papers/abstracts.html#JFP98
Thanks. I did actually consider using a tree structure instead of a list. However trees don't cope with infinite lists, and I do particularly want infinite lists of ranges. (Short pause for someone to point out that Wyzchyvski Heaps can process infinite lists in O(1) time). Paul.
participants (3)
-
Martin Erwig -
Paul Johnson -
Tomasz Zielonka