dlist-1.0: Difference lists

Copyright© 2017-2020 Oleg Grenrus 2020 Sean Leather
LicenseBSD-3-Clause
Maintainersean.leather@gmail.com
Stabilitystable
Safe HaskellSafe
LanguageHaskell2010

Data.DList.DNonEmpty

Contents

Description

A non-empty difference list is a difference list paired with a head element. Like the difference list, it supports \(\mathcal{O}\)(1) append and snoc operations.

This module provides the type for a non-empty difference list, DNonEmpty, and a collection of supporting functions for (a) converting to and from NonEmpty and DList and (b) operating efficiently on DNonEmpty values. The functions also retain the non-strict semantics of NonEmpty.

Synopsis

Non-Empty Difference List Type

data DNonEmpty a Source #

A non-empty difference list is a pair of a head element and a (possibly empty) difference list.

Just as DList is a representation of a list, so is DNonEmpty a representation of a NonEmpty. DNonEmpty supports \(\mathcal{O}\)(1) append and snoc operations, making it useful for replacing frequent applications of <> on NonEmpty (which is implemented with ++), especially if those uses are left-nested (e.g. (a <> b) <> c ).

Unlike DList, DNonEmpty is not an abstract type: its constructor is exported. An alternative definition of DNonEmpty is:

newtype DNonEmpty a = DNonEmpty ([a] -> NonEmpty a)

This type would need to be abstract to avoid producing DNonEmpty values that are not isomorphic to NonEmpty values. However, this type would also require some functions (such as map) to be implemented with fromNonEmpty (and thus ++), which could introduce efficiencies.

Constructors

a :| (DList a) infixr 5 
Instances
Monad DNonEmpty Source # 
Instance details

Defined in Data.DList.DNonEmpty.Internal

Methods

(>>=) :: DNonEmpty a -> (a -> DNonEmpty b) -> DNonEmpty b #

(>>) :: DNonEmpty a -> DNonEmpty b -> DNonEmpty b #

return :: a -> DNonEmpty a #

fail :: String -> DNonEmpty a #

Functor DNonEmpty Source # 
Instance details

Defined in Data.DList.DNonEmpty.Internal

Methods

fmap :: (a -> b) -> DNonEmpty a -> DNonEmpty b #

(<$) :: a -> DNonEmpty b -> DNonEmpty a #

Applicative DNonEmpty Source # 
Instance details

Defined in Data.DList.DNonEmpty.Internal

Methods

pure :: a -> DNonEmpty a #

(<*>) :: DNonEmpty (a -> b) -> DNonEmpty a -> DNonEmpty b #

liftA2 :: (a -> b -> c) -> DNonEmpty a -> DNonEmpty b -> DNonEmpty c #

(*>) :: DNonEmpty a -> DNonEmpty b -> DNonEmpty b #

(<*) :: DNonEmpty a -> DNonEmpty b -> DNonEmpty a #

Foldable DNonEmpty Source # 
Instance details

Defined in Data.DList.DNonEmpty.Internal

Methods

fold :: Monoid m => DNonEmpty m -> m #

foldMap :: Monoid m => (a -> m) -> DNonEmpty a -> m #

foldr :: (a -> b -> b) -> b -> DNonEmpty a -> b #

foldr' :: (a -> b -> b) -> b -> DNonEmpty a -> b #

foldl :: (b -> a -> b) -> b -> DNonEmpty a -> b #

foldl' :: (b -> a -> b) -> b -> DNonEmpty a -> b #

foldr1 :: (a -> a -> a) -> DNonEmpty a -> a #

foldl1 :: (a -> a -> a) -> DNonEmpty a -> a #

toList :: DNonEmpty a -> [a] #

null :: DNonEmpty a -> Bool #

length :: DNonEmpty a -> Int #

elem :: Eq a => a -> DNonEmpty a -> Bool #

maximum :: Ord a => DNonEmpty a -> a #

minimum :: Ord a => DNonEmpty a -> a #

sum :: Num a => DNonEmpty a -> a #

product :: Num a => DNonEmpty a -> a #

IsList (DNonEmpty a) Source # 
Instance details

Defined in Data.DList.DNonEmpty.Internal

Associated Types

type Item (DNonEmpty a) :: Type #

Methods

fromList :: [Item (DNonEmpty a)] -> DNonEmpty a #

fromListN :: Int -> [Item (DNonEmpty a)] -> DNonEmpty a #

toList :: DNonEmpty a -> [Item (DNonEmpty a)] #

Eq a => Eq (DNonEmpty a) Source # 
Instance details

Defined in Data.DList.DNonEmpty.Internal

Methods

(==) :: DNonEmpty a -> DNonEmpty a -> Bool #

(/=) :: DNonEmpty a -> DNonEmpty a -> Bool #

Ord a => Ord (DNonEmpty a) Source # 
Instance details

Defined in Data.DList.DNonEmpty.Internal

Read a => Read (DNonEmpty a) Source # 
Instance details

Defined in Data.DList.DNonEmpty.Internal

Show a => Show (DNonEmpty a) Source # 
Instance details

Defined in Data.DList.DNonEmpty.Internal

a ~ Char => IsString (DNonEmpty a) Source # 
Instance details

Defined in Data.DList.DNonEmpty.Internal

Methods

fromString :: String -> DNonEmpty a #

Semigroup (DNonEmpty a) Source # 
Instance details

Defined in Data.DList.DNonEmpty.Internal

Methods

(<>) :: DNonEmpty a -> DNonEmpty a -> DNonEmpty a #

sconcat :: NonEmpty (DNonEmpty a) -> DNonEmpty a #

stimes :: Integral b => b -> DNonEmpty a -> DNonEmpty a #

NFData a => NFData (DNonEmpty a) Source # 
Instance details

Defined in Data.DList.DNonEmpty.Internal

Methods

rnf :: DNonEmpty a -> () #

type Item (DNonEmpty a) Source # 
Instance details

Defined in Data.DList.DNonEmpty.Internal

type Item (DNonEmpty a) = a

Conversion

fromNonEmpty :: NonEmpty a -> DNonEmpty a Source #

fromNonEmpty xs is a DNonEmpty representing the NonEmpty xs.

fromNonEmpty obeys the laws:

toNonEmpty . fromNonEmpty = id
fromNonEmpty . toNonEmpty = id

As with fromList, this function is implemented with ++. Repeated uses of fromNonEmpty are just as inefficient as repeated uses of ++. If you find yourself doing some form of the following (possibly indirectly), you may not be taking advantage of the DNonEmpty representation and library:

fromNonEmpty . f . toNonEmpty

More likely, you will convert from a NonEmpty, perform some operation on the DNonEmpty, and convert back to a NonEmpty:

toNonEmpty . g . fromNonEmpty

toNonEmpty :: DNonEmpty a -> NonEmpty a Source #

toNonEmpty xs is the NonEmpty represented by xs.

toNonEmpty obeys the laws:

toNonEmpty . fromNonEmpty = id
fromNonEmpty . toNonEmpty = id

As with toList, evaluating toNonEmpty xs may “collapse” the chain of function composition underlying many DList functions (append in particular) used to construct the tail of xs. This may affect any efficiency you achieved due to laziness in the construction.

toList :: DNonEmpty a -> [a] Source #

toList xs is the non-empty list represented by xs.

toList obeys the law:

toList xs = toList (toNonEmpty xs)

fromList :: [a] -> DNonEmpty a Source #

fromList xs is a DNonEmpty representing the list xs. If xs is empty, an error is raised.

fromList obeys the law:

fromList xs = fromNonEmpty (fromList xs)

Basic Functions

singleton :: a -> DNonEmpty a Source #

singleton x is a DNonEmpty with the single element x.

singleton obeys the law:

toNonEmpty (singleton x) = x :| []

cons :: a -> DNonEmpty a -> DNonEmpty a infixr 9 Source #

cons x xs is a DNonEmpty with the head x and the tail xs.

\(\mathcal{O}\)(1).

cons obeys the law:

toNonEmpty (cons x xs) = cons x (toNonEmpty xs)

snoc :: DNonEmpty a -> a -> DNonEmpty a infixl 9 Source #

snoc xs x is a DNonEmpty with the initial DNonEmpty xs and the last element x.

\(\mathcal{O}\)(1).

snoc obeys the law:

toNonEmpty (snoc xs x) = toNonEmpty xs <> (x :| [])

append :: DNonEmpty a -> DNonEmpty a -> DNonEmpty a Source #

append xs ys is a DNonEmpty obtained from the concatenation of the elements of xs and ys.

\(\mathcal{O}\)(1).

append obeys the law:

toNonEmpty (append xs ys) = toNonEmpty xs <> toNonEmpty ys

head :: DNonEmpty a -> a Source #

head xs is the first element of xs.

\(\mathcal{O}\)(1).

head obeys the law:

head xs = head (toNonEmpty xs)

tail :: DNonEmpty a -> DList a Source #

tail xs is a DList of the elements in xs excluding the first element.

\(\mathcal{O}\)(1).

tail obeys the law:

toList (tail xs) = tail (toNonEmpty xs)

unfoldr :: (b -> (a, Maybe b)) -> b -> DNonEmpty a Source #

unfoldr f z is the DNonEmpty constructed from the recursive application of f. The recursion starts with the seed value z and ends when, for some z' : b, f z' == Nothing.

\(\mathcal{O}\)(length (unfoldr f z)).

unfoldr obeys the law:

toNonEmpty (unfoldr f z) = unfoldr f z

map :: (a -> b) -> DNonEmpty a -> DNonEmpty b Source #

map f xs is the DNonEmpty obtained by applying f to each element of xs.

\(\mathcal{O}\)(length (toNonEmpty xs)).

map obeys the law:

toNonEmpty (map f xs) = map f (toNonEmpty xs)