How to split a sequence according to a predicate?
<p>I very often run into the need to split a sequence into the two subsequences of elements that satisfy and don't satisfy a given predicate (preserving the original relative ordering).</p>

<p>This hypothetical "splitter" function would look something like this in action:</p>

<pre><code>&gt;&gt;&gt; data = map(str, range(14))
&gt;&gt;&gt; pred = lambda i: int(i) % 3 == 2
&gt;&gt;&gt; splitter(data, pred)
[('2', '5', '8', '11'), ('0', '1', '3', '4', '6', '7', '9', '10', '12', '13')]
</code></pre>

<p>My question is:</p>

<blockquote>
  <p>does Python already have a standard/built-in way to do this?</p>
</blockquote>

<p>This functionality is certainly not difficult to code (see Addendum below), but for a number of reasons, I'd prefer to use a standard/built-in method than a self-rolled one.</p>

<p>Thanks!</p>

<p><br/>
<br/>
Addendum: </p>

<p>The best standard function I've found so far for handling this task in Python is <code>itertools.groupby</code>.  To use it for this particular task however, it is necessary to call the predicate function twice for each list member, which I find annoyingly silly:</p>

<pre><code>&gt;&gt;&gt; import itertools as it
&gt;&gt;&gt; [tuple(v[1]) for v in it.groupby(sorted(data, key=pred), key=pred)]
[('0', '1', '3', '4', '6', '7', '9', '10', '12', '13'), ('2', '5', '8', '11')]
</code></pre>

<p>(The last output above differs from the desired one shown earlier in that the subsequence of elements that satisfy the predicate comes last rather than first, but this is very minor, and very easy to fix if needed.)</p>

<p>One can avoid the redundant calls to the predicate (by doing, basically, an "inline memoization"), but my best stab at this gets pretty elaborate, a far cry from the simplicity of <code>splitter(data, pred)</code>:</p>

<pre><code>&gt;&gt;&gt; first = lambda t: t[0]
&gt;&gt;&gt; [zip(*i[1])[1] for i in it.groupby(sorted(((pred(x), x) for x in data),
... key=first), key=first)]
[('0', '1', '3', '4', '6', '7', '9', '10', '12', '13'), ('2', '5', '8', '11')]
</code></pre>

<p>BTW, if you don't care about preserving the original ordering, <code>sorted</code>'s default sort order gets the job done (so the <code>key</code> parameter may be omitted from the <code>sorted</code> call):</p>

<pre><code>&gt;&gt;&gt; [zip(*i[1])[1] for i in it.groupby(sorted(((pred(x), x) for x in data)),
... key=first)]
[('0', '1', '3', '4', '6', '7', '9', '10', '12', '13'), ('2', '5', '8', '11')]
</code></pre>
