<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Data.Sequence</title><link href="ocean.css" rel="stylesheet" type="text/css" title="Ocean" /><script src="haddock-util.js" type="text/javascript"></script><script type="text/javascript">//<![CDATA[
window.onload = function () {pageLoad();setSynopsis("mini_Data-Sequence.html");};
//]]>
</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="index.html">Contents</a></li><li><a href="doc-index.html">Index</a></li></ul><p class="caption">containers-0.4.2.1: Assorted concrete container types</p></div><div id="content"><div id="module-header"><table class="info"><tr><th>Portability</th><td>portable</td></tr><tr><th>Stability</th><td>experimental</td></tr><tr><th>Maintainer</th><td>libraries@haskell.org</td></tr><tr><th>Safe Haskell</th><td>Trustworthy</td></tr></table><p class="caption">Data.Sequence</p></div><div id="table-of-contents"><p class="caption">Contents</p><ul><li><a href="#g:1">Construction
</a><ul><li><a href="#g:2">Repetition
</a></li><li><a href="#g:3">Iterative construction
</a></li></ul></li><li><a href="#g:4">Deconstruction
</a><ul><li><a href="#g:5">Queries
</a></li><li><a href="#g:6">Views
</a></li></ul></li><li><a href="#g:7">Scans
</a></li><li><a href="#g:8">Sublists
</a><ul><li><a href="#g:9">Sequential searches
</a></li></ul></li><li><a href="#g:10">Sorting
</a></li><li><a href="#g:11">Indexing
</a><ul><li><a href="#g:12">Indexing with predicates
</a></li></ul></li><li><a href="#g:13">Folds
</a></li><li><a href="#g:14">Transformations
</a><ul><li><a href="#g:15">Zips
</a></li></ul></li></ul></div><div id="description"><p class="caption">Description</p><div class="doc"><p>General purpose finite sequences.
Apart from being finite and having strict operations, sequences
also differ from lists in supporting a wider variety of operations
efficiently.
</p><p>An amortized running time is given for each operation, with <em>n</em> referring
to the length of the sequence and <em>i</em> being the integral index used by
some operations. These bounds hold even in a persistent (shared) setting.
</p><p>The implementation uses 2-3 finger trees annotated with sizes,
as described in section 4.2 of
</p><ul><li> Ralf Hinze and Ross Paterson,
"Finger trees: a simple general-purpose data structure",
<em>Journal of Functional Programming</em> 16:2 (2006) pp 197-217.
<a href="http://www.soi.city.ac.uk/~ross/papers/FingerTree.html">http://www.soi.city.ac.uk/~ross/papers/FingerTree.html</a>
</li></ul><p><em>Note</em>: Many of these operations have the same names as similar
operations on lists in the <a href="../base-4.5.1.0/Prelude.html">Prelude</a>. The ambiguity may be resolved
using either qualification or the <code>hiding</code> clause.
</p></div></div><div id="synopsis"><p id="control.syn" class="caption expander" onclick="toggleSection('syn')">Synopsis</p><ul id="section.syn" class="hide" onclick="toggleSection('syn')"><li class="src short"><span class="keyword">data</span> <a href="#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:empty">empty</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:singleton">singleton</a> :: a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:-60--124-">(<|)</a> :: a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:-124--62-">(|>)</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:-62--60-">(><)</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:fromList">fromList</a> :: [a] -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:replicate">replicate</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:replicateA">replicateA</a> :: <a href="../base-4.5.1.0/Control-Applicative.html#t:Applicative">Applicative</a> f => <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> f a -> f (<a href="Data-Sequence.html#t:Seq">Seq</a> a)</li><li class="src short"><a href="#v:replicateM">replicateM</a> :: <a href="../base-4.5.1.0/Control-Monad.html#t:Monad">Monad</a> m => <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> m a -> m (<a href="Data-Sequence.html#t:Seq">Seq</a> a)</li><li class="src short"><a href="#v:iterateN">iterateN</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> (a -> a) -> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:unfoldr">unfoldr</a> :: (b -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (a, b)) -> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:unfoldl">unfoldl</a> :: (b -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (b, a)) -> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:null">null</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:length">length</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></li><li class="src short"><span class="keyword">data</span> <a href="#t:ViewL">ViewL</a> a<ul class="subs"><li>= <a href="#v:EmptyL">EmptyL</a> </li><li>| a <a href="#v::-60-">:<</a> (<a href="Data-Sequence.html#t:Seq">Seq</a> a) </li></ul></li><li class="src short"><a href="#v:viewl">viewl</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:ViewL">ViewL</a> a</li><li class="src short"><span class="keyword">data</span> <a href="#t:ViewR">ViewR</a> a<ul class="subs"><li>= <a href="#v:EmptyR">EmptyR</a> </li><li>| (<a href="Data-Sequence.html#t:Seq">Seq</a> a) <a href="#v::-62-">:></a> a </li></ul></li><li class="src short"><a href="#v:viewr">viewr</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:ViewR">ViewR</a> a</li><li class="src short"><a href="#v:scanl">scanl</a> :: (a -> b -> a) -> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:scanl1">scanl1</a> :: (a -> a -> a) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:scanr">scanr</a> :: (a -> b -> b) -> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> b</li><li class="src short"><a href="#v:scanr1">scanr1</a> :: (a -> a -> a) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:tails">tails</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> (<a href="Data-Sequence.html#t:Seq">Seq</a> a)</li><li class="src short"><a href="#v:inits">inits</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> (<a href="Data-Sequence.html#t:Seq">Seq</a> a)</li><li class="src short"><a href="#v:takeWhileL">takeWhileL</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:takeWhileR">takeWhileR</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:dropWhileL">dropWhileL</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:dropWhileR">dropWhileR</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:spanl">spanl</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> (<a href="Data-Sequence.html#t:Seq">Seq</a> a, <a href="Data-Sequence.html#t:Seq">Seq</a> a)</li><li class="src short"><a href="#v:spanr">spanr</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> (<a href="Data-Sequence.html#t:Seq">Seq</a> a, <a href="Data-Sequence.html#t:Seq">Seq</a> a)</li><li class="src short"><a href="#v:breakl">breakl</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> (<a href="Data-Sequence.html#t:Seq">Seq</a> a, <a href="Data-Sequence.html#t:Seq">Seq</a> a)</li><li class="src short"><a href="#v:breakr">breakr</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> (<a href="Data-Sequence.html#t:Seq">Seq</a> a, <a href="Data-Sequence.html#t:Seq">Seq</a> a)</li><li class="src short"><a href="#v:partition">partition</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> (<a href="Data-Sequence.html#t:Seq">Seq</a> a, <a href="Data-Sequence.html#t:Seq">Seq</a> a)</li><li class="src short"><a href="#v:filter">filter</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:sort">sort</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:sortBy">sortBy</a> :: (a -> a -> <a href="../base-4.5.1.0/Data-Ord.html#t:Ordering">Ordering</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:unstableSort">unstableSort</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:unstableSortBy">unstableSortBy</a> :: (a -> a -> <a href="../base-4.5.1.0/Data-Ord.html#t:Ordering">Ordering</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:index">index</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> a</li><li class="src short"><a href="#v:adjust">adjust</a> :: (a -> a) -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:update">update</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:take">take</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:drop">drop</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:splitAt">splitAt</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> (<a href="Data-Sequence.html#t:Seq">Seq</a> a, <a href="Data-Sequence.html#t:Seq">Seq</a> a)</li><li class="src short"><a href="#v:elemIndexL">elemIndexL</a> :: <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> a => a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:elemIndicesL">elemIndicesL</a> :: <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> a => a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> [<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>]</li><li class="src short"><a href="#v:elemIndexR">elemIndexR</a> :: <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> a => a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:elemIndicesR">elemIndicesR</a> :: <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> a => a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> [<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>]</li><li class="src short"><a href="#v:findIndexL">findIndexL</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:findIndicesL">findIndicesL</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> [<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>]</li><li class="src short"><a href="#v:findIndexR">findIndexR</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:findIndicesR">findIndicesR</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> [<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>]</li><li class="src short"><a href="#v:foldlWithIndex">foldlWithIndex</a> :: (b -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> a -> b) -> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> b</li><li class="src short"><a href="#v:foldrWithIndex">foldrWithIndex</a> :: (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> a -> b -> b) -> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> b</li><li class="src short"><a href="#v:mapWithIndex">mapWithIndex</a> :: (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> a -> b) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> b</li><li class="src short"><a href="#v:reverse">reverse</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</li><li class="src short"><a href="#v:zip">zip</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> (a, b)</li><li class="src short"><a href="#v:zipWith">zipWith</a> :: (a -> b -> c) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> c</li><li class="src short"><a href="#v:zip3">zip3</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> c -> <a href="Data-Sequence.html#t:Seq">Seq</a> (a, b, c)</li><li class="src short"><a href="#v:zipWith3">zipWith3</a> :: (a -> b -> c -> d) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> c -> <a href="Data-Sequence.html#t:Seq">Seq</a> d</li><li class="src short"><a href="#v:zip4">zip4</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> c -> <a href="Data-Sequence.html#t:Seq">Seq</a> d -> <a href="Data-Sequence.html#t:Seq">Seq</a> (a, b, c, d)</li><li class="src short"><a href="#v:zipWith4">zipWith4</a> :: (a -> b -> c -> d -> e) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> c -> <a href="Data-Sequence.html#t:Seq">Seq</a> d -> <a href="Data-Sequence.html#t:Seq">Seq</a> e</li></ul></div><div id="interface"><h1>Documentation</h1><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:Seq" class="def">Seq</a> a </p><div class="doc"><p>General-purpose finite sequences.
</p></div><div class="subs instances"><p id="control.i:Seq" class="caption collapser" onclick="toggleSection('i:Seq')">Instances</p><div id="section.i:Seq" class="show"><table><tr><td class="src"><a href="../base-4.5.1.0/Control-Monad.html#t:Monad">Monad</a> <a href="Data-Sequence.html#t:Seq">Seq</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Control-Monad.html#t:Functor">Functor</a> <a href="Data-Sequence.html#t:Seq">Seq</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Typeable-Internal.html#t:Typeable1">Typeable1</a> <a href="Data-Sequence.html#t:Seq">Seq</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Control-Monad.html#t:MonadPlus">MonadPlus</a> <a href="Data-Sequence.html#t:Seq">Seq</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Foldable.html#t:Foldable">Foldable</a> <a href="Data-Sequence.html#t:Seq">Seq</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Traversable.html#t:Traversable">Traversable</a> <a href="Data-Sequence.html#t:Seq">Seq</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> a => <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> (<a href="Data-Sequence.html#t:Seq">Seq</a> a)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Data.html#t:Data">Data</a> a => <a href="../base-4.5.1.0/Data-Data.html#t:Data">Data</a> (<a href="Data-Sequence.html#t:Seq">Seq</a> a)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> (<a href="Data-Sequence.html#t:Seq">Seq</a> a)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Text-Read.html#t:Read">Read</a> a => <a href="../base-4.5.1.0/Text-Read.html#t:Read">Read</a> (<a href="Data-Sequence.html#t:Seq">Seq</a> a)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Text-Show.html#t:Show">Show</a> a => <a href="../base-4.5.1.0/Text-Show.html#t:Show">Show</a> (<a href="Data-Sequence.html#t:Seq">Seq</a> a)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Monoid.html#t:Monoid">Monoid</a> (<a href="Data-Sequence.html#t:Seq">Seq</a> a)</td><td class="doc empty"> </td></tr></table></div></div></div><h1 id="g:1">Construction
</h1><div class="top"><p class="src"><a name="v:empty" class="def">empty</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><em>O(1)</em>. The empty sequence.
</p></div></div><div class="top"><p class="src"><a name="v:singleton" class="def">singleton</a> :: a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><em>O(1)</em>. A singleton sequence.
</p></div></div><div class="top"><p class="src"><a name="v:-60--124-" class="def">(<|)</a> :: a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><em>O(1)</em>. Add an element to the left end of a sequence.
Mnemonic: a triangle with the single element at the pointy end.
</p></div></div><div class="top"><p class="src"><a name="v:-124--62-" class="def">(|>)</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><em>O(1)</em>. Add an element to the right end of a sequence.
Mnemonic: a triangle with the single element at the pointy end.
</p></div></div><div class="top"><p class="src"><a name="v:-62--60-" class="def">(><)</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><em>O(log(min(n1,n2)))</em>. Concatenate two sequences.
</p></div></div><div class="top"><p class="src"><a name="v:fromList" class="def">fromList</a> :: [a] -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><em>O(n)</em>. Create a sequence from a finite list of elements.
There is a function <code><a href="../base-4.5.1.0/Data-Foldable.html#v:toList">toList</a></code> in the opposite direction for all
instances of the <code><a href="../base-4.5.1.0/Data-Foldable.html#t:Foldable">Foldable</a></code> class, including <code><a href="Data-Sequence.html#t:Seq">Seq</a></code>.
</p></div></div><h2 id="g:2">Repetition
</h2><div class="top"><p class="src"><a name="v:replicate" class="def">replicate</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><em>O(log n)</em>. <code>replicate n x</code> is a sequence consisting of <code>n</code> copies of <code>x</code>.
</p></div></div><div class="top"><p class="src"><a name="v:replicateA" class="def">replicateA</a> :: <a href="../base-4.5.1.0/Control-Applicative.html#t:Applicative">Applicative</a> f => <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> f a -> f (<a href="Data-Sequence.html#t:Seq">Seq</a> a)</p><div class="doc"><p><code><a href="Data-Sequence.html#v:replicateA">replicateA</a></code> is an <code><a href="../base-4.5.1.0/Control-Applicative.html#t:Applicative">Applicative</a></code> version of <code><a href="Data-Sequence.html#v:replicate">replicate</a></code>, and makes
<em>O(log n)</em> calls to <code><a href="../base-4.5.1.0/Control-Applicative.html#v:-60--42--62-"><*></a></code> and <code><a href="../base-4.5.1.0/Control-Applicative.html#v:pure">pure</a></code>.
</p><pre> replicateA n x = sequenceA (replicate n x)
</pre></div></div><div class="top"><p class="src"><a name="v:replicateM" class="def">replicateM</a> :: <a href="../base-4.5.1.0/Control-Monad.html#t:Monad">Monad</a> m => <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> m a -> m (<a href="Data-Sequence.html#t:Seq">Seq</a> a)</p><div class="doc"><p><code><a href="Data-Sequence.html#v:replicateM">replicateM</a></code> is a sequence counterpart of <code><a href="../base-4.5.1.0/Control-Monad.html#v:replicateM">replicateM</a></code>.
</p><pre> replicateM n x = sequence (replicate n x)
</pre></div></div><h2 id="g:3">Iterative construction
</h2><div class="top"><p class="src"><a name="v:iterateN" class="def">iterateN</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> (a -> a) -> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><em>O(n)</em>. Constructs a sequence by repeated application of a function
to a seed value.
</p><pre> iterateN n f x = fromList (Prelude.take n (Prelude.iterate f x))
</pre></div></div><div class="top"><p class="src"><a name="v:unfoldr" class="def">unfoldr</a> :: (b -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (a, b)) -> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p>Builds a sequence from a seed value. Takes time linear in the
number of generated elements. <em>WARNING:</em> If the number of generated
elements is infinite, this method will not terminate.
</p></div></div><div class="top"><p class="src"><a name="v:unfoldl" class="def">unfoldl</a> :: (b -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (b, a)) -> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><code><code><a href="Data-Sequence.html#v:unfoldl">unfoldl</a></code> f x</code> is equivalent to <code><code><a href="Data-Sequence.html#v:reverse">reverse</a></code> (<code><a href="Data-Sequence.html#v:unfoldr">unfoldr</a></code> (<code><a href="../base-4.5.1.0/Control-Monad.html#v:fmap">fmap</a></code> swap . f) x)</code>.
</p></div></div><h1 id="g:4">Deconstruction
</h1><div class="doc"><p>Additional functions for deconstructing sequences are available
via the <code><a href="../base-4.5.1.0/Data-Foldable.html#t:Foldable">Foldable</a></code> instance of <code><a href="Data-Sequence.html#t:Seq">Seq</a></code>.
</p></div><h2 id="g:5">Queries
</h2><div class="top"><p class="src"><a name="v:null" class="def">null</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></p><div class="doc"><p><em>O(1)</em>. Is this the empty sequence?
</p></div></div><div class="top"><p class="src"><a name="v:length" class="def">length</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></p><div class="doc"><p><em>O(1)</em>. The number of elements in the sequence.
</p></div></div><h2 id="g:6">Views
</h2><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:ViewL" class="def">ViewL</a> a </p><div class="doc"><p>View of the left end of a sequence.
</p></div><div class="subs constructors"><p class="caption">Constructors</p><table><tr><td class="src"><a name="v:EmptyL" class="def">EmptyL</a></td><td class="doc"><p>empty sequence
</p></td></tr><tr><td class="src">a <a name="v::-60-" class="def">:<</a> (<a href="Data-Sequence.html#t:Seq">Seq</a> a)</td><td class="doc"><p>leftmost element and the rest of the sequence
</p></td></tr></table></div><div class="subs instances"><p id="control.i:ViewL" class="caption collapser" onclick="toggleSection('i:ViewL')">Instances</p><div id="section.i:ViewL" class="show"><table><tr><td class="src"><a href="../base-4.5.1.0/Control-Monad.html#t:Functor">Functor</a> <a href="Data-Sequence.html#t:ViewL">ViewL</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Typeable-Internal.html#t:Typeable1">Typeable1</a> <a href="Data-Sequence.html#t:ViewL">ViewL</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Foldable.html#t:Foldable">Foldable</a> <a href="Data-Sequence.html#t:ViewL">ViewL</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Traversable.html#t:Traversable">Traversable</a> <a href="Data-Sequence.html#t:ViewL">ViewL</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> a => <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> (<a href="Data-Sequence.html#t:ViewL">ViewL</a> a)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Data.html#t:Data">Data</a> a => <a href="../base-4.5.1.0/Data-Data.html#t:Data">Data</a> (<a href="Data-Sequence.html#t:ViewL">ViewL</a> a)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> (<a href="Data-Sequence.html#t:ViewL">ViewL</a> a)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Text-Read.html#t:Read">Read</a> a => <a href="../base-4.5.1.0/Text-Read.html#t:Read">Read</a> (<a href="Data-Sequence.html#t:ViewL">ViewL</a> a)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Text-Show.html#t:Show">Show</a> a => <a href="../base-4.5.1.0/Text-Show.html#t:Show">Show</a> (<a href="Data-Sequence.html#t:ViewL">ViewL</a> a)</td><td class="doc empty"> </td></tr></table></div></div></div><div class="top"><p class="src"><a name="v:viewl" class="def">viewl</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:ViewL">ViewL</a> a</p><div class="doc"><p><em>O(1)</em>. Analyse the left end of a sequence.
</p></div></div><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:ViewR" class="def">ViewR</a> a </p><div class="doc"><p>View of the right end of a sequence.
</p></div><div class="subs constructors"><p class="caption">Constructors</p><table><tr><td class="src"><a name="v:EmptyR" class="def">EmptyR</a></td><td class="doc"><p>empty sequence
</p></td></tr><tr><td class="src">(<a href="Data-Sequence.html#t:Seq">Seq</a> a) <a name="v::-62-" class="def">:></a> a</td><td class="doc"><p>the sequence minus the rightmost element,
and the rightmost element
</p></td></tr></table></div><div class="subs instances"><p id="control.i:ViewR" class="caption collapser" onclick="toggleSection('i:ViewR')">Instances</p><div id="section.i:ViewR" class="show"><table><tr><td class="src"><a href="../base-4.5.1.0/Control-Monad.html#t:Functor">Functor</a> <a href="Data-Sequence.html#t:ViewR">ViewR</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Typeable-Internal.html#t:Typeable1">Typeable1</a> <a href="Data-Sequence.html#t:ViewR">ViewR</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Foldable.html#t:Foldable">Foldable</a> <a href="Data-Sequence.html#t:ViewR">ViewR</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Traversable.html#t:Traversable">Traversable</a> <a href="Data-Sequence.html#t:ViewR">ViewR</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> a => <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> (<a href="Data-Sequence.html#t:ViewR">ViewR</a> a)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Data.html#t:Data">Data</a> a => <a href="../base-4.5.1.0/Data-Data.html#t:Data">Data</a> (<a href="Data-Sequence.html#t:ViewR">ViewR</a> a)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> (<a href="Data-Sequence.html#t:ViewR">ViewR</a> a)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Text-Read.html#t:Read">Read</a> a => <a href="../base-4.5.1.0/Text-Read.html#t:Read">Read</a> (<a href="Data-Sequence.html#t:ViewR">ViewR</a> a)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Text-Show.html#t:Show">Show</a> a => <a href="../base-4.5.1.0/Text-Show.html#t:Show">Show</a> (<a href="Data-Sequence.html#t:ViewR">ViewR</a> a)</td><td class="doc empty"> </td></tr></table></div></div></div><div class="top"><p class="src"><a name="v:viewr" class="def">viewr</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:ViewR">ViewR</a> a</p><div class="doc"><p><em>O(1)</em>. Analyse the right end of a sequence.
</p></div></div><h1 id="g:7">Scans
</h1><div class="top"><p class="src"><a name="v:scanl" class="def">scanl</a> :: (a -> b -> a) -> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><code><a href="Data-Sequence.html#v:scanl">scanl</a></code> is similar to <code><a href="../base-4.5.1.0/Data-Foldable.html#v:foldl">foldl</a></code>, but returns a sequence of reduced
values from the left:
</p><pre> scanl f z (fromList [x1, x2, ...]) = fromList [z, z `f` x1, (z `f` x1) `f` x2, ...]
</pre></div></div><div class="top"><p class="src"><a name="v:scanl1" class="def">scanl1</a> :: (a -> a -> a) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><code><a href="Data-Sequence.html#v:scanl1">scanl1</a></code> is a variant of <code><a href="Data-Sequence.html#v:scanl">scanl</a></code> that has no starting value argument:
</p><pre> scanl1 f (fromList [x1, x2, ...]) = fromList [x1, x1 `f` x2, ...]
</pre></div></div><div class="top"><p class="src"><a name="v:scanr" class="def">scanr</a> :: (a -> b -> b) -> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> b</p><div class="doc"><p><code><a href="Data-Sequence.html#v:scanr">scanr</a></code> is the right-to-left dual of <code><a href="Data-Sequence.html#v:scanl">scanl</a></code>.
</p></div></div><div class="top"><p class="src"><a name="v:scanr1" class="def">scanr1</a> :: (a -> a -> a) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><code><a href="Data-Sequence.html#v:scanr1">scanr1</a></code> is a variant of <code><a href="Data-Sequence.html#v:scanr">scanr</a></code> that has no starting value argument.
</p></div></div><h1 id="g:8">Sublists
</h1><div class="top"><p class="src"><a name="v:tails" class="def">tails</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> (<a href="Data-Sequence.html#t:Seq">Seq</a> a)</p><div class="doc"><p><em>O(n)</em>. Returns a sequence of all suffixes of this sequence,
longest first. For example,
</p><pre> tails (fromList "abc") = fromList [fromList "abc", fromList "bc", fromList "c", fromList ""]
</pre><p>Evaluating the <em>i</em>th suffix takes <em>O(log(min(i, n-i)))</em>, but evaluating
every suffix in the sequence takes <em>O(n)</em> due to sharing.
</p></div></div><div class="top"><p class="src"><a name="v:inits" class="def">inits</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> (<a href="Data-Sequence.html#t:Seq">Seq</a> a)</p><div class="doc"><p><em>O(n)</em>. Returns a sequence of all prefixes of this sequence,
shortest first. For example,
</p><pre> inits (fromList "abc") = fromList [fromList "", fromList "a", fromList "ab", fromList "abc"]
</pre><p>Evaluating the <em>i</em>th prefix takes <em>O(log(min(i, n-i)))</em>, but evaluating
every prefix in the sequence takes <em>O(n)</em> due to sharing.
</p></div></div><h2 id="g:9">Sequential searches
</h2><div class="top"><p class="src"><a name="v:takeWhileL" class="def">takeWhileL</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><em>O(i)</em> where <em>i</em> is the prefix length. <code><a href="Data-Sequence.html#v:takeWhileL">takeWhileL</a></code>, applied
to a predicate <code>p</code> and a sequence <code>xs</code>, returns the longest prefix
(possibly empty) of <code>xs</code> of elements that satisfy <code>p</code>.
</p></div></div><div class="top"><p class="src"><a name="v:takeWhileR" class="def">takeWhileR</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><em>O(i)</em> where <em>i</em> is the suffix length. <code><a href="Data-Sequence.html#v:takeWhileR">takeWhileR</a></code>, applied
to a predicate <code>p</code> and a sequence <code>xs</code>, returns the longest suffix
(possibly empty) of <code>xs</code> of elements that satisfy <code>p</code>.
</p><p><code><code><a href="Data-Sequence.html#v:takeWhileR">takeWhileR</a></code> p xs</code> is equivalent to <code><code><a href="Data-Sequence.html#v:reverse">reverse</a></code> (<code><a href="Data-Sequence.html#v:takeWhileL">takeWhileL</a></code> p (<code><a href="Data-Sequence.html#v:reverse">reverse</a></code> xs))</code>.
</p></div></div><div class="top"><p class="src"><a name="v:dropWhileL" class="def">dropWhileL</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><em>O(i)</em> where <em>i</em> is the prefix length. <code><code><a href="Data-Sequence.html#v:dropWhileL">dropWhileL</a></code> p xs</code> returns
the suffix remaining after <code><code><a href="Data-Sequence.html#v:takeWhileL">takeWhileL</a></code> p xs</code>.
</p></div></div><div class="top"><p class="src"><a name="v:dropWhileR" class="def">dropWhileR</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><em>O(i)</em> where <em>i</em> is the suffix length. <code><code><a href="Data-Sequence.html#v:dropWhileR">dropWhileR</a></code> p xs</code> returns
the prefix remaining after <code><code><a href="Data-Sequence.html#v:takeWhileR">takeWhileR</a></code> p xs</code>.
</p><p><code><code><a href="Data-Sequence.html#v:dropWhileR">dropWhileR</a></code> p xs</code> is equivalent to <code><code><a href="Data-Sequence.html#v:reverse">reverse</a></code> (<code><a href="Data-Sequence.html#v:dropWhileL">dropWhileL</a></code> p (<code><a href="Data-Sequence.html#v:reverse">reverse</a></code> xs))</code>.
</p></div></div><div class="top"><p class="src"><a name="v:spanl" class="def">spanl</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> (<a href="Data-Sequence.html#t:Seq">Seq</a> a, <a href="Data-Sequence.html#t:Seq">Seq</a> a)</p><div class="doc"><p><em>O(i)</em> where <em>i</em> is the prefix length. <code><a href="Data-Sequence.html#v:spanl">spanl</a></code>, applied to
a predicate <code>p</code> and a sequence <code>xs</code>, returns a pair whose first
element is the longest prefix (possibly empty) of <code>xs</code> of elements that
satisfy <code>p</code> and the second element is the remainder of the sequence.
</p></div></div><div class="top"><p class="src"><a name="v:spanr" class="def">spanr</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> (<a href="Data-Sequence.html#t:Seq">Seq</a> a, <a href="Data-Sequence.html#t:Seq">Seq</a> a)</p><div class="doc"><p><em>O(i)</em> where <em>i</em> is the suffix length. <code><a href="Data-Sequence.html#v:spanr">spanr</a></code>, applied to a
predicate <code>p</code> and a sequence <code>xs</code>, returns a pair whose <em>first</em> element
is the longest <em>suffix</em> (possibly empty) of <code>xs</code> of elements that
satisfy <code>p</code> and the second element is the remainder of the sequence.
</p></div></div><div class="top"><p class="src"><a name="v:breakl" class="def">breakl</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> (<a href="Data-Sequence.html#t:Seq">Seq</a> a, <a href="Data-Sequence.html#t:Seq">Seq</a> a)</p><div class="doc"><p><em>O(i)</em> where <em>i</em> is the breakpoint index. <code><a href="Data-Sequence.html#v:breakl">breakl</a></code>, applied to a
predicate <code>p</code> and a sequence <code>xs</code>, returns a pair whose first element
is the longest prefix (possibly empty) of <code>xs</code> of elements that
<em>do not satisfy</em> <code>p</code> and the second element is the remainder of
the sequence.
</p><p><code><code><a href="Data-Sequence.html#v:breakl">breakl</a></code> p</code> is equivalent to <code><code><a href="Data-Sequence.html#v:spanl">spanl</a></code> (not . p)</code>.
</p></div></div><div class="top"><p class="src"><a name="v:breakr" class="def">breakr</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> (<a href="Data-Sequence.html#t:Seq">Seq</a> a, <a href="Data-Sequence.html#t:Seq">Seq</a> a)</p><div class="doc"><p><code><code><a href="Data-Sequence.html#v:breakr">breakr</a></code> p</code> is equivalent to <code><code><a href="Data-Sequence.html#v:spanr">spanr</a></code> (not . p)</code>.
</p></div></div><div class="top"><p class="src"><a name="v:partition" class="def">partition</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> (<a href="Data-Sequence.html#t:Seq">Seq</a> a, <a href="Data-Sequence.html#t:Seq">Seq</a> a)</p><div class="doc"><p><em>O(n)</em>. The <code><a href="Data-Sequence.html#v:partition">partition</a></code> function takes a predicate <code>p</code> and a
sequence <code>xs</code> and returns sequences of those elements which do and
do not satisfy the predicate.
</p></div></div><div class="top"><p class="src"><a name="v:filter" class="def">filter</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><em>O(n)</em>. The <code><a href="Data-Sequence.html#v:filter">filter</a></code> function takes a predicate <code>p</code> and a sequence
<code>xs</code> and returns a sequence of those elements which satisfy the
predicate.
</p></div></div><h1 id="g:10">Sorting
</h1><div class="top"><p class="src"><a name="v:sort" class="def">sort</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><em>O(n log n)</em>. <code><a href="Data-Sequence.html#v:sort">sort</a></code> sorts the specified <code><a href="Data-Sequence.html#t:Seq">Seq</a></code> by the natural
ordering of its elements. The sort is stable.
If stability is not required, <code><a href="Data-Sequence.html#v:unstableSort">unstableSort</a></code> can be considerably
faster, and in particular uses less memory.
</p></div></div><div class="top"><p class="src"><a name="v:sortBy" class="def">sortBy</a> :: (a -> a -> <a href="../base-4.5.1.0/Data-Ord.html#t:Ordering">Ordering</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><em>O(n log n)</em>. <code><a href="Data-Sequence.html#v:sortBy">sortBy</a></code> sorts the specified <code><a href="Data-Sequence.html#t:Seq">Seq</a></code> according to the
specified comparator. The sort is stable.
If stability is not required, <code><a href="Data-Sequence.html#v:unstableSortBy">unstableSortBy</a></code> can be considerably
faster, and in particular uses less memory.
</p></div></div><div class="top"><p class="src"><a name="v:unstableSort" class="def">unstableSort</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><em>O(n log n)</em>. <code><a href="Data-Sequence.html#v:unstableSort">unstableSort</a></code> sorts the specified <code><a href="Data-Sequence.html#t:Seq">Seq</a></code> by
the natural ordering of its elements, but the sort is not stable.
This algorithm is frequently faster and uses less memory than <code><a href="Data-Sequence.html#v:sort">sort</a></code>,
and performs extremely well -- frequently twice as fast as <code><a href="Data-Sequence.html#v:sort">sort</a></code> --
when the sequence is already nearly sorted.
</p></div></div><div class="top"><p class="src"><a name="v:unstableSortBy" class="def">unstableSortBy</a> :: (a -> a -> <a href="../base-4.5.1.0/Data-Ord.html#t:Ordering">Ordering</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><em>O(n log n)</em>. A generalization of <code><a href="Data-Sequence.html#v:unstableSort">unstableSort</a></code>, <code><a href="Data-Sequence.html#v:unstableSortBy">unstableSortBy</a></code>
takes an arbitrary comparator and sorts the specified sequence.
The sort is not stable. This algorithm is frequently faster and
uses less memory than <code><a href="Data-Sequence.html#v:sortBy">sortBy</a></code>, and performs extremely well --
frequently twice as fast as <code><a href="Data-Sequence.html#v:sortBy">sortBy</a></code> -- when the sequence is already
nearly sorted.
</p></div></div><h1 id="g:11">Indexing
</h1><div class="top"><p class="src"><a name="v:index" class="def">index</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> a</p><div class="doc"><p><em>O(log(min(i,n-i)))</em>. The element at the specified position,
counting from 0. The argument should thus be a non-negative
integer less than the size of the sequence.
If the position is out of range, <code><a href="Data-Sequence.html#v:index">index</a></code> fails with an error.
</p></div></div><div class="top"><p class="src"><a name="v:adjust" class="def">adjust</a> :: (a -> a) -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><em>O(log(min(i,n-i)))</em>. Update the element at the specified position.
If the position is out of range, the original sequence is returned.
</p></div></div><div class="top"><p class="src"><a name="v:update" class="def">update</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><em>O(log(min(i,n-i)))</em>. Replace the element at the specified position.
If the position is out of range, the original sequence is returned.
</p></div></div><div class="top"><p class="src"><a name="v:take" class="def">take</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><em>O(log(min(i,n-i)))</em>. The first <code>i</code> elements of a sequence.
If <code>i</code> is negative, <code><code><a href="Data-Sequence.html#v:take">take</a></code> i s</code> yields the empty sequence.
If the sequence contains fewer than <code>i</code> elements, the whole sequence
is returned.
</p></div></div><div class="top"><p class="src"><a name="v:drop" class="def">drop</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><em>O(log(min(i,n-i)))</em>. Elements of a sequence after the first <code>i</code>.
If <code>i</code> is negative, <code><code><a href="Data-Sequence.html#v:drop">drop</a></code> i s</code> yields the whole sequence.
If the sequence contains fewer than <code>i</code> elements, the empty sequence
is returned.
</p></div></div><div class="top"><p class="src"><a name="v:splitAt" class="def">splitAt</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> (<a href="Data-Sequence.html#t:Seq">Seq</a> a, <a href="Data-Sequence.html#t:Seq">Seq</a> a)</p><div class="doc"><p><em>O(log(min(i,n-i)))</em>. Split a sequence at a given position.
<code><code><a href="Data-Sequence.html#v:splitAt">splitAt</a></code> i s = (<code><a href="Data-Sequence.html#v:take">take</a></code> i s, <code><a href="Data-Sequence.html#v:drop">drop</a></code> i s)</code>.
</p></div></div><h2 id="g:12">Indexing with predicates
</h2><div class="doc"><p>These functions perform sequential searches from the left
or right ends of the sequence, returning indices of matching
elements.
</p></div><div class="top"><p class="src"><a name="v:elemIndexL" class="def">elemIndexL</a> :: <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> a => a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></p><div class="doc"><p><code><a href="Data-Sequence.html#v:elemIndexL">elemIndexL</a></code> finds the leftmost index of the specified element,
if it is present, and otherwise <code><a href="../base-4.5.1.0/Data-Maybe.html#v:Nothing">Nothing</a></code>.
</p></div></div><div class="top"><p class="src"><a name="v:elemIndicesL" class="def">elemIndicesL</a> :: <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> a => a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> [<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>]</p><div class="doc"><p><code><a href="Data-Sequence.html#v:elemIndicesL">elemIndicesL</a></code> finds the indices of the specified element, from
left to right (i.e. in ascending order).
</p></div></div><div class="top"><p class="src"><a name="v:elemIndexR" class="def">elemIndexR</a> :: <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> a => a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></p><div class="doc"><p><code><a href="Data-Sequence.html#v:elemIndexR">elemIndexR</a></code> finds the rightmost index of the specified element,
if it is present, and otherwise <code><a href="../base-4.5.1.0/Data-Maybe.html#v:Nothing">Nothing</a></code>.
</p></div></div><div class="top"><p class="src"><a name="v:elemIndicesR" class="def">elemIndicesR</a> :: <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> a => a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> [<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>]</p><div class="doc"><p><code><a href="Data-Sequence.html#v:elemIndicesR">elemIndicesR</a></code> finds the indices of the specified element, from
right to left (i.e. in descending order).
</p></div></div><div class="top"><p class="src"><a name="v:findIndexL" class="def">findIndexL</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></p><div class="doc"><p><code><code><a href="Data-Sequence.html#v:findIndexL">findIndexL</a></code> p xs</code> finds the index of the leftmost element that
satisfies <code>p</code>, if any exist.
</p></div></div><div class="top"><p class="src"><a name="v:findIndicesL" class="def">findIndicesL</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> [<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>]</p><div class="doc"><p><code><code><a href="Data-Sequence.html#v:findIndicesL">findIndicesL</a></code> p</code> finds all indices of elements that satisfy <code>p</code>,
in ascending order.
</p></div></div><div class="top"><p class="src"><a name="v:findIndexR" class="def">findIndexR</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></p><div class="doc"><p><code><code><a href="Data-Sequence.html#v:findIndexR">findIndexR</a></code> p xs</code> finds the index of the rightmost element that
satisfies <code>p</code>, if any exist.
</p></div></div><div class="top"><p class="src"><a name="v:findIndicesR" class="def">findIndicesR</a> :: (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> [<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>]</p><div class="doc"><p><code><code><a href="Data-Sequence.html#v:findIndicesR">findIndicesR</a></code> p</code> finds all indices of elements that satisfy <code>p</code>,
in descending order.
</p></div></div><h1 id="g:13">Folds
</h1><div class="doc"><p>General folds are available via the <code><a href="../base-4.5.1.0/Data-Foldable.html#t:Foldable">Foldable</a></code> instance of <code><a href="Data-Sequence.html#t:Seq">Seq</a></code>.
</p></div><div class="top"><p class="src"><a name="v:foldlWithIndex" class="def">foldlWithIndex</a> :: (b -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> a -> b) -> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> b</p><div class="doc"><p><code><a href="Data-Sequence.html#v:foldlWithIndex">foldlWithIndex</a></code> is a version of <code><a href="../base-4.5.1.0/Data-Foldable.html#v:foldl">foldl</a></code> that also provides access
to the index of each element.
</p></div></div><div class="top"><p class="src"><a name="v:foldrWithIndex" class="def">foldrWithIndex</a> :: (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> a -> b -> b) -> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> b</p><div class="doc"><p><code><a href="Data-Sequence.html#v:foldrWithIndex">foldrWithIndex</a></code> is a version of <code><a href="../base-4.5.1.0/Data-Foldable.html#v:foldr">foldr</a></code> that also provides access
to the index of each element.
</p></div></div><h1 id="g:14">Transformations
</h1><div class="top"><p class="src"><a name="v:mapWithIndex" class="def">mapWithIndex</a> :: (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> a -> b) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> b</p><div class="doc"><p>A generalization of <code><a href="../base-4.5.1.0/Control-Monad.html#v:fmap">fmap</a></code>, <code><a href="Data-Sequence.html#v:mapWithIndex">mapWithIndex</a></code> takes a mapping function
that also depends on the element's index, and applies it to every
element in the sequence.
</p></div></div><div class="top"><p class="src"><a name="v:reverse" class="def">reverse</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> a</p><div class="doc"><p><em>O(n)</em>. The reverse of a sequence.
</p></div></div><h2 id="g:15">Zips
</h2><div class="top"><p class="src"><a name="v:zip" class="def">zip</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> (a, b)</p><div class="doc"><p><em>O(min(n1,n2))</em>. <code><a href="Data-Sequence.html#v:zip">zip</a></code> takes two sequences and returns a sequence
of corresponding pairs. If one input is short, excess elements are
discarded from the right end of the longer sequence.
</p></div></div><div class="top"><p class="src"><a name="v:zipWith" class="def">zipWith</a> :: (a -> b -> c) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> c</p><div class="doc"><p><em>O(min(n1,n2))</em>. <code><a href="Data-Sequence.html#v:zipWith">zipWith</a></code> generalizes <code><a href="Data-Sequence.html#v:zip">zip</a></code> by zipping with the
function given as the first argument, instead of a tupling function.
For example, <code>zipWith (+)</code> is applied to two sequences to take the
sequence of corresponding sums.
</p></div></div><div class="top"><p class="src"><a name="v:zip3" class="def">zip3</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> c -> <a href="Data-Sequence.html#t:Seq">Seq</a> (a, b, c)</p><div class="doc"><p><em>O(min(n1,n2,n3))</em>. <code><a href="Data-Sequence.html#v:zip3">zip3</a></code> takes three sequences and returns a
sequence of triples, analogous to <code><a href="Data-Sequence.html#v:zip">zip</a></code>.
</p></div></div><div class="top"><p class="src"><a name="v:zipWith3" class="def">zipWith3</a> :: (a -> b -> c -> d) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> c -> <a href="Data-Sequence.html#t:Seq">Seq</a> d</p><div class="doc"><p><em>O(min(n1,n2,n3))</em>. <code><a href="Data-Sequence.html#v:zipWith3">zipWith3</a></code> takes a function which combines
three elements, as well as three sequences and returns a sequence of
their point-wise combinations, analogous to <code><a href="Data-Sequence.html#v:zipWith">zipWith</a></code>.
</p></div></div><div class="top"><p class="src"><a name="v:zip4" class="def">zip4</a> :: <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> c -> <a href="Data-Sequence.html#t:Seq">Seq</a> d -> <a href="Data-Sequence.html#t:Seq">Seq</a> (a, b, c, d)</p><div class="doc"><p><em>O(min(n1,n2,n3,n4))</em>. <code><a href="Data-Sequence.html#v:zip4">zip4</a></code> takes four sequences and returns a
sequence of quadruples, analogous to <code><a href="Data-Sequence.html#v:zip">zip</a></code>.
</p></div></div><div class="top"><p class="src"><a name="v:zipWith4" class="def">zipWith4</a> :: (a -> b -> c -> d -> e) -> <a href="Data-Sequence.html#t:Seq">Seq</a> a -> <a href="Data-Sequence.html#t:Seq">Seq</a> b -> <a href="Data-Sequence.html#t:Seq">Seq</a> c -> <a href="Data-Sequence.html#t:Seq">Seq</a> d -> <a href="Data-Sequence.html#t:Seq">Seq</a> e</p><div class="doc"><p><em>O(min(n1,n2,n3,n4))</em>. <code><a href="Data-Sequence.html#v:zipWith4">zipWith4</a></code> takes a function which combines
four elements, as well as four sequences and returns a sequence of
their point-wise combinations, analogous to <code><a href="Data-Sequence.html#v:zipWith">zipWith</a></code>.
</p></div></div></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.11.0</p></div></body></html>
distrib
>
Mageia
>
5
>
i586
>
media
>
core-release
>
by-pkgid
>
6e204a966e8c42d976f99a1700ce5f20
>
files
>
2593
