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.

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.

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)

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"

O(n). intercalate xs xss is equivalent to (concat (intersperse xs xss)). It inserts the list xs in between the lists in xss and concatenates the result.

 intercalate = concat . intersperse

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.

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

O(n). scanl is similar to foldl, but returns a list of successive reduced values from the left:

 scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]

Properties:

 last (scanl f z xs) == foldl f z x

O(n). scanl1 is a variant of scanl that has no starting value argument:

 scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]

O(n). scanr is the right-to-left dual of scanl. Properties:

 head (scanr f z xs) == foldr f z xs

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

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.

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.

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

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

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