The lazyset package

This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.

[maintain]

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


[Skip to ReadMe]

Properties

Versions0.1.0.0, 0.1.0.0
Change logChangeLog.md
Dependenciesbase (==4.9.*), containers (>=0.5.8.1 && <0.6), data-ordlist (==0.4.*) [details]
LicenseMIT
AuthorCarlos Freund
Maintainercarlosfreund@googlemail.com
CategoryData
Home pagehttps://github.com/happyherp/lazyset
Source repositoryhead: git clone https://github.com/happyherp/lazyset
UploadedThu Dec 15 11:52:04 UTC 2016 by carlos_freund

Modules

[Index]

Downloads

Maintainers' corner

For package maintainers and hackage trustees

Readme for lazyset-0.1.0.0

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

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