Functional C#: Writing a 'partition' function
One of the more interesting higher order functions that I've come across while playing with F# is the partition function which is similar to the filter function except it returns the values which meet the predicate passed in as well as the ones which don't.
I came across an interesting problem recently where we needed to do exactly this and had ended up taking a more imperative for each style approach to solve the problem because this function doesn't exist in C# as far as I know.
In F# the function makes use of a tuple to do this so if we want to create the function in C# then we need to define a tuple object first.
public class Tuple<TFirst, TSecond> { private readonly TFirst first; private readonly TSecond second; public Tuple(TFirst first, TSecond second) { this.first = first; this.second = second; } public TFirst First { get { return first; } } public TSecond Second { get { return second; } } }
public static class IEnumerableExtensions { public static Tuple<IEnumerable<T>, IEnumerable<T>> Partition<T>(this IEnumerable<T> enumerableOf, Func<T, bool> predicate) { var positives = enumerableOf.Where(predicate); var negatives = enumerableOf.Where(e => !predicate(e)); return new Tuple<IEnumerable<T>, IEnumerable<T>>(positives, negatives); } }
I'm not sure of the best way to write this function – at the moment we end up creating two iterators to cover the two different filters that we're running over the collection which seems a bit strange.
In F# 'partition' is on List so the whole collection would be evaluated whereas in this case we're still only evaluating each item as it's needed so maybe there isn't a way to do it without using two iterators.
If we wanted to use this function to get the evens and odds from a collection we could write the following code:
var evensAndOdds = Enumerable.Range(1, 10).Partition(x => x % 2 == 0); var evens = evensAndOdds.First; var odds = evensAndOdds.Second;
The other thing that's nice about F# is that we can assign the result of the expression to two separate values in one go and I don't know of a way to do that in C#.
let evens, odds = [1..10] |> List.partition (fun x -> x % 2 = 0)
We don't need to have the intermediate variable 'evensAndOdds' which doesn't really add much to the code.
I'd be interested in knowing if there's a better way to do this than what I'm trying out.
Multiple assignment & partitioning: fun to use …here is an example in Groovy:
def (evens,odds) = list.split(){ it % 2 == 0 }
Philip Schwarz
2 Feb 10 at 12:02 am
This is pretty useful, and I agree it would be really nice to have that initialization of both variables in one without wrapping in the Tuple class.
I guess you could achieve what you want with out params, but it will make you feel dirty.
Chris Owen
2 Feb 10 at 12:12 am
I guess this is more Succinct.
public static Tuple<IEnumerable, IEnumerable> Partition(this IEnumerable enumerableOf, Func predicate)
{
var partitioned = enumerableOf.GroupBy(predicate).Select(e => new {e.Key, e});
return new Tuple<IEnumerable, IEnumerable>(partitioned.First().e, partitioned.Last().e);
}
Naveen
2 Feb 10 at 4:23 am
I thought the new version of .NET (4.0) had tuples?
Manuel
2 Feb 10 at 8:30 am
[...] Functional C#: Writing a 'partition' function – Mark Needham continues his series looking at writing more functional code in C# with a look at the implementation of a partition function to allow collections to be split. [...]
The Morning Brew - Chris Alcock » The Morning Brew #530
2 Feb 10 at 8:41 am
@Manuel, yeah it does see http://blogs.msdn.com/bclteam/archive/2009/07/07/building-tuple-matt-ellis.aspx for more info. But I guess this code is from a .NET 3.5 project.
Matt Warren
2 Feb 10 at 11:25 am
Apart from the multiple variable assignment, couldn't this be considered a kind of GroupBy?
var evensAndOdds = Enumerable.Range(1, 10).GroupBy(n => n%2==0);
or something like
var evensAndOdds = Enumerable.Range(1, 10).Select(n => new {number=n,first=(n%2==0)});
var evens = evensAndOdds.Where(n => n.first).Select(n => new { n.number });
var odds = evensAndOdds.Where(n => !n.first).Select(n => new { n.number });
Jonas Elfström
2 Feb 10 at 2:38 pm
@Philip Schwarz, yes and powerful. Had to check out if Ruby has it.
evens,odds=(1..10).partition{|n| n%2==0}
Not a character wasted and still clear (at least for me).
Jonas Elfström
3 Feb 10 at 8:54 am
@Jonas Elfström: I'd say some characters are wasted compared to what you get with Scala's _ placeholder:
// In hypothetical Scala/Ruby hybrid syntax:
evens,odds = (1..10) partition ( _%2==0)
Manuel
3 Feb 10 at 3:57 pm
@Naveen, your GroupBy variant assumes that you'll always have both positive and negative matches. If they all match positive or all match negative, your First and Second will be the same. And checking against an empty set of objects will result in exceptions.
Thomas G Mayfield
3 Feb 10 at 9:35 pm
[...] exemple concret de problème posé par l’énumération multiple est la création d’un opérateur de partitionnement d’énumérable. Dans l’exemple donné dans cet article, on peut voir que l’énumérable passé en source est [...]
Rx: MemoizeAll , Jerome Laban
4 Feb 10 at 5:24 am
@Jonas, @Manuel
The following Scala also works:
val (evens,odds) = 0 to 10 partition ( _ % 2 == 0)
Philip Schwarz
4 Feb 10 at 11:45 pm