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 |

## Synopsis

- data DList a where
- 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

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

pattern Nil :: DList a | A unidirectional pattern synonym for |

pattern Cons :: a -> [a] -> DList a | A unidirectional pattern synonym for |

## Instances

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