Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
781 views
in Technique[技术] by (71.8m points)

c# - Split a list into sublist by checking a condition on elements

Suppose I have an array of integeres and I want to split it into several parts, and I want to use zero as the condition on when to break. Something like this :

[1,2,3,0,4,5,0,6,7] => [[1,2,3,0], [4,5,0], [6,7]]

Well, it can be easily done using two for loops, but I wanted to know if it's possible to do this with LINQ.

There's a couple of question like this[1],[2], but as opposed to this one, they rely on a condition that's been provided from outside of the list.

Note: I know it's not polite to ask more than one question in a thread, but if anyone out there is familiar with functional programming ( since in it's essence, it's really an FP question ), I'd also like to see their perspective and possible solutions for this problem.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

You have a dependency between separate elements of your collection, specifically, for each element you want to know "was the previous element a zero?". As soon as your query depends on the previous element (or, more generally, as soon as your query depends on other elements of the same sequence), you should reach for Aggregate (or in more general functional programming terms, fold). This is because Aggregate, unlike other LINQ operators, allows you to carry state with you from one iteration to the next.

So, to answer your question, I'd write this query as follows in LINQ.

// assume our list of integers it called values
var splitByZero = values.Aggregate(new List<List<int>>{new List<int>()},
                                   (list, value) => {
                                       list.Last().Add(value);
                                       if (value == 0) list.Add(new List<int>());
                                       return list;
                                   });

I'll break this down into parts so I can better explain my thinking.

values.Aggregate(new List<List<int>>{new List<int>()},

As I said before, reach for Aggregate because we need to carry state. Putting a new empty list into our List of Lists removes an edge case of the List<List<int>> having no lists in it.

(list, value) => {...}

Again, looking at the signature of our lambda expression (which is Func<List<List<int>>, int, List<List<int>>), we can see the state passing explicitly: we accept a List<List<int>> and return the same.

list.Last().Add(value);

Since we always want to work on the most recent List<int>, we get the Last() element of our list of lists (which will never be null due to the section above).

if (value == 0) list.Add(new List<int>());

This is where we do the splitting - on the next iteration, the call to Last() will return this new list.

return list;

And we finally pass the state on to the next iteration.


This could be generalized with little difficulty, in a SplitOn method, as follows:

public static IEnumerable<IEnumerable<T>> SplitOn<T>(this IEnumerable<T> source, Func<T, bool> predicate)
{
    return source.Aggregate(new List<List<T>> {new List<T>()},
                            (list, value) =>
                                {
                                    list.Last().Add(value);
                                    if (predicate(value)) list.Add(new List<T>());
                                    return list;
                                });
}

The version using IEnumerable's instead of List's is somewhat less clear because of the way Enumerables work, but again, isn't particularly hard to create from the above code, and looks like (simplified just a touch via a ternary operator):

public static IEnumerable<IEnumerable<T>> SplitOn<T>(this IEnumerable<T> source, Func<T, bool> predicate)
{
    return source.Aggregate(Enumerable.Repeat(Enumerable.Empty<T>(), 1),
                            (list, value) =>
                                {
                                    list.Last().Concat(Enumerable.Repeat(value, 1));
                                    return predicate(value) ? list.Concat(Enumerable.Repeat(Enumerable.Empty<T>(), 1)) : list;
                                });
}

You also might find Haskell's implementation of splitOn interesting, as it does exactly what you want. I would call it nontrivial (to put it lightly).


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...