Reduce Redux

By Sam Page
Published on February 25th, 2009

«Lambda Functions
xX
FinQ Stats»
2 Comments

Reduce is a powerful function pattern. In fact, it can be used as the base implementation for both Filter and Map. That’s what we’ll do to take our functional library to the next level of functional goodness.

We initially had Reduce take a list of many values and produce a single value, an aggregate, but there’s nothing stopping us from returning a list of values. To accomplish this, we can have the Reduce initial value parameter be an empty “result” list, and then have the aggregation function push result items onto the list as it processes the input sequence.

In the implementations of Filter and Map below, a lambda function is created that wraps the predicate passed to Filter or the conversion passed to Map. In addition, the call to Reduce itself creates the initial empty result sequence required and returns it as the reduction result. 

/// <summary>
/// Reduce uses an initial value and an accumulation function to
/// build a result value from a sequence. In LINQ, Aggregate().
/// </summary>
public static R Reduce<T, R>(this IEnumerable<T> list, R init, Agg<T, R> agg)
{
    R result = init;

    if( null == list ) return result;

    foreach (T it in list)
        result = agg(it, result);

    return result;
}

/// <summary>
/// Filter uses a predicate function to conditionally copy elements
/// from an input sequence. In LINQ, Where().
/// </summary>
public static IEnumerable<T> Filter<T>(this IEnumerable<T> list, Pred<T> pred)
{
    return list.Reduce(new List<T>(), (it, result) =>
        {
            if (pred(it))
                result.Add(it);
            return result;
        });
}

/// <summary>
/// Map uses a conversion function to build a result sequence from an
/// input sequence. In LINQ, Select()
/// </summary>
public static IEnumerable<R> Map<T, R>(this IEnumerable<T> list, Conv<T, R> conv)
{
    return list.Reduce(new List<R>(), (it, result) =>
        {
            result.Add(conv(it));
            return result;
        });
}

Having Reduce as the basis for Filter and Map (and just about everything else in the FinQ library) is elegant coding. And it also allows us to make some deep design experiments which is good for exploring C# features. I’m curious to take a good look at the C# yield performance compared to straight iteration. A recursive Reduce will also be interesting. I’ll look at those in a future post.


Comments

2 Responses to “Reduce Redux”

  1. Dan Says:
    March 12th, 2009 at 10:36 am

    My understanding is that what you’re calling reduce is more commonly called fold. (There is also a reduce with the same semantics in, say, python, so you’re not really off track.) People who know more than me also call it a catamorphism.

    Here’s an interesting article on fold, FYI: http://www.cs.nott.ac.uk/~gmh/fold.pdf (PDF; ~166K). It runs along the tracks you’ve laid here, then adds many other things that can be built on fold for future posting fodder :-).

  2. Sam Page Says:
    March 12th, 2009 at 5:26 pm

    Thanks for the comment and good link Dan. I’m going to do a lot more with that fold function, especially with the map/reduce pattern which has a nicer ring to it than map/fold IMO. However I absolutely refuse to catamorphasize! ;)

    Microsoft’s LINQ calls the same function Aggregate and I have a post in the queue on why Microsoft may have chosen that naming path over the more common reduce/fold/foldl, etc.

Leave a Reply