| Copyright | © 2017-2020 Oleg Grenrus 2020 Sean Leather |
|---|---|
| License | BSD-3-Clause |
| Maintainer | sean.leather@gmail.com |
| Stability | stable |
| Safe Haskell | Safe |
| Language | Haskell2010 |
Data.DList.DNonEmpty
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
- 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)
<>
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.
Instances
Conversion
fromNonEmpty :: NonEmpty a -> DNonEmpty a Source #
fromNonEmpty xs
is a
DNonEmpty
representing the
NonEmpty
xs
.
fromNonEmpty
obeys the laws:
toNonEmpty. fromNonEmpty =idfromNonEmpty .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=idfromNonEmpty. 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(toNonEmptyxs)
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(fromListxs)
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) =consx (toNonEmptyxs)
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) =toNonEmptyxs<>(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) =toNonEmptyxs<>toNonEmptyys
head :: DNonEmpty a -> a Source #
head xs
is the first element of
xs
.
\(\mathcal{O}\)
(
1
).
head
obeys the law:
head xs =head(toNonEmptyxs)
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(toNonEmptyxs)
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) =mapf (toNonEmptyxs)