Safe Haskell | Safe |
---|---|
Language | Haskell2010 |
Non-empty difference lists: a data structure for O(1) append on non-empty lists.
Synopsis
- data NonEmptyDList a where
- pattern Cons :: a -> [a] -> NonEmptyDList a
- toNonEmpty :: NonEmptyDList a -> NonEmpty a
- apply :: NonEmptyDList a -> [a] -> NonEmpty a
- toList :: NonEmptyDList a -> [a]
- toDList :: NonEmptyDList a -> DList a
- toEndo :: NonEmptyDList a -> Endo [a]
- toEndo' :: NonEmptyDList a -> [a] -> [a]
- fromNonEmpty :: NonEmpty a -> NonEmptyDList a
- singleton :: a -> NonEmptyDList a
- cons :: a -> NonEmptyDList a -> NonEmptyDList a
- snoc :: NonEmptyDList a -> a -> NonEmptyDList a
- append :: NonEmptyDList a -> NonEmptyDList a -> NonEmptyDList a
- concat1 :: NonEmpty (NonEmptyDList a) -> NonEmptyDList a
- replicate :: Int -> a -> NonEmptyDList a
- head :: NonEmptyDList a -> a
- tail :: NonEmptyDList a -> [a]
- unfoldr :: (b -> (a, Maybe b)) -> b -> NonEmptyDList a
- map :: (a -> b) -> NonEmptyDList a -> NonEmptyDList b
Documentation
data NonEmptyDList a where Source #
A difference list is a function that, given a list, returns the original contents of the difference list prepended to the given list.
Implemented as a newtype over [a] ->
.NonEmpty
a
pattern Cons :: a -> [a] -> NonEmptyDList a | A unidirectional pattern synonym using |
Instances
Conversion
toNonEmpty :: NonEmptyDList a -> NonEmpty a Source #
Convert a dlist to a non-empty list
apply :: NonEmptyDList a -> [a] -> NonEmpty a Source #
Apply a dlist to a list to get the underlying non-empty list with an extension
toList :: NonEmptyDList a -> [a] Source #
Convert a dlist to a list
toDList :: NonEmptyDList a -> DList a Source #
Convert to DList
.
Note: dlist
doesn't expose internals, so this have to go through list.
toEndo' :: NonEmptyDList a -> [a] -> [a] Source #
Convert to representation of DList
.
Construction
The O(1) functions.
fromNonEmpty :: NonEmpty a -> NonEmptyDList a Source #
Convert a list to a dlist
singleton :: a -> NonEmptyDList a Source #
Create dlist with a single element
cons :: a -> NonEmptyDList a -> NonEmptyDList a infixr 9 Source #
O(1). Prepend a single element to a dlist
snoc :: NonEmptyDList a -> a -> NonEmptyDList a infixl 9 Source #
O(1). Append a single element to a dlist
append :: NonEmptyDList a -> NonEmptyDList a -> NonEmptyDList a Source #
O(1). Append dlists
Other functions
concat1 :: NonEmpty (NonEmptyDList a) -> NonEmptyDList a Source #
O(spine). Concatenate dlists
replicate :: Int -> a -> NonEmptyDList a Source #
O(n). Create a dlist of the given number of elements.
Always creates a list with at least one element.
head :: NonEmptyDList a -> a Source #
O(n). Return the head of the dlist
tail :: NonEmptyDList a -> [a] Source #
O(n). Return the tail of the dlist
unfoldr :: (b -> (a, Maybe b)) -> b -> NonEmptyDList a Source #
O(n). Unfoldr for dlists
map :: (a -> b) -> NonEmptyDList a -> NonEmptyDList b Source #
O(n). Map over difference lists.