range-set-list

Memory efficient sets with ranges of elements.

https://github.com/phadej/range-set-list#readme

Version on this page:0.1.3.1@rev:6
LTS Haskell 22.39:0.1.3.1@rev:6
Stackage Nightly 2024-10-31:0.1.4@rev:1
Latest on Hackage:0.1.4@rev:1

See all snapshots range-set-list appears in

MIT licensed and maintained by Oleg Grenrus
This version can be pinned in stack with:range-set-list-0.1.3.1@sha256:84974f02b055f38d5768006e42d9016362291ac7bda84220a8eccc11b6d2ac3f,2044

Module documentation for 0.1.3.1

range-set-list

Build Status Hackage Stackage LTS 2 Stackage LTS 3 Stackage Nightly

A few trivial implementations of range sets.

You can find the package (and its documentation) on hackage.

This module is intended to be imported qualified, to avoid name clashes with Prelude functions, e.g.,

import Data.RangeSet.List (RSet)
import qualified Data.RangeSet.List as RSet

This package contains two implementations of exactly the same interface, plus one specialization, all of which provide exactly the same behavior:

  • “Data.RangeSet.List” implements the simplest RSet based on list. Set construction and manipulation is most efficient for this version, but lookups may require a full list traversal.
  • “Data.RangeSet.Map” implements a slightly less simple RSet based on map. Construction and manipulation have more overhead in this version, but lookups are significantly faster, especially for large sets.
  • “Data.RangeSet.IntMap” is simply a specialization of “Data.RangeSet.Map” to Ints based on IntMap.

Compared to Data.Set, this module also imposes an Enum constraint for many functions. We must be able to identify consecutive elements to be able to glue and split ranges properly.

The implementation assumes that

x < succ x
pred x < x

and there aren’t elements in between (not true for Float and Double). Also succ and pred are never called for largest or smallest value respectively.

Changes

0.1.3.1

  • Show instance print parens around

0.1.3

  • Data.RangeSet.Map.member doesn’t require Enum

0.1.2.0

  • Map implementations: Data.RangeSet.IntMap and Data.RangeSet.Map

0.1.1.0

  • Add Semigroup, NFData, Hashable and Typeable instances

0.1.0.0

  • Consider API stable

0.0.7

  • findMin & findMax

0.0.6

  • size

0.0.5

  • Export full

0.0.4

  • Complement sets (require Bounded), full and complement

0.0.3

  • Dependencies update

0.0.2

  • More quickcheck properties

0.0.1

  • Initial release