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