# lazyset: Set and Map from lazy/infinite lists.

[ data, library, mit ] [ Propose Tags ]

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

## Modules

[Index]

• Data

#### Maintainer's Corner

For package maintainers and hackage trustees

Candidates

Versions [RSS] 0.1.0.0 ChangeLog.md base (>=4.9 && <4.10), containers (>=0.5.8.1 && <0.6), data-ordlist (>=0.4 && <0.5) [details] MIT Carlos Freund carlosfreund@googlemail.com Data https://github.com/happyherp/lazyset head: git clone https://github.com/happyherp/lazyset by carlos_freund at 2016-12-15T11:53:11Z NixOS:0.1.0.0 904 total (6 in the last 30 days) (no votes yet) [estimated by Bayesian average] λ λ λ Docs available Last success reported on 2016-12-15

[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