Copyright | (c) Carlos Freund 2016 |
---|---|

License | MIT |

Maintainer | carlosfreund@gmail.com |

Stability | experimental |

Safe Haskell | Safe |

Language | Haskell2010 |

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

- data LazySet a = LazySet [Set a]
- member :: Ord a => a -> LazySet a -> Bool
- lookup :: Ord a => a -> LazySet a -> Maybe a
- null :: LazySet a -> Bool
- size :: Ord a => LazySet a -> Int
- spanAntitone :: Ord a => (a -> Bool) -> LazySet a -> (LazySet a, LazySet a)
- union :: Ord a => LazySet a -> LazySet a -> LazySet a
- empty :: Ord a => LazySet a
- fromAscList :: Ord a => [a] -> LazySet a
- growFromAscList :: Ord a => Float -> [a] -> LazySet a
- fromList :: Ord a => [a] -> LazySet a
- fromDescList :: Ord a => [a] -> LazySet (Down a)
- build :: Ord a => Int -> Float -> [a] -> [Set a]
- toList :: Ord a => LazySet a -> [a]

# Documentation

# Query

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

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 Source #

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.

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

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) Source #

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.

# Build

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

Builds a `LazySet`

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

:: Ord a | |

=> Float | The factor by which the subtrees grow.
Must be >= 1.0. A growth of 1.0 makes the |

-> [a] | An ascending List |

-> LazySet a |

Like `fromAscList`

but with a custom growth-factor.

Kind of internal.