Maintainer | jameshfisher@gmail.com |
---|---|
Safe Haskell | Safe |
This module provides an infinite list type and operations thereon.
Haskell has two outstanding features:
- laziness, which in particular allows infinite data structures;
- a very strong type system.
In that light, it's a bit embarrassing that its default libraries do not allow
one to express the infinitude of, say, a list. For example, repeat
has type a → [a]
, when it of course should not return a finite list.
This module defines an infinite list data structure and provides all the standard list-manipulating functions that make sense on them. The advantages of using this over a standard list are:
- Type safety and clarity.
We are prevented from using nonsensical functions on infinite lists.
These include the functions:
last
,init
,null
,length
,foldl
,scanr
,scanl
,replicate
,reverse
,any
(etc.),isSuffixOf
, 'Data.List.(\)',union
,unionBy
,intersect
,intersectBy
,transpose
,deleteFirstsBy
,subsequences
,nonEmptySubsequences
,permutations
,sort
,sortBy
,sum
(etc.),elem
(etc.),lookup
,findIndex
,elemIndex
,isInfixOf
,nub
. - No pattern-matching on nil.
Where you can identify that
[]
will never be present, using a list forces you to either write clunky error-generating pattern matches, or alternatively put up with compiler warnings about incompete pattern matches. Code is simplified. - Faster code. We do not need or want runtime pattern-matches on a data constructor which will never occur. Haskell compilers love single-constructor datatypes: http://www.haskell.org/haskellwiki/Performance/Data_types#Single-constructor_datatypes
- data InfList a = a ::: (InfList a)
- type Pred a = a -> Bool
- iterate :: (a -> a) -> a -> InfList a
- repeat :: a -> InfList a
- cycle :: [a] -> InfList a
- head :: InfList a -> a
- tail :: InfList a -> InfList a
- toList :: InfList a -> [a]
- fromList :: [a] -> InfList a
- map :: (a -> b) -> InfList a -> InfList b
- mapAccumL :: (acc -> a -> (acc, b)) -> acc -> InfList a -> InfList b
- foldr :: (a -> b -> b) -> InfList a -> b
- unfoldr :: (a -> (b, a)) -> a -> InfList b
- intersperse :: a -> InfList a -> InfList a
- intercalate :: [a] -> InfList [a] -> InfList a
- (+++) :: [a] -> InfList a -> InfList a
- concatMap :: (a -> [b]) -> InfList a -> InfList b
- concat :: InfList [a] -> InfList a
- splitAt :: Int -> InfList a -> ([a], InfList a)
- span :: Pred a -> InfList a -> ([a], InfList a)
- break :: Pred a -> InfList a -> ([a], InfList a)
- groupBy :: (a -> a -> Bool) -> InfList a -> InfList [a]
- group :: Eq a => InfList a -> InfList [a]
- partition :: Pred a -> InfList a -> (InfList a, InfList a)
- isPrefixOf :: Eq a => [a] -> InfList a -> Bool
- stripPrefix :: Eq a => [a] -> InfList a -> Maybe (InfList a)
- inits :: InfList a -> InfList [a]
- tails :: InfList a -> InfList (InfList a)
- take :: Int -> InfList a -> [a]
- drop :: Int -> InfList a -> InfList a
- takeWhile :: Pred a -> InfList a -> [a]
- dropWhile :: Pred a -> InfList a -> InfList a
- zip :: InfList a -> InfList b -> InfList (a, b)
- zip3 :: InfList a -> InfList b -> InfList c -> InfList (a, b, c)
- zipWith :: (a -> b -> c) -> InfList a -> InfList b -> InfList c
- zipWith3 :: (a -> b -> c -> d) -> InfList a -> InfList b -> InfList c -> InfList d
- unzip :: InfList (a, b) -> (InfList a, InfList b)
- unzip3 :: InfList (a, b, c) -> (InfList a, InfList b, InfList c)
- filter :: Pred a -> InfList a -> InfList a
- deleteBy :: Eq a => Pred a -> InfList a -> InfList a
- delete :: Eq a => a -> InfList a -> InfList a
- (!!!) :: InfList a -> Int -> a
- findIndices :: Pred a -> InfList a -> InfList Int
- elemIndices :: Eq a => a -> InfList a -> InfList Int
Data type
The infinite list data type.
This is identical to the normal list data type
with the sole exception that it lacks the []
constructor.
Type synonyms
Infinite-list producer replacements
:: (a -> a) | the element-generating function |
-> a | the initial element |
-> InfList a | the infinite list of elements |
Repeatedly apply a generating function on an initial value, generating an infinite list.
:: a | The list element |
-> InfList a | the infinite list where each element is that element |
Given a list element, use that as every element in an infinite list.
:: [a] | A non-empty finite list |
-> InfList a | The elements of that list repeated infinitely |
Repeat the elements of a non-empty finite list.
Operations on InfList
Accessors
:: InfList a | the list |
-> a | its first element |
Get the first element of a list. This is guaranteed to exist.
Get the tail of a list. This is guaranteed to exist.
Conversion to and from lists
Convert an InfList
to an infinite list.
Use sparingly.
:: [a] | an infinite list |
-> InfList a | the corresponding InfList |
Convert an infinite list to an InfList
.
Throws an error if the given list runs out of elements.
Use sparingly.
Maps
:: (a -> b) | an element mapping function |
-> InfList a | a list of elements |
-> InfList b | the result of applying the function to each list element |
Apply a function to each element of the list, yielding a new list of the results.
:: (acc -> a -> (acc, b)) | The mapping/accumulating function |
-> acc | The initial accumulator |
-> InfList a | An infinite list |
-> InfList b | The mapped list |
Applies a function to each element of a list, passing an accumulating
parameter from left to right, returning a new list.
This is not quite the same as mapAccumL
: there is no final
accumulator returned.
Folds
Catamorphism.
This is not the same as foldr
on lists,
as it contains no base value.
:: (a -> (b, a)) | The unfolding function |
-> a | The seed value |
-> InfList b | The unfolded list |
Build a list from a seed value. The iterating function takes
the seed value and produces the next element in the list along with
a new seed value to use for the next element.
Not the same as unfoldr
.
Concatenating, interspersing, glueing
:: a | The element to place between |
-> InfList a | The list to intersperse |
-> InfList a | The interspersed list |
Place a given element between every adjacent two elements of a given infinite list.
:: [a] | The separating list |
-> InfList [a] | The infinite list to intercalate |
-> InfList a | The infinite list intercalated with the separating list |
Given an infinite list of finite lists, intersperse the infinite list with a given finite list, and concatenate it.
:: [a] | a finite list |
-> InfList a | an infinite list |
-> InfList a | the finite list prepended to the infinite list |
Prepend a finite list to a infinite list yielding a new infinite list.
:: (a -> [b]) | the element expanding function |
-> InfList a | a list of those elements |
-> InfList b | the concatenation of the expansion of each element |
Expand all elements of an infinite list into finite lists and concatenate them.
Concatenate an infinite list of finite lists into an infinite list of elements. That is, remove one level of nesting.
Splitting
Given a natural number, get a two-tuple of the finite list of that many elements from the start of a given infinite list, and the infinite list that follows them.
:: Pred a | a predicate on list elements |
-> InfList a | a list of those elements |
-> ([a], InfList a) | the longest satisfying prefix, and the rest |
Split an infinite list into a longest prefix such that all the elements of it satisfy a given predicate, and the rest of the list following them.
:: Pred a | a predicate on list elements |
-> InfList a | a list of those elements |
-> ([a], InfList a) | the longest non-satisfying prefix, and the rest |
Split an infinite list into a longest prefix such that all the elements of it do not satisfy a given predicate, and the rest of the list following them.
:: (a -> a -> Bool) | a binary predicate on elements |
-> InfList a | an infinite list of that element type |
-> InfList [a] | maximal-length finite lists satisfying the predicate |
Given a predicate over two elements, split an infinite list of elements of that type into maximal-length finite lists where each adjacent pair of elements in each list satisfies the predicate in that order.
In practise, the predicate is associative and commutative, e.g. an equality
relation, as used in the group
function.
Given an infinite list, split it into maximal-length finite lists where every element in each list is equal.
:: Pred a | A predicate on elements |
-> InfList a | An infinite list of those elements |
-> (InfList a, InfList a) | Those elements satisfying and not satisfying the predicate, respectively |
Given a predicate and an infinite list, return a pair of infinite lists of elements which do and do not satisfy the predicate, respectively.
Prefixes and suffixes
:: Eq a | |
=> [a] | A finite list |
-> InfList a | An infinite list |
-> Bool | Whether the finite list is a prefix of the infinite list |
Is a given finite list a prefix of a given infinite list?
:: Eq a | |
=> [a] | the potential prefix |
-> InfList a | the list to check the prefix of |
-> Maybe (InfList a) | the rest of the list |
Given a potential prefix of an infinite list, if the infinite list has
that prefix, return just the rest of the infinite list; otherwise,
return Nothing
.
:: InfList a | A list to take prefixes of |
-> InfList [a] | A list of prefixes in ascending order of length |
List the prefixes of an infinite list in ascending order of length.
List the tails of an infinite list in ascending order of distance from the head of the list.
:: Int | a natural number |
-> InfList a | an infinite list |
-> [a] | that many elements from the start of the infinite list |
Given a natural number, return that many elements from the start of an infinite list.
:: Int | a natural number |
-> InfList a | an infinite list |
-> InfList a | the rest of the list after dropping that many elements |
Given a natural number, drop that many elements from the start of an infinite list.
:: Pred a | a predicate on list elements |
-> InfList a | an infinite list |
-> [a] | the satisfying prefix of that list |
The longest prefix of an infinite list such that all elements of that prefix satisfy a given predicate.
:: Pred a | a predicate on list elements |
-> InfList a | an infinite list |
-> InfList a | the rest of the list after satisfying elements are dropped |
Remove the longest prefix of an infinite list where all elements of that prefix satisfy a given predicate.
Zip functions
Zip two infinite lists into an infinite list of two-tuples, where `(a,b)` in the nth tuple are the nth elements of the first and second list respectively.
:: (a -> b -> c) | the combining function |
-> InfList a | the first list |
-> InfList b | the second list |
-> InfList c | the result list |
Zip two infinite lists into a third list where the nth element of the third list is the result of applying a given function to the nth elements of the first and second lists.
Reverse the operation of zip
. That is, given an infinite list of
two-tuples, return a two-tuple of infinite lists where the nth element
of the first list in the result is the first element of the nth tuple of the
first list, and correspondingly for the second list in the result tuple.
Dropping and deleting of elements
:: Pred a | a predicate on list elements |
-> InfList a | the list of elements |
-> InfList a | all elements of the list that satisfy the predicate |
Select the elements of a list that satisfy a predicate.
:: Eq a | |
=> Pred a | A predicate on list elements |
-> InfList a | A list of those elements |
-> InfList a | The same list minus the first element satisfying the predicate |
Delete the first element satisfying a given predicate.
Notice that this is not the same as deleteBy
.
:: Eq a | |
=> a | An element to compare to |
-> InfList a | A list |
-> InfList a | The same list minus the first element equal to the given element |
Delete the first element equal to a given element.
Index functions
:: InfList a | An infinite list of elements |
-> Int | An index into that list |
-> a | The element at that index |
Given a natural number, get that the element at that index of a given infinite list.