Reduce - 7 higher order functions

Fourth blog post in this series is about Reduce, a pattern I heard of first with Map/Reduce, that I will be revisiting later  on. At the moment let's focus on Reduce. What is it?

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

Reduce

The function signature of Reduce is very much like Fold but without the seed value.

U Fold<T, U>(Func<U, T, U> fn, U init, IEnumerable<T> list)
T Reduce<T>(Func<T, T, T> fn, IEnumerable<T> list

No seed value and same result type as list type. Otherwise pretty much the same.

Examples

Easiest example to show is summing up a list of ints.

public int Sum(int[] numbers)
{
    return numbers.Reduce((a, b) => a + b);
}

And we could do the same with functions like Max or Min. This is not very useful. We've been able to do that before. Let's say we want to collect all outgoing links from this blog.

// Links
var links = new[]
{
    "http://litemedia.info/map-7-higher-order-functions",
    "http://litemedia.info/fold-7-higher-order-functions",
    "http://litemedia.info/partition-7-higher-order-functions",
};


// Map - noop because of yield
var map = links.Map(OutgoingUrls);

// Reduce
var outgoingLinks = map.Reduce((links1, links2) =>
{
    // Add all links2 to links1 list
    var result = new List<string>(links1);
    foreach (var link in links2)
    {
        // Filter unique
        if (!result.Contains(link))
        {
            result.Add(link);
        }
    }
return result;

});

// DONE: all outgoing links are now in variable 'outgoingLinks'

// For url, get outgoing urls
private IEnumerable<string> OutgoingUrls(string url)
{
    var result = new List<string>();
    var request = HttpWebRequest.Create(url);
// Request url content
using (var response = request.GetResponse())
using (var reader = new StreamReader(response.GetResponseStream()))
{
    // Match all href=&quot;http://...&quot; not litemedia
    var matches = Regex.Matches(reader.ReadToEnd(), @&quot;href=&quot;&quot;(?&lt;url&gt;(?:http\:)?//(?!litemedia).*?)&quot;&quot;&quot;);
    foreach (Match match in matches)
    {
        result.Add(match.Groups[&quot;url&quot;].Value);
    }
}

return result;

}

Thanks to Map uses yield, we're only traversing the list of links once.

Implementation

The implementation is straight forward. One difference between Fold and Reduce, is that Reduce requires at least one item in the list. You cannot reduce an empty list.

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

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

IEnumerator&lt;T&gt; enumerator = list.GetEnumerator();
if (!enumerator.MoveNext())
{
    throw new ArgumentException(&quot;Can&#39;t run reduce on an empty list&quot;, &quot;list&quot;);
}

var result = enumerator.Current;
while (enumerator.MoveNext())
{
    result = fn(result, enumerator.Current);
}

return result;

}

public static T Reduce<T>(this IEnumerable<T> list, Func<T, T, T> fn)
{
    return Reduce(fn, list);
}

Because I need to get the first item in the list separately, and start the reduce iteration from second item, I've chosen to use the enumerator directly, and not the foreach syntactic sugar.

Conclusion

Reduce is one of those functions that is hard to put into a context. With out Map, its really just another Sum/Max/Min aggregate function, but together with map you have a lot of possibilities. I hope this sheared some light as to when and how, reduce should be used.