Safe Haskell	Safe
Language	Haskell2010

Data.SkipList

Description

SkipLists are comprised of a list and an index on top of it which makes deep indexing into the list more efficient (O(log n)). They achieve this by essentially memoizing the tail function to create a balanced tree.

NOTE: SkipLists are amortized efficient, see the benchmarks for performance results.

Synopsis

Documentation

data SkipList a Source #

SkipLists are lists that support amortized efficient indexing.

Instances

Functor SkipList Source #
Methods fmap :: (a -> b) -> SkipList a -> SkipList b # (<$) :: a -> SkipList b -> SkipList a #
Foldable SkipList Source #
Methods fold :: Monoid m => SkipList m -> m # foldMap :: Monoid m => (a -> m) -> SkipList a -> m # foldr :: (a -> b -> b) -> b -> SkipList a -> b # foldr' :: (a -> b -> b) -> b -> SkipList a -> b # foldl :: (b -> a -> b) -> b -> SkipList a -> b # foldl' :: (b -> a -> b) -> b -> SkipList a -> b # foldr1 :: (a -> a -> a) -> SkipList a -> a # foldl1 :: (a -> a -> a) -> SkipList a -> a # toList :: SkipList a -> [a] # null :: SkipList a -> Bool # length :: SkipList a -> Int # elem :: Eq a => a -> SkipList a -> Bool # maximum :: Ord a => SkipList a -> a # minimum :: Ord a => SkipList a -> a # sum :: Num a => SkipList a -> a # product :: Num a => SkipList a -> a #

toSkipList Source #

Arguments

:: Int	The step size in the index.
-> [a]	The list to convert.
-> SkipList a

Convert a list to a SkipList.

lookup :: SkipList a -> Int -> a Source #

Lookup in a SkipList.