Stability | experimental |
---|---|
Maintainer | dons@galois.com |
Self adapting polymorphic lists.
This library statically specializes the polymorphic container representation of lists to specific, more efficient representations, when instantiated with particular monomorphic types. It does this via an associated more efficient data type for each pair of elements you wish to store in your container.
The resulting list structures use less space, and functions on them tend to be faster, than regular lists.
Instead of representing '[1..5] :: [Int]' as:
(:) / \ / \ I# 1# (:) / \ / \ I# 2# (:) / \ / \ I# 3# []
The compiler will select an associated data type that packs better, via the class instances, resulting in:
ConsInt 1# | ConsInt 2# | ConsInt 3# | []
The user however, still sees a polymorphic list type.
This list type currently doesn't fuse.
- class AdaptList a where
- toList :: AdaptList a => List a -> [a]
- fromList :: AdaptList a => [a] -> List a
- enumFromToList :: (AdaptList a, Ord a, Enum a) => a -> a -> List a
- uncons :: AdaptList a => List a -> Maybe (a, List a)
- (++) :: AdaptList a => List a -> List a -> List a
- last :: AdaptList a => List a -> a
- init :: AdaptList a => List a -> List a
- length :: AdaptList a => List a -> Int
- map :: (AdaptList a, AdaptList b) => (a -> b) -> List a -> List b
- reverse :: AdaptList a => List a -> List a
- intersperse :: AdaptList a => a -> List a -> List a
- intercalate :: (AdaptList (List a), AdaptList a) => List a -> List (List a) -> List a
- foldl :: AdaptList b => (a -> b -> a) -> a -> List b -> a
- foldl1 :: AdaptList a => (a -> a -> a) -> List a -> a
- foldr :: AdaptList a => (a -> b -> b) -> b -> List a -> b
- foldr1 :: AdaptList a => (a -> a -> a) -> List a -> a
- concat :: (AdaptList (List a), AdaptList a) => List (List a) -> List a
- concatMap :: (AdaptList a1, AdaptList a) => (a -> List a1) -> List a -> List a1
- and :: List Bool -> Bool
- or :: List Bool -> Bool
- any :: AdaptList a => (a -> Bool) -> List a -> Bool
- all :: AdaptList a => (a -> Bool) -> List a -> Bool
- sum :: (AdaptList a, Num a) => List a -> a
- product :: (AdaptList a, Num a) => List a -> a
- maximum :: (AdaptList a, Ord a) => List a -> a
- minimum :: (AdaptList a, Ord a) => List a -> a
- scanl :: (AdaptList b, AdaptList a) => (a -> b -> a) -> a -> List b -> List a
- scanl1 :: AdaptList a => (a -> a -> a) -> List a -> List a
- scanr :: (AdaptList a, AdaptList b) => (a -> b -> b) -> b -> List a -> List b
- scanr1 :: AdaptList a => (a -> a -> a) -> List a -> List a
- iterate :: AdaptList a => (a -> a) -> a -> List a
- repeat :: AdaptList a => a -> List a
- replicate :: AdaptList a => Int -> a -> List a
- cycle :: AdaptList a => List a -> List a
- unfoldr :: AdaptList a => (b -> Maybe (a, b)) -> b -> List a
- take :: AdaptList a => Int -> List a -> List a
- drop :: AdaptList a => Int -> List a -> List a
- splitAt :: AdaptList a => Int -> List a -> (List a, List a)
- elem :: (AdaptList a, Eq a) => a -> List a -> Bool
- notElem :: (AdaptList a, Eq a) => a -> List a -> Bool
- filter :: AdaptList a => (a -> Bool) -> List a -> List a
- zip :: (AdaptPair a b, AdaptList a, AdaptList b, AdaptList (Pair a b)) => List a -> List b -> List (Pair a b)
- errorEmptyList :: String -> a
- moduleError :: String -> String -> a
- bottom :: a
The adaptive list class-associated type
Representation-improving polymorphic lists.
The empty list
cons :: a -> List a -> List aSource
Prepend a value onto a list
Is the list empty?
The first element of the list
tail :: List a -> List aSource
The tail of the list
Basic Interface
enumFromToList :: (AdaptList a, Ord a, Enum a) => a -> a -> List aSource
O(n), construct a list by enumerating a range
uncons :: AdaptList a => List a -> Maybe (a, List a)Source
O(1), uncons, take apart a list into the head and tail.
(++) :: AdaptList a => List a -> List a -> List aSource
O(n), Append two lists, i.e.,
[x1, ..., xm] ++ [y1, ..., yn] == [x1, ..., xm, y1, ..., yn] [x1, ..., xm] ++ [y1, ...] == [x1, ..., xm, y1, ...]
If the first list is not finite, the result is the first list. The spine of the first list argument must be copied.
last :: AdaptList a => List a -> aSource
O(n), Extract the last element of a list, which must be finite and non-empty.
init :: AdaptList a => List a -> List aSource
O(n). Return all the elements of a list except the last one. The list must be finite and non-empty.
List transformations
map :: (AdaptList a, AdaptList b) => (a -> b) -> List a -> List bSource
O(n). map
f xs
is the list obtained by applying f
to each element
of xs
, i.e.,
map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn] map f [x1, x2, ...] == [f x1, f x2, ...]
Properties:
map f . map g = map (f . g) map f (repeat x) = repeat (f x) map f (replicate n x) = replicate n (f x)
reverse :: AdaptList a => List a -> List aSource
O(n). reverse
xs
returns the elements of xs
in reverse order.
xs
must be finite. Will fuse as a consumer only.
intersperse :: AdaptList a => a -> List a -> List aSource
O(n). The intersperse
function takes an element and a list and
`intersperses' that element between the elements of the list.
For example,
intersperse ',' "abcde" == "a,b,c,d,e"
intercalate :: (AdaptList (List a), AdaptList a) => List a -> List (List a) -> List aSource
O(n). intercalate
xs xss
is equivalent to (
.
It inserts the list concat
(intersperse
xs xss))xs
in between the lists in xss
and concatenates the
result.
intercalate = concat . intersperse
Reducing lists (folds)
foldl :: AdaptList b => (a -> b -> a) -> a -> List b -> aSource
O(n). foldl
, applied to a binary operator, a starting value (typically
the left-identity of the operator), and a list, reduces the list
using the binary operator, from left to right:
foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
The list must be finite. The accumulator is whnf strict.
foldr :: AdaptList a => (a -> b -> b) -> b -> List a -> bSource
O(n). foldr
, applied to a binary operator, a starting value (typically
the right-identity of the operator), and a list, reduces the list
using the binary operator, from right to left:
foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
Special folds
concat :: (AdaptList (List a), AdaptList a) => List (List a) -> List aSource
O(n). Concatenate a list of lists. concat :: [[a]] -> [a]
concatMap :: (AdaptList a1, AdaptList a) => (a -> List a1) -> List a -> List a1Source
O(n), fusion. Map a function over a list and concatenate the results.
any :: AdaptList a => (a -> Bool) -> List a -> BoolSource
O(n). Applied to a predicate and a list, any
determines if any element
of the list satisfies the predicate.
all :: AdaptList a => (a -> Bool) -> List a -> BoolSource
Applied to a predicate and a list, all
determines if all elements
of the list satisfy the predicate.
sum :: (AdaptList a, Num a) => List a -> aSource
O(n), fusion. The sum
function computes the sum of a finite list of numbers.
product :: (AdaptList a, Num a) => List a -> aSource
O(n),fusion. The product
function computes the product of a finite list of numbers.
maximum :: (AdaptList a, Ord a) => List a -> aSource
O(n). maximum
returns the maximum value from a list,
which must be non-empty, finite, and of an ordered type.
It is a special case of Data.List.maximumBy
, which allows the
programmer to supply their own comparison function.
minimum :: (AdaptList a, Ord a) => List a -> aSource
O(n). minimum
returns the minimum value from a list,
which must be non-empty, finite, and of an ordered type.
It is a special case of Data.List.minimumBy
, which allows the
programmer to supply their own comparison function.
Building lists
Scans
Infinite lists
iterate :: AdaptList a => (a -> a) -> a -> List aSource
O(n), iterate
f x
returns an infinite list of repeated applications
of f
to x
:
iterate f x == [x, f x, f (f x), ...]
repeat :: AdaptList a => a -> List aSource
O(n). repeat
x
is an infinite list, with x
the value of every element.
replicate :: AdaptList a => Int -> a -> List aSource
O(n). replicate
n x
is a list of length n
with x
the value of
every element.
It is an instance of the more general Data.List.genericReplicate
,
in which n
may be of any integral type.
cycle :: AdaptList a => List a -> List aSource
fusion. cycle
ties a finite list into a circular one, or equivalently,
the infinite repetition of the original list. It is the identity
on infinite lists.
Unfolding
unfoldr :: AdaptList a => (b -> Maybe (a, b)) -> b -> List aSource
The unfoldr
function is a `dual' to foldr
: while foldr
reduces a list to a summary value, unfoldr
builds a list from
a seed value. The function takes the element and returns Nothing
if it is done producing the list or returns Just
(a,b)
, in which
case, a
is a prepended to the list and b
is used as the next
element in a recursive call. For example,
iterate f == unfoldr (\x -> Just (x, f x))
In some cases, unfoldr
can undo a foldr
operation:
unfoldr f' (foldr f z xs) == xs
if the following holds:
f' (f x y) = Just (x,y) f' z = Nothing
A simple use of unfoldr:
unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10 [10,9,8,7,6,5,4,3,2,1]
TODO: AdaptPair state.
Sublists
Extracting sublists
take :: AdaptList a => Int -> List a -> List aSource
O(n). take
n
, applied to a list xs
, returns the prefix of xs
of length n
, or xs
itself if n >
:
length
xs
take 5 "Hello World!" == "Hello" take 3 [1,2,3,4,5] == [1,2,3] take 3 [1,2] == [1,2] take 3 [] == [] take (-1) [1,2] == [] take 0 [1,2] == []
It is an instance of the more general Data.List.genericTake
,
in which n
may be of any integral type.
drop :: AdaptList a => Int -> List a -> List aSource
O(n). drop
n xs
returns the suffix of xs
after the first n
elements, or []
if n >
:
length
xs
drop 6 "Hello World!" == "World!" drop 3 [1,2,3,4,5] == [4,5] drop 3 [1,2] == [] drop 3 [] == [] drop (-1) [1,2] == [1,2] drop 0 [1,2] == [1,2]
It is an instance of the more general Data.List.genericDrop
,
in which n
may be of any integral type.
splitAt :: AdaptList a => Int -> List a -> (List a, List a)Source
splitAt
n xs
returns a tuple where first element is xs
prefix of
length n
and second element is the remainder of the list:
splitAt 6 "Hello World!" == ("Hello ","World!") splitAt 3 [1,2,3,4,5] == ([1,2,3],[4,5]) splitAt 1 [1,2,3] == ([1],[2,3]) splitAt 3 [1,2,3] == ([1,2,3],[]) splitAt 4 [1,2,3] == ([1,2,3],[]) splitAt 0 [1,2,3] == ([],[1,2,3]) splitAt (-1) [1,2,3] == ([],[1,2,3])
It is equivalent to (
.
take
n xs, drop
n xs)splitAt
is an instance of the more general Data.List.genericSplitAt
,
in which n
may be of any integral type.
Searching lists
Searching by equality
filter :: AdaptList a => (a -> Bool) -> List a -> List aSource
O(n). filter
, applied to a predicate and a list, returns the list of
those elements that satisfy the predicate; i.e.,
filter p xs = [ x | x <- xs, p x]
Properties:
filter p (filter q s) = filter (\x -> q x && p x) s
Zipping and unzipping lists
zip :: (AdaptPair a b, AdaptList a, AdaptList b, AdaptList (Pair a b)) => List a -> List b -> List (Pair a b)Source
O(n),fusion. zip
takes two lists and returns a list of
corresponding pairs. If one input list is short, excess elements of
the longer list are discarded.
Properties:
zip a b = zipWith (,) a b
errorEmptyList :: String -> aSource
moduleError :: String -> String -> aSource