dlist-1.0: Difference lists

Copyright | © 2006-2009 Don Stewart 2013-2020 Sean Leather
License | BSD-3-Clause
Maintainer | sean.leather@gmail.com
Stability | stable
Safe Haskell | Trustworthy
Language | Haskell2010

Data.DList

Contents

- Difference List Type
- Conversion
- Basic Functions

Description

A difference list is an abstraction representing a list that supports \(\mathcal{O}\)(`1`) `append` and `snoc` operations. This module provides the type for a difference list, `DList`, and a collection of supporting functions for (a) converting to and from lists and (b) operating on `DList`s efficiently.

Synopsis

- data DList a where
  - pattern Nil :: DList a
  - pattern Cons :: a -> [a] -> DList a
- fromList :: [a] -> DList a
- toList :: DList a -> [a]
- apply :: DList a -> [a] -> [a]
- empty :: DList a
- singleton :: a -> DList a
- cons :: a -> DList a -> DList a
- snoc :: DList a -> a -> DList a
- append :: DList a -> DList a -> DList a
- concat :: [DList a] -> DList a
- replicate :: Int -> a -> DList a
- head :: DList a -> a
- tail :: DList a -> [a]
- unfoldr :: (b -> Maybe (a, b)) -> b -> DList a
- foldr :: (a -> b -> b) -> b -> DList a -> b
- map :: (a -> b) -> DList a -> DList b
- intercalate :: DList a -> [DList a] -> DList a

# Difference List Type

data DList a where Source #

A difference list is an abstraction representing a list that supports \(\mathcal{O}\)(`1`) `append` and `snoc` operations, making it useful for replacing frequent applications of `++` such as logging and pretty printing (esp. if those uses of `++` are left-nested).

Bundled Patterns

pattern Nil :: DList a | A unidirectional pattern synonym for `empty`. This is implemented with `toList`.
pattern Cons :: a -> [a] -> DList a | A unidirectional pattern synonym for `cons`. This is implemented with `toList`.

#### Instances

Instances details

Alternative DList Source # |
Instance details Defined in Data.DList.Internal Methods empty :: DList a Source # (<|>) :: DList a -> DList a -> DList a Source # some :: DList a -> DList [a] Source # many :: DList a -> DList [a] Source #
Applicative DList Source # |
Instance details Defined in Data.DList.Internal Methods pure :: a -> DList a Source # (<*>) :: DList (a -> b) -> DList a -> DList b Source # liftA2 :: (a -> b -> c) -> DList a -> DList b -> DList c Source # (*>) :: DList a -> DList b -> DList b Source # (<*) :: DList a -> DList b -> DList a Source #
Functor DList Source # |
Instance details Defined in Data.DList.Internal Methods fmap :: (a -> b) -> DList a -> DList b Source # (<$) :: a -> DList b -> DList a Source #
Monad DList Source # |
Instance details Defined in Data.DList.Internal Methods (>>=) :: DList a -> (a -> DList b) -> DList b Source # (>>) :: DList a -> DList b -> DList b Source # return :: a -> DList a Source #
MonadPlus DList Source # |
Instance details Defined in Data.DList.Internal Methods mzero :: DList a Source # mplus :: DList a -> DList a -> DList a Source #
MonadFail DList Source # |
Instance details Defined in Data.DList.Internal Methods fail :: String -> DList a Source #
Foldable DList Source # |

Instance details

Defined in Data.DList.Internal

Methods

fold :: Monoid m => DList m -> m Source #

foldMap :: Monoid m => (a -> m) -> DList a -> m Source #

foldMap' :: Monoid m => (a -> m) -> DList a -> m Source #

foldr :: (a -> b -> b) -> b -> DList a -> b Source #

foldr' :: (a -> b -> b) -> b -> DList a -> b Source #

foldl :: (b -> a -> b) -> b -> DList a -> b Source #

foldl' :: (b -> a -> b) -> b -> DList a -> b Source #

foldr1 :: (a -> a -> a) -> DList a -> a Source #

foldl1 :: (a -> a -> a) -> DList a -> a Source #

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

null :: DList a -> Bool Source #

length :: DList a -> Int Source #

elem :: Eq a => a -> DList a -> Bool Source #

maximum :: Ord a => DList a -> a Source #

minimum :: Ord a => DList a -> a Source #

sum :: Num a => DList a -> a Source #

product :: Num a => DList a -> a Source #

Traversable DList Source # |
Instance details Defined in Data.DList.Internal Methods traverse :: Applicative f => (a -> f b) -> DList a -> f (DList b) Source # sequenceA :: Applicative f => DList (f a) -> f (DList a) Source # mapM :: Monad m => (a -> m b) -> DList a -> m (DList b) Source # sequence :: Monad m => DList (m a) -> m (DList a) Source #
NFData a => NFData (DList a) Source # |
Instance details Defined in Data.DList.Internal Methods rnf :: DList a -> () Source #
Monoid (DList a) Source # |
Instance details Defined in Data.DList.Internal Methods mempty :: DList a Source # mappend :: DList a -> DList a -> DList a Source # mconcat :: [DList a] -> DList a Source #
Semigroup (DList a) Source # |
Instance details Defined in Data.DList.Internal Methods (<>) :: DList a -> DList a -> DList a Source # sconcat :: NonEmpty (DList a) -> DList a Source # stimes :: Integral b => b -> DList a -> DList a Source #
a ~ Char => IsString (DList a) Source # |
Instance details Defined in Data.DList.Internal Methods fromString :: String -> DList a Source #
IsList (DList a) Source # |

Instance details

Defined in Data.DList.Internal

Associated Types

type Item (DList a) |
Instance details Defined in Data.DList.Internal type Item (DList a) = a

Methods

fromList :: [Item (DList a)] -> DList a Source #

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

toList :: DList a -> [Item (DList a)] Source #

Read a => Read (DList a) Source # |
Instance details Defined in Data.DList.Internal Methods readsPrec :: Int -> ReadS (DList a) Source # readList :: ReadS [DList a] Source # readPrec :: ReadPrec (DList a) Source # readListPrec :: ReadPrec [DList a] Source #
Show a => Show (DList a) Source # |
Instance details Defined in Data.DList.Internal Methods showsPrec :: Int -> DList a -> ShowS Source # show :: DList a -> String Source # showList :: [DList a] -> ShowS Source #
Eq a => Eq (DList a) Source # |
Instance details Defined in Data.DList.Internal Methods (==) :: DList a -> DList a -> Bool Source # (/=) :: DList a -> DList a -> Bool Source #
Ord a => Ord (DList a) Source # |
Instance details Defined in Data.DList.Internal Methods compare :: DList a -> DList a -> Ordering Source # (<) :: DList a -> DList a -> Bool Source # (<=) :: DList a -> DList a -> Bool Source # (>) :: DList a -> DList a -> Bool Source # (>=) :: DList a -> DList a -> Bool Source # max :: DList a -> DList a -> DList a Source # min :: DList a -> DList a -> DList a Source #
type Item (DList a) Source # |
Instance details Defined in Data.DList.Internal type Item (DList a) = a

# Conversion

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

`fromList xs` is a `DList` representing the list `xs`.

`fromList` obeys the laws:

    toList . fromList = id
    fromList . toList = id

This function is implemented with `++`. Repeated uses of `fromList` 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 `DList` representation and library:

    fromList . f . toList

More likely, you will convert from a list, perform some operation on the `DList`, and convert back to a list:

    toList . g . fromList

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

`toList xs` is the list represented by `xs`.

`toList` obeys the laws:

    toList . fromList = id
    fromList . toList = id

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

apply :: DList a -> [a] -> [a] Source #

`apply xs ys` is the list represented by the `xs` after appending `ys` to it.

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

`apply` obeys the law:

    apply xs ys = toList xs ++ ys

# Basic Functions

empty :: DList a Source #

`empty` is a `DList` with no elements.

`empty` obeys the law:

    toList empty = []

singleton :: a -> DList a Source #

`singleton x` is a `DList` with the single element `x`.

`singleton` obeys the law:

    toList (singleton x) = [x]

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

`cons x xs` is a `DList` with the `head` `x` and the `tail` `xs`.

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

`cons` obeys the law:

    toList (cons x xs) = x : toList xs

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

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

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

`snoc` obeys the law:

    toList (snoc xs x) = toList xs ++ [x]

append :: DList a -> DList a -> DList a Source #

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

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

`append` obeys the law:

    toList (append xs ys) = toList xs ++ toList ys

concat :: [DList a] -> DList a Source #

`concat xss` is a `DList` representing the concatenation of all `DList`s in the list `xss`.

\(\mathcal{O}\)(``length` xss`).

`concat` obeys the law:

    toList (concat xss) = concat (map toList xss)

replicate :: Int -> a -> DList a Source #

`replicate n x` is a `DList` of length `n` with `x` as the value of every element.

\(\mathcal{O}\)(`n`).

`replicate` obeys the law:

    toList (replicate n x) = replicate n x

head :: DList a -> a Source #

`head xs` is the first element of `xs`. If `xs` is empty, an `error` is raised.

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

`head` obeys the law:

    head xs = head (toList xs)

tail :: DList a -> [a] Source #

`tail xs` is a list of the elements in `xs` excluding the first element. If `xs` is empty, an `error` is raised.

\(\mathcal{O}\)(``length` (`toList` xs)`).

`tail` obeys the law:

    tail xs = tail (toList xs)

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

`unfoldr f z` is the `DList` 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:

    toList (unfoldr f z) = unfoldr f z

foldr :: (a -> b -> b) -> b -> DList a -> b Source #

`foldr f z xs` is the right-fold of `f` over `xs`.

\(\mathcal{O}\)(``length` (`toList` xs)`).

`foldr` obeys the law:

    foldr f z xs = foldr f z (toList xs)

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

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

\(\mathcal{O}\)(``length` (`toList` xs)`).

`map` obeys the law:

    toList (map f xs) = map f (toList xs)

intercalate :: DList a -> [DList a] -> DList a Source #

`intercalate xs xss` is the concatenation of `xss` after the insertion of `xs` between every pair of elements.

\(\mathcal{O}\)(``length` xss`).

`intercalate` obeys the law:

    toList (intercalate xs xss) = intercalate (toList xs) (map toList xss)