Data.Set.Lazy

A Set that can be created from lazy, ordered, infinite lists.

Documentation

data LazySet a

Constructors

LazySet [Set a]

Instances

Eq a => Eq (LazySet a)

Methods

(==) :: LazySet a -> LazySet a -> Bool

(/=) :: LazySet a -> LazySet a -> Bool

Show a => Show (LazySet a)

Methods

showsPrec :: Int -> LazySet a -> ShowS

show :: LazySet a -> String

showList :: [LazySet a] -> ShowS

Query

member :: Ord a => a -> LazySet a -> Bool

Checks if the value is a member of the LazySet. Performance: O(m)=log m Where m is the position of the element beeing searched for. This only applies after the element has been fetched from the underlying list.

lookup :: Ord a => a -> LazySet a -> Maybe a

Searches for a value in a Set. If it can not be found returns Nothing otherwhise Returns 'Just a' if it can find it. The returned value will be the one from the set, not the one that was passed.

null :: LazySet a -> Bool

Returns true if the LazSet is empty.

size :: Ord a => LazySet a -> Int

Returns the size of the set. Do not use this on infinite Sets.

Combine

spanAntitone :: Ord a => (a -> Bool) -> LazySet a -> (LazySet a, LazySet a)

Splits the LazySet into two parts. The first containing all consecutive elements of the Set where the predicate applies. The second contains the (infinite) rest.

union :: Ord a => LazySet a -> LazySet a -> LazySet a

Union of two LazySets.

Build

empty :: Ord a => LazySet a

Create an empty LazySet.

fromAscList :: Ord a => [a] -> LazySet a

Builds a LazySet from an ascending ordered list. If the list is not ordered an error is thrown.

growFromAscList

Arguments

:: Ord a

=> Float

The factor by which the subtrees grow. Must be >= 1.0. A growth of 1.0 makes the LazySet behave like a List. The higher it is set, the more it behaves like a Set. The downside of a higher growth-factor is that bigger batches are extracted from the source-list at once.

-> [a]

An ascending List

-> LazySet a

Like fromAscList but with a custom growth-factor.

fromList :: Ord a => [a] -> LazySet a

Alias for fromAscList.

fromDescList :: Ord a => [a] -> LazySet (Down a)

Create a LazSet from a descending list.

build

Arguments

:: Ord a

=> Int

starting-depth

-> Float

growth-factor

-> [a]

Ascending source-list

-> [Set a]

Kind of internal.

Export

toList :: Ord a => LazySet a -> [a]

List with all elements in order.