Data.DList.DNonEmpty

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.

Non-Empty Difference List Type

data DNonEmpty a

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

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

Defined in Data.DList.DNonEmpty.Internal

Methods

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

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

Applicative DNonEmpty

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

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)

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)

Defined in Data.DList.DNonEmpty.Internal

Methods

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

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

Ord a => Ord (DNonEmpty a)

Defined in Data.DList.DNonEmpty.Internal

Methods

compare :: DNonEmpty a -> DNonEmpty a -> Ordering

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

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

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

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

max :: DNonEmpty a -> DNonEmpty a -> DNonEmpty a

min :: DNonEmpty a -> DNonEmpty a -> DNonEmpty a

Read a => Read (DNonEmpty a)

Defined in Data.DList.DNonEmpty.Internal

Methods

readsPrec :: Int -> ReadS (DNonEmpty a)

readList :: ReadS [DNonEmpty a]

readPrec :: ReadPrec (DNonEmpty a)

readListPrec :: ReadPrec [DNonEmpty a]

Show a => Show (DNonEmpty a)

Defined in Data.DList.DNonEmpty.Internal

Methods

showsPrec :: Int -> DNonEmpty a -> ShowS

show :: DNonEmpty a -> String

showList :: [DNonEmpty a] -> ShowS

a ~ Char => IsString (DNonEmpty a)

Defined in Data.DList.DNonEmpty.Internal

Methods

fromString :: String -> DNonEmpty a

Semigroup (DNonEmpty a)

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)

Defined in Data.DList.DNonEmpty.Internal

Methods

rnf :: DNonEmpty a -> ()

type Item (DNonEmpty a)

Defined in Data.DList.DNonEmpty.Internal

type Item (DNonEmpty a) = a

Conversion

fromNonEmpty :: NonEmpty a -> DNonEmpty a

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

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]

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

toList obeys the law:

toList xs = toList (toNonEmpty xs)

fromList :: [a] -> DNonEmpty a

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

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

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

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

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

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

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

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

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)