Mark Needham

Thoughts on Software Development

Functional C#: Writing a ‘partition’ function

with 12 comments

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.

Be Sociable, Share!

Written by Mark Needham

February 1st, 2010 at 11:34 pm

Posted in .NET

Tagged with , ,

  • Philip Schwarz

    Multiple assignment & partitioning: fun to use …here is an example in Groovy:

    def (evens,odds) = list.split(){ it % 2 == 0 }

  • 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.

  • 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);
    }

  • Manuel

    I thought the new version of .NET (4.0) had tuples?

  • Pingback: The Morning Brew - Chris Alcock » The Morning Brew #530()

  • Matt Warren

    @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.

  • 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 });

  • @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).

  • Manuel

    @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)

  • Thomas G Mayfield

    @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.

  • Pingback: Rx: MemoizeAll , Jerome Laban()

  • Philip Schwarz

    @Jonas, @Manuel

    The following Scala also works:

    val (evens,odds) = 0 to 10 partition ( _ % 2 == 0)