Copyright | Copyright (C) 2007 John Goerzen |
---|---|
License | BSD3 |
Maintainer | David Fox <dsf@seereason.com>, Andreas Abel |
Stability | stable |
Portability | portable |
Safe Haskell | None |
Language | Haskell2010 |
Generic operations over list-like structures
Written by John Goerzen, jgoerzen@complete.org
Synopsis
- class (IsList full, item ~ Item full, FoldableLL full item, Monoid full) => ListLike full item | full -> item where
- empty :: full
- singleton :: item -> full
- cons :: item -> full -> full
- snoc :: full -> item -> full
- append :: full -> full -> full
- head :: full -> item
- uncons :: full -> Maybe (item, full)
- last :: full -> item
- tail :: full -> full
- init :: full -> full
- null :: full -> Bool
- length :: full -> Int
- map :: ListLike full' item' => (item -> item') -> full -> full'
- rigidMap :: (item -> item) -> full -> full
- reverse :: full -> full
- intersperse :: item -> full -> full
- concat :: ListLike full' full => full' -> full
- concatMap :: ListLike full' item' => (item -> full') -> full -> full'
- rigidConcatMap :: (item -> full) -> full -> full
- any :: (item -> Bool) -> full -> Bool
- all :: (item -> Bool) -> full -> Bool
- maximum :: Ord item => full -> item
- minimum :: Ord item => full -> item
- replicate :: Int -> item -> full
- take :: Int -> full -> full
- drop :: Int -> full -> full
- splitAt :: Int -> full -> (full, full)
- takeWhile :: (item -> Bool) -> full -> full
- dropWhile :: (item -> Bool) -> full -> full
- dropWhileEnd :: (item -> Bool) -> full -> full
- span :: (item -> Bool) -> full -> (full, full)
- break :: (item -> Bool) -> full -> (full, full)
- group :: (ListLike full' full, Eq item) => full -> full'
- inits :: ListLike full' full => full -> full'
- tails :: ListLike full' full => full -> full'
- isPrefixOf :: Eq item => full -> full -> Bool
- isSuffixOf :: Eq item => full -> full -> Bool
- isInfixOf :: Eq item => full -> full -> Bool
- stripPrefix :: Eq item => full -> full -> Maybe full
- stripSuffix :: Eq item => full -> full -> Maybe full
- elem :: Eq item => item -> full -> Bool
- notElem :: Eq item => item -> full -> Bool
- find :: (item -> Bool) -> full -> Maybe item
- filter :: (item -> Bool) -> full -> full
- partition :: (item -> Bool) -> full -> (full, full)
- index :: full -> Int -> item
- elemIndex :: Eq item => item -> full -> Maybe Int
- elemIndices :: (Eq item, ListLike result Int) => item -> full -> result
- findIndex :: (item -> Bool) -> full -> Maybe Int
- findIndices :: ListLike result Int => (item -> Bool) -> full -> result
- sequence :: (Monad m, ListLike fullinp (m item)) => fullinp -> m full
- mapM :: (Monad m, ListLike full' item') => (item -> m item') -> full -> m full'
- rigidMapM :: Monad m => (item -> m item) -> full -> m full
- nub :: Eq item => full -> full
- delete :: Eq item => item -> full -> full
- deleteFirsts :: Eq item => full -> full -> full
- union :: Eq item => full -> full -> full
- intersect :: Eq item => full -> full -> full
- sort :: Ord item => full -> full
- insert :: Ord item => item -> full -> full
- toList' :: full -> [item]
- fromList' :: [item] -> full
- fromListLike :: ListLike full' item => full -> full'
- nubBy :: (item -> item -> Bool) -> full -> full
- deleteBy :: (item -> item -> Bool) -> item -> full -> full
- deleteFirstsBy :: (item -> item -> Bool) -> full -> full -> full
- unionBy :: (item -> item -> Bool) -> full -> full -> full
- intersectBy :: (item -> item -> Bool) -> full -> full -> full
- groupBy :: (ListLike full' full, Eq item) => (item -> item -> Bool) -> full -> full'
- sortBy :: (item -> item -> Ordering) -> full -> full
- insertBy :: (item -> item -> Ordering) -> item -> full -> full
- genericLength :: Num a => full -> a
- genericTake :: Integral a => a -> full -> full
- genericDrop :: Integral a => a -> full -> full
- genericSplitAt :: Integral a => a -> full -> (full, full)
- genericReplicate :: Integral a => a -> item -> full
- type ListOps full = ListLike full (Item full)
- toList :: IsList l => l -> [Item l]
- fromList :: IsList l => [Item l] -> l
- class ListLike full item => InfiniteListLike full item | full -> item where
- zip :: (ListLike full item, ListLike fullb itemb, ListLike result (item, itemb)) => full -> fullb -> result
- zipWith :: (ListLike full item, ListLike fullb itemb, ListLike result resultitem) => (item -> itemb -> resultitem) -> full -> fullb -> result
- sequence_ :: (Monad m, FoldableLL full (m item)) => full -> m ()
Documentation
class (IsList full, item ~ Item full, FoldableLL full item, Monoid full) => ListLike full item | full -> item where Source #
The class implementing list-like functions.
It is worth noting that types such as Map
can be instances of
ListLike
. Due to their specific ways of operating, they may not behave
in the expected way in some cases. For instance, cons
may not increase
the size of a map if the key you have given is already in the map; it will
just replace the value already there.
Implementators must define at least:
- singleton
- head
- tail
- null or genericLength
singleton, uncons, null | singleton, uncons, genericLength | singleton, head, tail, null | singleton, head, tail, genericLength
The empty list
singleton :: item -> full Source #
Creates a single-element list out of an element
cons :: item -> full -> full Source #
Like (:) for lists: adds an element to the beginning of a list
snoc :: full -> item -> full Source #
Adds an element to the *end* of a ListLike
.
append :: full -> full -> full Source #
Combines two lists. Like (++).
Extracts the first element of a ListLike
.
uncons :: full -> Maybe (item, full) Source #
Extract head and tail, return Nothing if empty
Extracts the last element of a ListLike
.
Gives all elements after the head.
All elements of the list except the last one. See also inits
.
Tests whether the list is empty.
length :: full -> Int Source #
Length of the list. See also genericLength
.
map :: ListLike full' item' => (item -> item') -> full -> full' Source #
Apply a function to each element, returning any other
valid ListLike
. rigidMap
will always be at least
as fast, if not faster, than this function and is recommended
if it will work for your purposes. See also mapM
.
rigidMap :: (item -> item) -> full -> full Source #
Like map
, but without the possibility of changing the type of
the item. This can have performance benefits for things such as
ByteStrings, since it will let the ByteString use its native
low-level map implementation.
reverse :: full -> full Source #
Reverse the elements in a list.
intersperse :: item -> full -> full Source #
Add an item between each element in the structure
concat :: ListLike full' full => full' -> full Source #
Flatten the structure.
concatMap :: ListLike full' item' => (item -> full') -> full -> full' Source #
Map a function over the items and concatenate the results.
See also rigidConcatMap
.
rigidConcatMap :: (item -> full) -> full -> full Source #
Like concatMap
, but without the possibility of changing
the type of the item. This can have performance benefits
for some things such as ByteString.
any :: (item -> Bool) -> full -> Bool Source #
True if any items satisfy the function
all :: (item -> Bool) -> full -> Bool Source #
True if all items satisfy the function
maximum :: Ord item => full -> item Source #
The maximum value of the list
minimum :: Ord item => full -> item Source #
The minimum value of the list
replicate :: Int -> item -> full Source #
Generate a structure with the specified length with every element
set to the item passed in. See also genericReplicate
take :: Int -> full -> full Source #
Takes the first n elements of the list. See also genericTake
.
drop :: Int -> full -> full Source #
Drops the first n elements of the list. See also genericDrop
splitAt :: Int -> full -> (full, full) Source #
Equivalent to (
. See also take
n xs, drop
n xs)genericSplitAt
.
takeWhile :: (item -> Bool) -> full -> full Source #
Returns all elements at start of list that satisfy the function.
dropWhile :: (item -> Bool) -> full -> full Source #
Drops all elements from the start of the list that satisfy the function.
dropWhileEnd :: (item -> Bool) -> full -> full Source #
Drops all elements from the end of the list that satisfy the function.
span :: (item -> Bool) -> full -> (full, full) Source #
break :: (item -> Bool) -> full -> (full, full) Source #
group :: (ListLike full' full, Eq item) => full -> full' Source #
Split a list into sublists, each which contains equal arguments.
For order-preserving types, concatenating these sublists will produce
the original list. See also groupBy
.
inits :: ListLike full' full => full -> full' Source #
All initial segments of the list, shortest first
tails :: ListLike full' full => full -> full' Source #
All final segnemts, longest first
isPrefixOf :: Eq item => full -> full -> Bool Source #
True when the first list is at the beginning of the second.
isSuffixOf :: Eq item => full -> full -> Bool Source #
True when the first list is at the beginning of the second.
isInfixOf :: Eq item => full -> full -> Bool Source #
True when the first list is wholly containted within the second
stripPrefix :: Eq item => full -> full -> Maybe full Source #
Remove a prefix from a listlike if possible
stripSuffix :: Eq item => full -> full -> Maybe full Source #
Remove a suffix from a listlike if possible
elem :: Eq item => item -> full -> Bool Source #
True if the item occurs in the list
notElem :: Eq item => item -> full -> Bool Source #
True if the item does not occur in the list
find :: (item -> Bool) -> full -> Maybe item Source #
Take a function and return the first matching element, or Nothing if there is no such element.
filter :: (item -> Bool) -> full -> full Source #
Returns only the elements that satisfy the function.
partition :: (item -> Bool) -> full -> (full, full) Source #
Returns the lists that do and do not satisfy the function.
Same as (
filter
p xs, filter
(not
. p) xs)
index :: full -> Int -> item Source #
The element at 0-based index i. Raises an exception if i is out of bounds. Like (!!) for lists.
elemIndex :: Eq item => item -> full -> Maybe Int Source #
Returns the index of the element, if it exists.
elemIndices :: (Eq item, ListLike result Int) => item -> full -> result Source #
Returns the indices of the matching elements. See also
findIndices
findIndex :: (item -> Bool) -> full -> Maybe Int Source #
Take a function and return the index of the first matching element, or Nothing if no element matches
findIndices :: ListLike result Int => (item -> Bool) -> full -> result Source #
Returns the indices of all elements satisfying the function
sequence :: (Monad m, ListLike fullinp (m item)) => fullinp -> m full Source #
Evaluate each action in the sequence and collect the results
mapM :: (Monad m, ListLike full' item') => (item -> m item') -> full -> m full' Source #
rigidMapM :: Monad m => (item -> m item) -> full -> m full Source #
Like mapM
, but without the possibility of changing the type
of the item. This can have performance benefits with some types.
nub :: Eq item => full -> full Source #
Removes duplicate elements from the list. See also nubBy
delete :: Eq item => item -> full -> full Source #
Removes the first instance of the element from the list.
See also deleteBy
deleteFirsts :: Eq item => full -> full -> full Source #
List difference. Removes from the first list the first instance
of each element of the second list. See (\\)
and deleteFirstsBy
union :: Eq item => full -> full -> full Source #
List union: the set of elements that occur in either list.
Duplicate elements in the first list will remain duplicate.
See also unionBy
.
intersect :: Eq item => full -> full -> full Source #
List intersection: the set of elements that occur in both lists.
See also intersectBy
sort :: Ord item => full -> full Source #
Sorts the list. On data types that do not preserve ordering,
or enforce their own ordering, the result may not be what
you expect. See also sortBy
.
insert :: Ord item => item -> full -> full Source #
Inserts the element at the last place where it is still less than or
equal to the next element. On data types that do not preserve
ordering, or enforce their own ordering, the result may not
be what you expect. On types such as maps, this may result in
changing an existing item. See also insertBy
.
toList' :: full -> [item] Source #
Converts the structure to a list. This is logically equivolent
to fromListLike
, but may have a more optimized implementation.
These two functions are now retired in favor of the methods of
IsList, but they are retained here because some instances still
use this implementation.
fromList' :: [item] -> full Source #
Generates the structure from a list.
fromListLike :: ListLike full' item => full -> full' Source #
Converts one ListLike to another. See also toList'
.
Default implementation is fromListLike = map id
nubBy :: (item -> item -> Bool) -> full -> full Source #
Generic version of nub
deleteBy :: (item -> item -> Bool) -> item -> full -> full Source #
Generic version of deleteBy
deleteFirstsBy :: (item -> item -> Bool) -> full -> full -> full Source #
Generic version of deleteFirsts
unionBy :: (item -> item -> Bool) -> full -> full -> full Source #
Generic version of union
intersectBy :: (item -> item -> Bool) -> full -> full -> full Source #
Generic version of intersect
groupBy :: (ListLike full' full, Eq item) => (item -> item -> Bool) -> full -> full' Source #
Generic version of group
.
sortBy :: (item -> item -> Ordering) -> full -> full Source #
Sort function taking a custom comparison function
insertBy :: (item -> item -> Ordering) -> item -> full -> full Source #
Like insert
, but with a custom comparison function
genericLength :: Num a => full -> a Source #
Length of the list
genericTake :: Integral a => a -> full -> full Source #
Generic version of take
genericDrop :: Integral a => a -> full -> full Source #
Generic version of drop
genericSplitAt :: Integral a => a -> full -> (full, full) Source #
Generic version of splitAt
genericReplicate :: Integral a => a -> item -> full Source #
Generic version of replicate
Instances
toList :: IsList l => l -> [Item l] #
The toList
function extracts a list of Item l
from the structure l
.
It should satisfy fromList . toList = id.
fromList :: IsList l => [Item l] -> l #
The fromList
function constructs the structure l
from the given
list of Item l
class ListLike full item => InfiniteListLike full item | full -> item where Source #
An extension to ListLike
for those data types that are capable
of dealing with infinite lists. Some ListLike
functions are capable
of working with finite or infinite lists. The functions here require
infinite list capability in order to work at all.
Nothing
iterate :: (item -> item) -> item -> full Source #
An infinite list of repeated calls of the function to args
repeat :: item -> full Source #
An infinite list where each element is the same
cycle :: full -> full Source #
Converts a finite list into a circular one
Instances
InfiniteListLike [a] a Source # | |
InfiniteListLike (FMList a) a Source # | |
zip :: (ListLike full item, ListLike fullb itemb, ListLike result (item, itemb)) => full -> fullb -> result Source #
Takes two lists and returns a list of corresponding pairs.