Data.SkipList

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.

Documentation

data SkipList a

SkipLists are lists that support amortized efficient indexing.

Instances

Functor SkipList

Methods

fmap :: (a -> b) -> SkipList a -> SkipList b

(<$) :: a -> SkipList b -> SkipList a

Foldable SkipList

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

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

Lookup in a SkipList.