:: [[a]] -> [a]

Concatenate a list of lists.

Examples

>>> concat [[1,2,3], [4,5], [6], []]
[1,2,3,4,5,6]

>>> concat []
[]

>>> concat [[42]]
[42]

Fair n-way interleaving: given a finite number of (possibly infinite) lists, produce a single list such that whenever v has finite index in one of the input lists, v also has finite index in the output list. No list's elements occur more frequently (on average) than another's.

Unfair n-way interleaving: given a possibly infinite number of (possibly infinite) lists, produce a single list such that whenever v has finite index in an input list at finite index, v also has finite index in the output list. Elements from lists at lower index occur more frequently, but not exponentially so.

Get the diagonal of a square matrix

This is the hinge algorithm of the Omega monad, exposed because it can be useful on its own. Joins a list of lists with the property that for every i j there is an n such that xs !! i !! j == diagonal xs !! n. In particular, n <= (i+j)*(i+j+1)/2 + j.

Merge all chunks by combining to one list. (Equiv to join)

The join function is the conventional monad join operator. It is used to remove one level of monadic structure, projecting its bound argument into the outer level. 'join bss' can be understood as the do expression

do bs <- bss
bs

Examples

>>> join [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
[1,2,3,4,5,6,7,8,9]

>>> join (Just (Just 3))
Just 3

A common use of join is to run an IO computation returned from an STM transaction, since STM transactions can't perform IO directly. Recall that

atomically :: STM a -> IO a

is used to run STM transactions atomically. So, by specializing the types of atomically and join to

atomically :: STM (IO b) -> IO (IO b)
join       :: IO (IO b)  -> IO b

we can compose them as

join . atomically :: STM (IO b) -> IO b

to run an STM transaction and the IO action it returns.

The join function is the conventional monad join operator. It is used to remove one level of monadic structure, projecting its bound argument into the outer level. 'join bss' can be understood as the do expression

do bs <- bss
bs

Examples

A common use of join is to run an IO computation returned from an STM transaction, since STM transactions can't perform IO directly. Recall that

atomically :: STM a -> IO a

is used to run STM transactions atomically. So, by specializing the types of atomically and join to

atomically :: STM (IO b) -> IO (IO b)
join       :: IO (IO b)  -> IO b

we can compose them as

join . atomically :: STM (IO b) -> IO b

to run an STM transaction and the IO action it returns.

Infix version of join As an example, one could use this to rewrite

between (char '"') (char '"')

to

between .$ (char '"')

Or

fromEither :: Either a a -> a
fromEither = either id id

to

fromEither :: Either a a -> a
fromEither = either .$ id

The concatenation of all the elements of a container of lists.

Examples

Basic usage:

>>> concat (Just [1, 2, 3])
[1,2,3]

>>> concat (Left 42)
[]

>>> concat [[1, 2, 3], [4, 5], [6], []]
[1,2,3,4,5,6]

The concatenation of all the elements of a container of lists.

O(n) Concatenate all vectors in the list

The mergeAll function merges a (potentially) infinite number of ordered lists, under the assumption that the heads of the inner lists are sorted. An element is duplicated in the result as many times as the total number of occurrences in all inner lists. The mergeAll function is closely related to foldr merge []. The former does not assume that the outer list is finite, whereas the latter does not assume that the heads of the inner lists are sorted. When both sets of assumptions are met, these two functions are equivalent. This implementation of mergeAll uses a tree of comparisons, and is based on input from Dave Bayer, Heinrich Apfelmus, Omar Antolin Camarena, and Will Ness. See CHANGES for details.

The unionAll computes the union of a (potentially) infinite number of lists, under the assumption that the heads of the inner lists are sorted. The result will duplicate an element as many times as the maximum number of occurrences in any single list. Thus, the result is a set if and only if every inner list is a set. The unionAll function is closely related to foldr union []. The former does not assume that the outer list is finite, whereas the latter does not assume that the heads of the inner lists are sorted. When both sets of assumptions are met, these two functions are equivalent. Note that there is no simple way to express unionAll in terms of mergeAll or vice versa on arbitrary valid inputs. They are related via nub however, as nub . mergeAll == unionAll . map nub. If every list is a set, then map nub == id, and in this special case (and only in this special case) does nub . mergeAll == unionAll. This implementation of unionAll uses a tree of comparisons, and is based on input from Dave Bayer, Heinrich Apfelmus, Omar Antolin Camarena, and Will Ness. See CHANGES for details.

Return the longest common prefix of a set of lists.

P(xs) === all (isPrefixOf (commonPrefix xs)) xs
length s > length (commonPrefix xs) --> not (all (isPrefixOf s) xs)

Add some lists.

Concating the result of an action.