Split IEnumerable by predicate In order to divide an IEnumerable in C# by a predicate, I implemented the following (in a static class):

public static IEnumerable&lt;IEnumerable&lt;T&gt;&gt; SplitBeforeIf&lt;T&gt;(this IEnumerable&lt;T&gt; input, Func&lt;T, bool&gt; pred)
{
    //This exists to store the predicate satisfier, which I kept as
    //the first T in the inner IEnumerable (except, maybe the first one).
    T predSatis = default(T);
    while(input.Any())
    {
        var temp = input.TakeWhile(v =&gt; !pred(v));
        //I was told that the below is the best test for default-ness.
        //(I assume that pred(default(T)) is always false.)
        if(predSatis == null || predSatis.Equals(default(T)))
            yield return temp;
        else
            yield return (new List&lt;T&gt;{predSatis}).Concat(temp);

        input = input.SkipWhile(v =&gt; !pred(v));
        predSatis = input.FirstOrDefault();
        input = input.Skip(1);
    }
    if(predSatis != null &amp;&amp; !predSatis.Equals(default(T)))
        yield return new List&lt;T&gt;{predSatis};
}


This returns as follows:


new List&lt;int&gt;{1,2,3,4,5}.SplitBeforeIf(v =&gt; v % 2 == 0) gives {{1}, {2,3}, {4,5}}
new List&lt;int&gt;{6,1,2,3,4,5}.SplitBeforeIf(v =&gt; v % 2 == 0) gives {{}, {6, 1}, {2,3}, {4, 5}}
new List&lt;int&gt;{1,2,3,4,5,6}.SplitBeforeIf(v =&gt; v % 2 == 0) gives {{1}, {2,3}, {4,5}, {6}}.


I have 3 questions (besides any other comments on the code):


I see that, despite my best efforts, this is \$O(n^2)\$. Why? Can this be improved for a generic IEnumerable?
This does not support a stateful predicate or a stateful IEnumerable input. Can this be remedied?
This looks awfully like Clojure's partition-by. How does Clojure avoid the first issue (it may also have the second, but functional programming dislikes state anyway)?


Being a little pedantic about these things, I also would prefer solutions that don't accumulate values into another data structure (just to see if full laziness is possible).
So I thought I'd try this out with a test enumerable.

public class NumberValues : IEnumerable&lt;int&gt;
{
    public NumberValues(int startValue, int endValue)
    {
        _endValue = endValue;
        _startValue = startValue;
        counter = 0;
    }
    public NumberValues(int endValue) : this(0, 10) { }

    public int counter { get; set; }

    public IEnumerator&lt;int&gt; GetEnumerator()
    {

        var iterator = _startValue;
        while (iterator &lt; _endValue)
        {
            Trace.Write(iterator + ",");
            iterator++;
            counter++;
            yield return iterator;
        }

    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}


followed closely by

    [TestCase(0,5)]
    [TestCase(1,5)]
    [TestCase(0,6)]
    [TestCase(1,6)]
    [TestCase(0,10)]
    [TestCase(1,10)]
    public void TestSkipBeforeIf(int start, int end)
    {
        var numberValue = new NumberValues(start,end);
        numberValue.SplitBeforeIf(i =&gt; i%2 == 0).ToList();
    }


which results in the following output.

0,5 &gt; 0,0,1,0,1,2,0,1,2,3,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,  - 25
1,5 &gt; 1,1,1,2,1,2,3,1,2,3,4,1,2,3,4,1,2,3,4,  - 19
0,6 &gt; 0,0,1,0,1,2,0,1,2,3,0,1,2,3,4,0,1,2,3,4,5,0,1,2,3,4,5,  - 27
1,6 &gt; 1,1,1,2,1,2,3,1,2,3,4,1,2,3,4,5,1,2,3,4,5,  - 21
0,10 &gt; 0,0,1,0,1,2,0,1,2,3,0,1,2,3,4,0,1,2,3,4,5,0,1,2,3,4,5,6,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,8,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,  - 65
1,10 &gt;     1,1,1,2,1,2,3,1,2,3,4,1,2,3,4,5,1,2,3,4,5,6,1,2,3,4,5,6,7,1,2,3,4,5,6,7,8,1,2,3,,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,  - 55

0,20 &gt; 230
0,40 &gt; 860
0,100 &gt; 5150


But why?

        while (input.Any())
        {
            var temp = input.TakeWhile(v =&gt; !pred(v));
            if (predSatis == null || predSatis.Equals(default(T)))
                yield return temp;
            else
                yield return (new List&lt;T&gt; { predSatis }).Concat(temp);

            input = input.SkipWhile(v =&gt; !pred(v));
            predSatis = input.FirstOrDefault();
            input = input.Skip(1);
        }


if you evaluate your 2 lines

input = input.SkipWhile(v =&gt; !pred(v));
predSatis = input.FirstOrDefault();


over iterations of your while loop, it is necessary to expand the input variable for each iteration.

input.SkipWhile(pred).FirstOrDefault
input.SkipWhile(pred).SkipWhile(pred).FirstOrDefault
input.SkipWhile(pred).SkipWhile(pred).SkipWhile(pred).FirstOrDefault
input.SkipWhile(pred).SkipWhile(pred).SkipWhile(pred).SkipWhile(pred).FirstOrDefault


having seen this, we now consider the evaluation of input.SkipWhile(!pred)

so over 100 iterations

pred = x =&gt; x % 2 == 0 : 5150
pred = x =&gt; x % 3 == 0 : 3600
pred = x =&gt; x % 4 == 0 : 2625
pred = x =&gt; x % 5 == 0 : 2120
pred = x =&gt; x % 6 == 0 : 1849
pred = x =&gt; x % 15 == 0 : 837
pred = x =&gt; x % 20 == 0 : 605
pred = x =&gt; x % 25 == 0 : 504
pred = x =&gt; x % 30 == 0 : 564
pred = x =&gt; x % 30 == 0 : 413


Your functions behaviour is therefore dependent not just on the size of your data, but on the form of your predicate.

For your own analysis, this is what I used for evaluating the predicate

   [TestCase(1,5000,10)]
   public void TestSkipBeforeIf(int start, int end, int mod)
   {
        var numberValue = new NumberValues(start,end);
        numberValue.SplitBeforeIf(i =&gt; i%mod == 0).ToList();
   }


I'm not clear what you meant by stateful predicate or IEnumerable, however in terms of the IEnumerable I have maintained a count as state. Similarly I could maintain a count for the pred, or add some bizarre checking behaviour.

Func&lt;object, int, bool&gt; predStateful = (y,x) =&gt;
{
    if (x == y.Check(x))
    {
        return false;
    }
    return x%mod == 0;
};
Func&lt;int, bool&gt; pred = x =&gt; predStateful(MyCheckingObject,x);
numberValue.SplitBeforeIf(pred).ToList();


Thanks for the interesting question.

EDIT: Modified Chunk function using a predicate. 
original 

    public static IEnumerable&lt;IEnumerable&lt;TValue&gt;&gt; Chunk&lt;TValue&gt;(
                    this IEnumerable&lt;TValue&gt; values,
                    Func&lt;TValue,bool&gt; pred)
    {
        using (var enumerator = values.GetEnumerator())
        {
            while (enumerator.MoveNext())
            {
                yield return GetChunk(enumerator, pred).ToList();
            }
        }
    }
    private static IEnumerable&lt;T&gt; GetChunk&lt;T&gt;(
                     IEnumerator&lt;T&gt; enumerator,
                     Func&lt;T,bool&gt; pred)
    {
        do
        {
            yield return enumerator.Current;
        } while (!pred(enumerator.Current) &amp;&amp; enumerator.MoveNext());
    }