The lazyset package

[ Tags: benchmark, data, library, mit ] [ Propose Tags ]

A Set and Map implementation that is completly lazy and works for infinite sets and maps.


[Skip to Readme]

Properties

Versions 0.1.0.0
Change log ChangeLog.md
Dependencies base (==4.9.*), containers (>=0.5.8.1 && <0.6), data-ordlist (==0.4.*) [details]
License MIT
Author Carlos Freund
Maintainer carlosfreund@googlemail.com
Category Data
Home page https://github.com/happyherp/lazyset
Source repository head: git clone https://github.com/happyherp/lazyset
Uploaded Thu Dec 15 11:53:11 UTC 2016 by carlos_freund
Distributions NixOS:0.1.0.0
Downloads 70 total (11 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2016-12-15 [all 1 reports]
Hackage Matrix CI

Modules

[Index]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees


Readme for lazyset-0.1.0.0

[back to package description]

lazyset

A Lazy Set and Map implemented in Haskell. Allows efficient, lazy lookups on sorted lists. The list may be of ininite size. The Source-List must

  • contain elements that implement Ord
  • must be ascending (or descending: see fromDescList)
  • either produce an infinite number of elements or terminate

Set Sample usage


import Data.Set.Lazy

set = fromAscList $ map (*3) [1..]

3 `member` set -> True
4 `member` set -> False

Map Sample usage


import Prelude hiding(lookup)
import Data.Map.Lazier


sqrtmap = fromList $ map (\i->(i, sqrt i)) [1..]
lookup 2 sqrtmap -> Just 1.4142135623730951

Performance

Elements from the Source-List will be requested in batches of increasing size. By default the batch-size is increases by two. This would lead to batches of 1,2,4,8,16. This can be changed by using growFromAscList factor list. For Example a factor of 1.3 casues the batches to be 1,2,2,3,3,4,5. Increasing the growth-factor reduces lookup times but increases the batch-size. When it is set to 1.0 it performs like a list. lookup: O(m) = log m where m is the index of the element in the source-list.

Issues

This breaks the set, because the underlying list stops producing elements.


set = fromList $ filter (<4) [1..]
5 `member` set