Copyright | © 2017-2020 Oleg Grenrus 2020 Sean Leather |
---|---|

License | BSD-3-Clause |

Maintainer | sean.leather@gmail.com |

Stability | stable |

Safe Haskell | Safe |

Language | Haskell2010 |

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

- data DNonEmpty a = a :| (DList a)
- fromNonEmpty :: NonEmpty a -> DNonEmpty a
- toNonEmpty :: DNonEmpty a -> NonEmpty a
- toList :: DNonEmpty a -> [a]
- fromList :: [a] -> DNonEmpty a
- singleton :: a -> DNonEmpty a
- cons :: a -> DNonEmpty a -> DNonEmpty a
- snoc :: DNonEmpty a -> a -> DNonEmpty a
- append :: DNonEmpty a -> DNonEmpty a -> DNonEmpty a
- head :: DNonEmpty a -> a
- tail :: DNonEmpty a -> DList a
- unfoldr :: (b -> (a, Maybe b)) -> b -> DNonEmpty a
- map :: (a -> b) -> DNonEmpty a -> DNonEmpty b

# Non-Empty Difference List Type

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)

`<>`

cUnlike `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.

#### Instances

# 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:

toListxs =`toList`

(`toNonEmpty`

xs)

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

** fromList xs** is a

`DNonEmpty`

representing the list **. If**

`xs`

`xs`

is
empty, an `error`

is raised.`fromList`

obeys the law:

fromListxs =`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`

(singletonx) = x`:|`

[]

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

** cons x xs** is a

`DNonEmpty`

with the `head`

**and the**

`x`

`tail`

**.**

`xs`

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

).

`cons`

obeys the law:

`toNonEmpty`

(consx xs) =`cons`

x (`toNonEmpty`

xs)

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

** snoc xs x** is a

`DNonEmpty`

with the initial `DNonEmpty`

**and the last element**

`xs`

**.**

`x`

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

).

`snoc`

obeys the law:

`toNonEmpty`

(snocxs 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 **and**

`xs`

**.**

`ys`

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

).

`append`

obeys the law:

`toNonEmpty`

(appendxs 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:

headxs =`head`

(`toNonEmpty`

xs)

tail :: DNonEmpty a -> DList a Source #

** tail xs** is a

`DList`

of the elements in **excluding the first element.**

`xs`

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

).

`tail`

obeys the law:

`toList`

(tailxs) =`tail`

(`toNonEmpty`

xs)

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

** map f xs** is the

`DNonEmpty`

obtained by applying **to each element of**

`f`

**.**

`xs`

\(\mathcal{O}\)(

).`length`

(`toNonEmpty`

xs)

`map`

obeys the law:

`toNonEmpty`

(mapf xs) =`map`

f (`toNonEmpty`

xs)