MANY TO ONE - THE SUBTLE ART OF AGGREGATION | CSIS 110 - Introduction to Computing Sciences

MANY TO ONE - THE SUBTLE ART OF

AGGREGATION

We’ve looked at loops for converting one thing into another, X items in →

X new items out. That sort’ve thing. There’s another use case for loops that

I’d like to cover - reducing many items into a single value.

This could be making a total count, calculating Averages, Means or other

statistical data, or other more complex aggregations.

In Procedural code, we’d have a loop, a state tracking value and inside the

loop we’d update the state constantly, based on each item from our array.

Here’s a very simple example of what I’m talking about:

var total = 0;

foreach(var x in listOfIntegers)

{

total += x;

}

There’s actually an in-built Linq method for doing this:

var total = listOfIntegers.Sum();

There really shouldn’t ever be a need to do this sort of operation “long-hand”.

Even if we’re creating the sum of a particular property from an array of

Objects, Linq still has us covered:

var films = GetAllFilmsForDirector("Alfred Hitchcock");

var totalRevenue = films.Sum(x => x.BoxOfficeRevenue);

There’s another function for calculating Means in the same manner called

Average. There’s nothing for calculating Median, so far as I’m aware.

I could calculate the Median with a quick bit of functional style code,

however. It would look like this:

var numbers = new [] {

83,

27,

11,

};

bool IsEvenNumber(int number) => number % 2 == 0;

var sortedList = numbers.OrderBy(x => x).ToArray();

var median = IsEvenNumber(sortedList.Count())

sortedList.Skip((sortedList.Count()/2)-1).Take(2).Average()

sortedList.Skip((sortedList.Count()) / 2).First();

// median = 55.

There are more complex aggregations that are required sometimes. What if

we wanted - for example - a sum of two different values from an Enumerable

of complex objects?

Procedural code might look like this:

var films = GetAllFilmsForDirector("Christopher Nolan");

var totalBudget = 0.0M;

var totalRevenue = 0.0M;

foreach (var f in films)

{

totalBudget += f.Budget;

totalRevenue += f.BoxOfficeRevenue;

}

We could use two separate Sum function calls, but then we’d be iterating

twice through the Enumerable, hardly an efficient way to get our information.

Instead, we can use another strangely little-known feature of Linq - the

aggregate function. This consists of the following components:

Seed - a starting value for the final value.

An Aggregator function, this has two parameters - the current item from

the Enumerable we’re aggregating down, and the current running total.

The seed doesn’t have to be a primitive type, like an integer or whatever, it

can just as easily be a complex object. In order to re-write the code sample,

above, in a Functional style, however, we just need a simple Tuple.

var films = GetAllFilmsForDirector("Christopher Nolan");

var (totalBudget, totalRevenue) = films.Aggregate(

(0.0M, 0.0M),

(runningTotals, x) => (

runningTotals.Item1 +

x.Budget,

x.BoxOfficeRevenue

);

runningTotals.Item2 +

)

In the right place, Aggregate is an incredibly powerful feature of C#, and one

worth taking the time to explore and understand properly.

It’s also an example of another concept important to Functional Programming

- recursion.

Customised Iteration Behavior

Recursion sits at the back of a lot of Functional versions of Iteration. For the

benefit of anyone that doesn’t know, it’s a function that calls itself repeatedly

until some condition or other is met.

It’s a very powerful technique, but has some limitations to bear in mind in

C#. The most important two being:

If developed improperly, it can lead to infinite loops, which will literally

run until the user terminates the application, or all available space on the

stack is consumed. As Treguard, the legendary Dungeon Master of the

popular British Fantasy RPG gameshow Knightmare would put it:

“Oooh, Nasty”5.

In C# they tend to be consume a lot of memory compared to other forms

of iteration. There are ways around this, but that’s a topic for another

chapter.

I have a lot more to say about recursion, and we’ll get to that shortly, but this

for the purposes of this chapter, I’ll give the simplest example I can think of.

Let’s say that you want to iterate through an Enumerable but you don’t know

how long for. Let’s say you have a list of delta values for an integer (i.e. the

amount to add or subtract each time) and you want to find out how many

steps it is until you get from the starting value (whatever that might be) to 0.

You could quite easily get the final value with an Aggregate call, but we

don’t want the final value. We’re interested in all of the intermediate values,

and we want to stop prematurely through the iteration. This is a simple

arithmetic operation, but if complex objects were involved in a real-world

scenario, there might be a significant performance saving from the ability to

terminate the process early.

In Procedural code, you’d probably write something like this:

var deltas = GetDeltas().ToArray();

var startingValue = 10;

var currentValue = startingValue;

var i = -1;

foreach(var d in deltas)

{

if(currentValue == 0)

{

break;

} i+

currentValue = startingValue + d;

}

return i;

In this example I’m returning -1 to say that the starting value is already

the one we’re looking for, otherwise I’m returning the zero-based index of

the array that resulted in 0 being reached.

This is how I’d do it recursively:

var deltas = GetDeltas().ToArray();

int GetFirstPositionWithValueZero(int currentValue, int i

= -1) =>

currentValue == 0

? i

: GetFirstPositionWithValueZero(currentValue +

deltas[i], i + 1);

return GetFirstPositionWithValueZero(10);

This is Functional now, but it’s not really ideal. For a start, I’ve nested a

function in a function. Delightfully recursive, but it’s not very elegant.

The other major problem is that this won’t scale up well if the list of deltas is

large. I’ll show you what I mean.

Let’s imagine there are only 3 values for the Deltas: 2, -12 & 9. In this case

we’d expect our answer to come back as 1, because the second position (i.e.

index=1) of the array resulted in a zero (10+2-12). We would also expect that

the 9 will never be evaluated. That’s the efficiency saving we’re looking for

from our code here.

What was actually happening with the recursive code, though.

First, it called GetFirstPositionWithValueZero with a current value of 10 (i.e.

the starting value) and i was allowed to be the default of -1.

The body of the function is a ternary if statement. If zero has been reached,

return i, otherwise call the function again but with updated values for current

and i.

This is what’ll happen with the first delta (i.e. i=0, i.e. 2), so

GetFirstPositionWithValueZero is called again with the current value now

updated to 12 and i as 0.

The new value is not 0, so the second call to GetFirstPositionWithValueZero

will call itself again, this time with the current value updated with delta[1]

and i incremented to 1. delta[1] is -12, which would mean the third call

results in a 0, which means that i can simply be returned.

Here’s the problem though…

The third call got an answer, but the first two calls are still open in memory

and stored on the stack. The third call returns 1, which is passed up a level to

the second call to GetFirstPositionWithValueZero, which now also returns 1,

and so on… Until finally the original first call to

GetFirstPositionWithValueZero returns the 1.

If you want to see that a little graphically, imagine it looking something like

this:

GetFirstPositionWithValueZero(10, -1)

GetFirstPositionWithValueZero(12, 0)

GetFirstPositionWithValueZero(0, 1)

return 1;

That’s fine with 3 items in our array, but what if there are hundreds!

Recursion, as I’ve said, is a powerful tool, but it comes with a cost in C#.

Purer Functional languages (including F#) have a feature called Tail Call

Optimised Recursion which allows the use of recursion without this memory

usage problem.

Tail Recursion is an important concept, and one I’m going to return to later in

a whole chapter dedicated to it, so I’m not going to dwell on it in any further

detail here.

As it stands, out-of-the-box C# doesn’t permit Tail Recursion, even though

it’s available in the .NET Common Language Runtime (CLR). There are a

few tricks we can try to make it available to us, but they’re a little too

complex for this chapter, so I’ll talk about them at a later juncture.

For now, consider recursion as it’s described here, and keep in mind that you

might want to be careful where and when you use it.

Immutability

There’s more to Functional Programming in C# than just Linq. Another

important feature I’d like to discuss is Immutability (i.e. a variable may not

change value once declared). To what extent is it possible in C#?

Firstly, there are some newer developments with regards to Immutability in

C# 8 and upwards. See the next chapter for that. For this chapter, I’m

restricting myself to what is true of just about any version of .NET.

To begin, let’s consider this little C# snippet:

public class ClassA

{

public string PropA { get; set; }

public int PropB { get; set; }

public DateTime PropC { get; set; }

public IEnumerable<double> PropD { get; set; }

public IList<string> PropE { get; set; }

}

Is this immutable? It very much is not. Any of those properties can be

replaced with new values via the setter. The IList also provides a set of

functions that allows its underlying array to be added to or removed from.

We could make the setters private, meaning we’d have to instantiate the class

via a detailed contructor:

public class ClassA

{

public string PropA { get; private set; }

public int PropB { get; private set; }

public DateTime PropC { get; private set; }

public IEnumerable<double> PropD { get; private set; }

public IList<string> PropE { get; private set; }

public ClassA(string propA, int propB, DateTime propC,

IEnumerable<double> propD, IList<string> propE)

{

this.PropA = propA;

this.PropB = propB;

this.PropC = propC;

this.PropD = propD;

this.PropE = propE;

}

Is it immutable now? No, honestly it’s not. The properties can be replaced

inside the class, but the developer can ensure that no such code is ever

added. In that case, the integer property PropB and the IEnumerable PropD

are fine, but everything else is still mutable. It’s true that we can’t actually

outright replace any of them, but the List can still have its elements alterered,

the string is effectively a char[], so anything can be done to it.

If we didn’t actually need to hold a mutable copy of PropE, we could easily

replace it with an IEnumerable or IReadOnlyList, but that still leaves the

issue of the string and DateTime fields.

There’s also the possibility of introducing something like this:

public class ClassA

{

public string PropA { get; private set; }

public int PropB { get; private set; }

public DateTime PropC { get; private set; }

public IEnumerable<double> PropD { get; private set; }

public IList<string> PropE { get; private set; }

public SubClassB PropF { get; private set; }

public ClassA(string propA, int propB, DateTime propC,

IEnumerable<double> propD, IList<string> propE, SubClassB

propF)

{

this.PropA = propA;

this.PropB = propB;

this.PropC = propC;

this.PropD = propD;

this.PropE = propE;

this.PropF = propF

}

All properties of PropF are also potentially going to be mutable - unless this

same structure with private setters is followed there too.

What about classes from outside your codebase? What about Microsoft

classes, or those from a 3rd party Nuget package? There’s no way to enforce

immutability.

Unfortunately there simply isn’t any way to enforce universal immutability,

not even in the most recent versions of C#. I would assume that for

backwards compatibility reasons, there is never going to be.

My solution is far from perfect. I would simply pretend that Immutability

exists in the project, and never change any object. There’s nothing in older

versions of C# that provides any level of enforcement whatsoever, so you’d

simply have to make a decision for yourself, or within your team, to act as if

it does.

Putting it all Together - a Complete Functional

Flow

I’ve talked a lot about some simple techniques you can use to make your

code more functional right away. Now, I’d like to show a complete, if

minute, application written to demonstrate an end-to-end functional process.

I’m going to write a very simple CSV parser. In my example, I want to read

in the complete text of a CSV file containing data about the first few series

of Doctor Who6. I want to read the data, parse it into a Plain Old C# Object

(POCO, i.e. a class containing only data and no logic) and then aggregate it

into a report which counts the number of episodes, and the number of

episodes known to be missing for each season. 7. I’m simplifying CSV

parsing for the purposes of this example. I’m not worrying about quotes

around string fields, commas in field values or any values requiring

additional parsing. There are 3rd party libraries for all of that! I’m just

proving a point.

This complete process represents a nice, typical functional flow. Take a

single item, break it up into a list, apply list operations, then aggregate back

down into a single value again.

This is the structure of my CSV file:

[0] - Season Number. Integer value between 1 and 39. I’m running the

risk of dating this book now, but there are 39 seasons to date.

[1] - Story Name - a string field I don’t care about

[2] - Writer - ditto

[3] - Director - ditto

[4] - Number of Episodes - in Doctor Who, all stories comprise between

1 and 14 episodes. Until 1989, all stories were multi-part serials.

[5] - Number of Missing Episodes - the number of episodes of this serial

not known to exist. Any non-zero number is too many.

I want to end up with a report that has just these fields:

Season Number

Total Episodes

Total Missing Episodes

Percentage Missing

Let’s crack on with some code….

var text = File.ReadAllText(filePath);

// Split the string containing the whole contents of the

// file into an array where each line of the original file

// (i.e. each record) is an array element

var splitLines = text.Split(Environment.NewLine);

// Split each line into an array of fields, splitting the

// source array by the ',' character. Convert to Array

// for each access.

var splitLinesAndFields = splitLines.Selct(x =>

x.Split(",").ToArray());

// Convert each string array of fields into a data class.

// parse any non-string fields into the correct type.

// Not strictly necessary, based on the final aggregation

// that follows, but I believe in leaving behind easily

// extendible code

var parsedData = splitLinesAndFields.Select(x => new Story

{

SeasonNumber = int.Parse(x[0]),

StoryName = x[1],

Writer = x[2],

Director = x[3],

NumberOfEpisodes = int.Parse(x[4]),

NumberOfMissingEpisodes = int.Parse(x[5])

});

// group by SeasonNumber, this gives us an array of Story

// objects for each season of the TV series

var groupedBySeason = parsedData.GroupBy(x =>

SeasonNumber);

// Use a 3 field Tuple as the aggregate state:

// S (int) = the season number. Not required for

// the aggregation, but we need a way

// to pin each set of aggregated totals

// to a season

// NoEps (int) = the total number of episodes in all

// serials in the season

// NoMisEps (int) = The total number of missing episodes

// from the season

var aggregatedReportLines = groupedBySeason.Select(x =>

x.Aggregate((S: x.Key, NoEps: 0, NoMisEps: 0),

(acc, val) => (acc.S,

acc.NoEps + val.NumberOfEpisodes,

acc.NoMisEps +

val.NumberOfMissingEpisodes)

)

);

// convert the Tuple-based results set to a proper

// object and add in the calculated field PercentageMissing

// not strictly necessary, but makes for more readable

// and extendible code

var report = aggregatedReportLines.Select(x => new

ReportLine

{

SeasonNumber = x.S,

NumberOfEpisodes = x.NoEps,

NumberOfMIssingEpisodes = x.NoMisEps,

PercentageMissing = (x.NoMisEps/x.NoEps)*100

});

// format the report lines to a list of strings

var reportTextLines = report.Select(x => $"

{x.SeasonNumber}, {x.NumberOfEpisodes}," +

"{x.NumberofMissingEpisodes},{x.PercentageMissing}");

// join the lines into a large single string with New Line

// characters between each line

var reportBody = string.Join(Environment.NewLine,

reportTextLines);

var reportHeader = "Season,No Episodes,No

MissingEps,Percentage Missing";

// the final report consists of the header, a new line,

then the reportbody

var finalReport = $"{reportHeader}{Environment.NewLine}

{reportTextLines}";

In case you’re curious, the results would look something like this (I’ve added

a few Tabs in to make it readable):

Season No Episodes No Missing Eps Percentage Missing,

1 42 9 21.4,

2 39 2 5.1,

3 45 28 62.2,

4 43 33 76.7,

5 40 18 45,

6 44 8 18.2,

7 25 0 0,

8 25 0 0,

...

26 0 0,

Note, I could have made the code sample more concise and written just

about all of this together in one long, continuous fluent expression like this:

var reportTextLines = File.ReadAllText(filePath)

.Split(Environment.NewLine)

.Select(x => x.Split(",").ToArray())

.GroupBy(x => x[0])

.Select(x

x.Aggregate((S: x.Key, NoEps: 0, NoMisEps: 0),

(acc, val) => (acc.S,

acc.NoEps + int.Parse(va[4]),

acc.NoMisEps + int.Parse(val[5]))

)

.Select(x => $"{x.S}, {x.NoEps},{x.NoMisEps},

{(x.NoMisEps/x.NoEps)*100}");

var reportBody = string.Join(Environment.NewLine,

reportTextLines);

var reportHeader = "Season,No Episodes,No

MissingEps,Percentage Missing";

var finalReport = $"{reportHeader}{Environment.NewLine}

{reportHeader}";

There’s nothing wrong with that sort of approach, but I like splitting it out

into individual lines for a couple of reasons:

The variable names provide some insight into what your code is doing.

We’re sort’ve semi-enforcing a form of code commenting.

It’s possible to inspect the intermediate variables, to see what’s in them

at each step. This makes debugging easier.

There isn’t any ultimate functional difference, nothing that would be noticed

by the end user, so which style you adopt is more a matter of personal taste.

Write in whatever way it seems best to you. Do try and keep it readable, and

easy for everyone to follow, though.

Taking it Further - Develop Your Functional Skills

Here’s a challenge for you. If some or all of the techniques described to you

here were new, then go off and have fun with them for a bit.

Challenge yourself to writing code with the following rules:

Treat all variables as immutable - do not change any variable value once

set. Basically treat everything as if it were a constant.

None of the following statements are permitted - If, For, ForEach,

While. If is acceptable only in a Ternary expression - i.e. the

single- line expression in the style: someBoolean ? valueOne :

valueTwo.

Where possible write as many functions as small, concise arrow

functions.

Either do this as part of your production code, or else go out and look for a

code challenge site, something like The Advent or Project Euler. Something

you can get your teeth into.

Is this immutable? It very much is not. Any of those properties can be

replaced with new values via the setter. The IList also provides a set of

functions that allows its underlying array to be added to or removed from.

We could make the setters private, meaning we’d have to instantiate the class