| 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
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
- 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).
Bundled Patterns
| 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 =idfromList .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=idfromList. 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.