Finite sequences

The Seq a type represents a finite sequence of values of type a. Sequences generally behave very much like lists.

• The class instances for sequences are all based very closely on those for lists.
• Many functions in this module have the same names as functions in the Prelude or in Data.List. In almost all cases, these functions behave analogously. For example, filter filters a sequence in exactly the same way that Prelude.filter filters a list. The only major exception is the lookup function, which is based on the function by that name in Data.IntMap rather than the one in Prelude.

There are two major differences between sequences and lists:

• Sequences support a wider variety of efficient operations than do lists. Notably, they offer
  • Constant-time access to both the front and the rear with <|, |>, viewl, viewr. For recent GHC versions, this can be done more conveniently using the bidirectional patterns Empty, :<|, and :|>. See the detailed explanation in the "Pattern synonyms" section.
  • Logarithmic-time concatenation with ><
  • Logarithmic-time splitting with splitAt, take and drop
  • Logarithmic-time access to any element with lookup, !?, index, insertAt, deleteAt, adjust', and update

Note that sequences are typically slower than lists when using only operations for which they have the same big-(O) complexity: sequences make rather mediocre stacks!

• Whereas lists can be either finite or infinite, sequences are always finite. As a result, a sequence is strict in its length. Ignoring efficiency, you can imagine that Seq is defined

  data Seq a = Empty | a :<| !(Seq a)

  This means that many operations on sequences are stricter than those on lists. For example,

   (1 : undefined) !! 0 = 1

  but

   (1 :<|
  undefined) `index` 0 = undefined

Sequences may also be compared to immutable arrays or vectors. Like these structures, sequences support fast indexing, although not as fast. But editing an immutable array or vector, or combining it with another, generally requires copying the entire structure; sequences generally avoid that, copying only the portion that has changed.

Detailed performance information

An amortized running time is given for each operation, with <math> referring to the length of the sequence and i being the integral index used by some operations. These bounds hold even in a persistent (shared) setting. Despite sequences being structurally strict from a semantic standpoint, they are in fact implemented using laziness internally. As a result, many operations can be performed incrementally, producing their results as they are demanded. This greatly improves performance in some cases. These functions include

• The Functor methods fmap and <$, along with mapWithIndex
• The Applicative methods <*>, *>, and <*
• The zips: zipWith, zip, etc.
• inits, tails
• fromFunction, replicate, intersperse, and cycleTaking
• reverse
• chunksOf

Note that the Monad method, >>=, is not particularly lazy. It will take time proportional to the sum of the logarithms of the individual result sequences to produce anything whatsoever. Several functions take special advantage of sharing to produce results using much less time and memory than one might expect. These are documented individually for functions, but also include certain class methods: <$ and *> each take time and space proportional to the logarithm of the size of their result. <* takes time and space proportional to the product of the length of its first argument and the logarithm of the length of its second argument.

Warning

The size of a Seq must not exceed maxBound::Int. Violation of this condition is not detected and if the size limit is exceeded, the behaviour of the sequence is undefined. This is unlikely to occur in most applications, but some care may be required when using ><, <*>, *>, or >>, particularly repeatedly and particularly in combination with replicate or fromFunction.

Implementation

The implementation uses 2-3 finger trees annotated with sizes, as described in section 4.2 of

• Ralf Hinze and Ross Paterson, "Finger trees: a simple general-purpose data structure", Journal of Functional Programming 16:2 (2006) pp 197-217.

Actually, Sequence is a better name for this

Special wrapper for formats that support encoding/decoding sequence of array.

Evaluate each monadic action in the structure from left to right, and collect the results. For a version that ignores the results see sequence_.

Examples

Basic usage: The first two examples are instances where the input and and output of sequence are isomorphic.

>>> sequence $ Right [1,2,3,4]
[Right 1,Right 2,Right 3,Right 4]

>>> sequence $ [Right 1,Right 2,Right 3,Right 4]
Right [1,2,3,4]

The following examples demonstrate short circuit behavior for sequence.

>>> sequence $ Left [1,2,3,4]
Left [1,2,3,4]

>>> sequence $ [Left 0, Right 1,Right 2,Right 3,Right 4]
Left 0

Evaluate each action and collect the results.

Evaluate each action and collect the results.

Run a Pipe repeatedly, and output its result value downstream. Stops when no more input is available from upstream. Since 0.5.0

Evaluate each action in the sequence and collect the results

sequence = mapM id

Replace the elements of a stream of monadic actions with the outputs of those actions.

>>> drain $ Stream.sequence $ Stream.fromList [putStr "a", putStr "b", putStrLn "c"]
abc

>>> :{
drain $ Stream.replicateM 3 (return $ threadDelay 1000000 >> print 1)
& (fromSerial . Stream.sequence)
:}
1
1
1

>>> :{
drain $ Stream.replicateM 3 (return $ threadDelay 1000000 >> print 1)
& (fromAsync . Stream.sequence)
:}
1
1
1

Concurrent (do not use with fromParallel on infinite streams)

Evaluate each action and collect the results.

Evaluate each action and collect the results.

Evaluate each action and collect the results.

Evaluate each action and collect the results.

Evaluate each action in the structure from left to right and collect the results. For a version that ignores the results see sequence_.