Data.DList.DNonEmpty

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.

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 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 xs is the non-empty list represented by xs.

toList obeys the law:

toList xs = toList (toNonEmpty xs)

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)

singleton x is a DNonEmpty with the single element x.

singleton obeys the law:

toNonEmpty (singleton x) = x :| []

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 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 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 xs is the first element of xs.

\mathcal{O}(1).

head obeys the law:

head xs = head (toNonEmpty xs)

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 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 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)