lazyset

Set and Map from lazy/infinite lists. https://github.com/happyherp/lazyset

Latest on Hackage:0.1.0.0

This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow stackage.org to host generated Haddocks.

MIT licensed by Carlos Freund

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

Changes

Revision history for lazyset

0.1.0.0 -- YYYY-mm-dd

  • First version. Released on an unsuspecting world.
  • Import of files from https://github.com/happyherp/littlethings/tree/master/euler
  • making this a cabal-module
comments powered byDisqus