Data.DList.NonEmpty

Non-empty difference lists: a data structure for O(1) append on non-empty lists.

Documentation

data NonEmptyDList a

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.

Instances

Monad NonEmptyDList

Methods

(>>=) :: NonEmptyDList a -> (a -> NonEmptyDList b) -> NonEmptyDList b

(>>) :: NonEmptyDList a -> NonEmptyDList b -> NonEmptyDList b

return :: a -> NonEmptyDList a

fail :: String -> NonEmptyDList a

Functor NonEmptyDList

Methods

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

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

Applicative NonEmptyDList

Methods

pure :: a -> NonEmptyDList a

(<*>) :: NonEmptyDList (a -> b) -> NonEmptyDList a -> NonEmptyDList b

(*>) :: NonEmptyDList a -> NonEmptyDList b -> NonEmptyDList b

(<*) :: NonEmptyDList a -> NonEmptyDList b -> NonEmptyDList a

Foldable NonEmptyDList

Methods

fold :: Monoid m => NonEmptyDList m -> m

foldMap :: Monoid m => (a -> m) -> NonEmptyDList a -> m

foldr :: (a -> b -> b) -> b -> NonEmptyDList a -> b

foldr' :: (a -> b -> b) -> b -> NonEmptyDList a -> b

foldl :: (b -> a -> b) -> b -> NonEmptyDList a -> b

foldl' :: (b -> a -> b) -> b -> NonEmptyDList a -> b

foldr1 :: (a -> a -> a) -> NonEmptyDList a -> a

foldl1 :: (a -> a -> a) -> NonEmptyDList a -> a

toList :: NonEmptyDList a -> [a]

null :: NonEmptyDList a -> Bool

length :: NonEmptyDList a -> Int

elem :: Eq a => a -> NonEmptyDList a -> Bool

maximum :: Ord a => NonEmptyDList a -> a

minimum :: Ord a => NonEmptyDList a -> a

sum :: Num a => NonEmptyDList a -> a

product :: Num a => NonEmptyDList a -> a

Traversable NonEmptyDList

Methods

traverse :: Applicative f => (a -> f b) -> NonEmptyDList a -> f (NonEmptyDList b)

sequenceA :: Applicative f => NonEmptyDList (f a) -> f (NonEmptyDList a)

mapM :: Monad m => (a -> m b) -> NonEmptyDList a -> m (NonEmptyDList b)

sequence :: Monad m => NonEmptyDList (m a) -> m (NonEmptyDList a)

Traversable1 NonEmptyDList

Methods

traverse1 :: Apply f => (a -> f b) -> NonEmptyDList a -> f (NonEmptyDList b)

sequence1 :: Apply f => NonEmptyDList (f b) -> f (NonEmptyDList b)

Alt NonEmptyDList

Methods

(<!>) :: NonEmptyDList a -> NonEmptyDList a -> NonEmptyDList a

some :: Applicative NonEmptyDList => NonEmptyDList a -> NonEmptyDList [a]

many :: Applicative NonEmptyDList => NonEmptyDList a -> NonEmptyDList [a]

Apply NonEmptyDList

Methods

(<.>) :: NonEmptyDList (a -> b) -> NonEmptyDList a -> NonEmptyDList b

(.>) :: NonEmptyDList a -> NonEmptyDList b -> NonEmptyDList b

(<.) :: NonEmptyDList a -> NonEmptyDList b -> NonEmptyDList a

Bind NonEmptyDList

Methods

(>>-) :: NonEmptyDList a -> (a -> NonEmptyDList b) -> NonEmptyDList b

join :: NonEmptyDList (NonEmptyDList a) -> NonEmptyDList a

Foldable1 NonEmptyDList

Methods

fold1 :: Semigroup m => NonEmptyDList m -> m

foldMap1 :: Semigroup m => (a -> m) -> NonEmptyDList a -> m

toNonEmpty :: NonEmptyDList a -> NonEmpty a

IsList (NonEmptyDList a)

Associated Types

type Item (NonEmptyDList a) :: *

Methods

fromList :: [Item (NonEmptyDList a)] -> NonEmptyDList a

fromListN :: Int -> [Item (NonEmptyDList a)] -> NonEmptyDList a

toList :: NonEmptyDList a -> [Item (NonEmptyDList a)]

Eq a => Eq (NonEmptyDList a)

Methods

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

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

Ord a => Ord (NonEmptyDList a)

Methods

compare :: NonEmptyDList a -> NonEmptyDList a -> Ordering

(<) :: NonEmptyDList a -> NonEmptyDList a -> Bool

(<=) :: NonEmptyDList a -> NonEmptyDList a -> Bool

(>) :: NonEmptyDList a -> NonEmptyDList a -> Bool

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

max :: NonEmptyDList a -> NonEmptyDList a -> NonEmptyDList a

min :: NonEmptyDList a -> NonEmptyDList a -> NonEmptyDList a

Read a => Read (NonEmptyDList a)

Methods

readsPrec :: Int -> ReadS (NonEmptyDList a)

readList :: ReadS [NonEmptyDList a]

readPrec :: ReadPrec (NonEmptyDList a)

readListPrec :: ReadPrec [NonEmptyDList a]

Show a => Show (NonEmptyDList a)

Methods

showsPrec :: Int -> NonEmptyDList a -> ShowS

show :: NonEmptyDList a -> String

showList :: [NonEmptyDList a] -> ShowS

(~) * a Char => IsString (NonEmptyDList a)

Methods

fromString :: String -> NonEmptyDList a

Semigroup (NonEmptyDList a)

Methods

(<>) :: NonEmptyDList a -> NonEmptyDList a -> NonEmptyDList a

sconcat :: NonEmpty (NonEmptyDList a) -> NonEmptyDList a

stimes :: Integral b => b -> NonEmptyDList a -> NonEmptyDList a

NFData a => NFData (NonEmptyDList a)

Methods

rnf :: NonEmptyDList a -> ()

type Item (NonEmptyDList a)

type Item (NonEmptyDList a) = a

Conversion

toNonEmpty :: NonEmptyDList a -> NonEmpty a

Convert a dlist to a non-empty list

apply :: NonEmptyDList a -> [a] -> NonEmpty a

Apply a dlist to a list to get the underlying non-empty list with an extension

toList :: NonEmptyDList a -> [a]

Convert a dlist to a list

toDList :: NonEmptyDList a -> DList a

Convert to DList.

Note: dlist doesn't expose internals, so this have to go through list.

toEndo :: NonEmptyDList a -> Endo [a]

Convert to representation of DList.

toEndo' :: NonEmptyDList a -> [a] -> [a]

Convert to representation of DList.

Construction

The O(1) functions.

fromNonEmpty :: NonEmpty a -> NonEmptyDList a

Convert a list to a dlist

singleton :: a -> NonEmptyDList a

Create dlist with a single element

cons :: a -> NonEmptyDList a -> NonEmptyDList a infixr 9

O(1). Prepend a single element to a dlist

snoc :: NonEmptyDList a -> a -> NonEmptyDList a infixl 9

O(1). Append a single element to a dlist

append :: NonEmptyDList a -> NonEmptyDList a -> NonEmptyDList a

O(1). Append dlists

Other functions

concat1 :: NonEmpty (NonEmptyDList a) -> NonEmptyDList a

O(spine). Concatenate dlists

replicate :: Int -> a -> NonEmptyDList a

O(n). Create a dlist of the given number of elements.

Always creates a list with at least one element.

head :: NonEmptyDList a -> a

O(n). Return the head of the dlist

tail :: NonEmptyDList a -> [a]

O(n). Return the tail of the dlist

unfoldr :: (b -> (a, Maybe b)) -> b -> NonEmptyDList a

O(n). Unfoldr for dlists

map :: (a -> b) -> NonEmptyDList a -> NonEmptyDList b

O(n). Map over difference lists.