seq is:module

Various utilities for forcing Core structures It can often be useful to force various parts of the AST. This module provides a number of seq-like functions to accomplish this.
Sequential strategies provide ways to compositionally specify the degree of evaluation of a data type between the extremes of no evaluation and full evaluation. Sequential strategies may be viewed as complimentary to the parallel ones (see module Control.Parallel.Strategies).
Seq. Import as:
import qualified RIO.Seq as Seq
This module defines convenient functions to build Bindings that bind actions to key sequences. For example, see WildBind.Task.X11.Seq.Example in wild-bind-task-x11 package.
This module provides sequence-specific multimap functionality.

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 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
This modules provides RegexMaker and RegexLike instances for using ByteString with the DFA backend (Text.Regex.Lib.WrapDFAEngine and Text.Regex.Lazy.DFAEngineFPS). This module is usually used via import Text.Regex.TDFA. This exports instances of the high level API and the medium level API of compile,execute, and regexec.
This provides String instances for RegexMaker and RegexLike based on Text.Regex.Posix.Wrap, and a (RegexContext Regex String String) instance. To use these instance, you would normally import Text.Regex.Posix. You only need to import this module to use the medium level API of the compile, regexec, and execute functions. All of these report error by returning Left values instead of undefined or error or fail.
The Sequence struct is an opaque data type representing a [sequence][glib-Sequences] data type.
The SequenceIter struct is an opaque data type representing an iterator pointing into a Sequence.
Abstractions over sequential data structures, like lists and vectors.
This exports instances of the high level API and the medium level API of compile,execute, and regexec.
Perhaps place the sequencer handle in an MVar?
This module provides structures about sequence tables.
This module provides operations for sequence tables of relational-query with HDBC.
Functions for sequencing actions requested from concurrent threads. Here is an example usage:
import qualified Control.Concurrent.PooledIO.Independent as Parallel
import qualified Control.Concurrent.PooledIO.Sequence as Sequence

thread :: Sequence.In -> FilePath -> IO ()
thread seqIn name = do
txt <- Sequence.sync seqIn $ readFile (name ++ ".in")
-- evaluate result with ($!!) before sending it to the sequencing thread
Sequence.async seqIn . writeFile (name ++ ".out") $!! processMyText txt
doFurtherStuff
-- block main program until completion
Sequence.sync seqIn $ return ()

main :: IO ()
main = do
(seqIn, seqOut) <- Sequence.new
void $ forkIO $ Sequence.run seqOut
Parallel.run $ map (thread seqIn) ["a", "b", "c"]