Partition - 7 higher order functions

Here's my third blog post in my serie about higher order functions. Partition is one of those higher order functinos that I always forget about and unnecessarily reinvent the wheel.

• map
• fold
• partition
• reduce
• expand
• collect
• scan

Partition

This higher order function splits a list into several lists using a function to discriminate what list item goes in what list. It is basically a bucket sort. This doesn't exist in the .NET Framework by default, as far as I know. If you want this functionality you may copy/paste my implementation below.

Examples

You have a list of people and want to display them in age groups.

var people = new List<Person>
{
    new Person(name: "A", age: 12),
    new Person(name: "B", age: 23),
    new Person(name: "C", age: 43),
    new Person(name: "D", age: 65),
    new Person(name: "E", age: 33),
};


var parts = people.Partition(p => p.Age < 25 ? 0 : 1);

var under25 = parts[0]; // A, B
var over25 = parts[1]; // C, D, E

This function is build into F# and there returns a touple. This makes it extremely slick to handle the partition result.

let evens, odds = [1..10] |> List.partition (fun i -> i % 2 = 0)


val odds : int list = [1; 3; 5; 7; 9]
val evens : int list = [2; 4; 6; 8; 10]

What happens, is that partition returns a tuple of the two parts, and F# automatically divides the tuple into two values for us. Not only beautiful, but also very useful.

Implementation

With C# I find it more useful to return an array with parts, instead of a tuple, because the tuple isn't very well implemented in C#.

public static IEnumerable<T>[] Partition<T>(Func<T, int> fn, IEnumerable<T> list)
{
    if (list == null)
    {
        throw new ArgumentNullException("list", "Supplied list to Partition is not allowed to be null");
    }

if (fn == null)
{
    throw new ArgumentNullException(&quot;fn&quot;, &quot;Supplied function to Partition is not allowed to be null&quot;);
}

// Expand the array arr to fit index i
Func&lt;IList&lt;T&gt;[], int, IList&lt;T&gt;[]&gt; expand = (arr, i) =&gt;
{
    var newArray = new IList&lt;T&gt;[i + 1];
    Array.Copy(arr, newArray, arr.Length);

    // Initialize new array
    for (var k = arr.Length; k &lt; newArray.Length; k++)
    {
        newArray[k] = new List&lt;T&gt;();
    }

    return newArray;
};

var result = new IList&lt;T&gt;[0];
foreach (var item in list)
{
    var index = fn(item);
    if (index &lt; 0)
    {
        throw new IndexOutOfRangeException(&quot;Your partition function returned index less than 0&quot;);
    }

    // new index
    if (index &gt; result.Length - 1)
    {
        // expand array
        result = expand(result, index);
    }

    result[index].Add(item);
}

return result;

}

public static IEnumerable<T>[] Partition<T>(this IEnumerable<T> list, Func<T, int> fn)
{
    return Partition(fn, list);
}

The real problem here is expanding the array, because we don't know how many parts we're intending to return. We could use a predicate function and lock the result down to two parts, but that wouldn't be as useful as this.

Conclusion

When you need to split a list into several lists by some discriminating value, the partition function is your friend, simply because it is shorter than throwing out the foreach. It communicates the purpose of your code and makes it clearer to your readers.