Functional Practice: Euler Problem #1 in F#

Time for a little more coding practice as I'm learning F#. And for that, I'm headed back to Project Euler. Many of these problems lend themselves to functional-style solutions.

I took a look at Euler Problem #1 way back in October 2013 (wow, has it been that long already?) with a solution in Haskell. Since I've already thought about this problem, putting together a solution in F# was pretty simple.

[Update: Collected articles for the first 10 Euler Problems in F# are available here: Jeremy Explores Functional Programming.]

Euler Problem #1
Here is problem 1:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

For the solution in Haskell, we built things up step-by-step. We'll do the same thing here for F#.

Building a Solution
We'll start with the example with the numbers below 10. Once we have a matching output, we'll expand it to work with numbers below 1000.

The first step is to get a list of the natural numbers below 10:

The "[1..9]" creates a list that gives us the natural numbers below 10 -- which translates into integers from 1 to 9 inclusive.

For these examples, I'll just show the input (from an F# script file) and the output (from the F# Interactive window). I prefer using a script file for syntax highlighting and such. But this would work just the same if we typed things into F# Interactive directly.

Piping Forward
The next step is to get the numbers that are multiples of 3 or 5. For this, we'll use the "filter" function:

The "List.filter" function takes 2 parameters. The first parameter is a function used to filter the data. We just have to return a true/false value to determine whether the list item is included in the resulting list. In this case, we use a function that checks to see if "x" is evenly divisible by 3 or 5 (using the modulus operator).

This is very similar to the LINQ "Where" function in C# that takes a "Func<TSource, bool>" (a delegate) as a parameter. The anonymous function we show here is equivalent to a lambda expression in C#.

The last parameter of the "filter" function is the list. In F# (and other functional languages), it is common to have the data parameter as the last parameter. This is a bit different than C# programmers are used to; in C#, we usually put the data parameter as the first parameter (since it's most important).

One reason that we like to have the data parameter last is so that we can easily use pipelining -- where we pass the output of one function as a parameter to another function. In F#, we use the "|>" operator for this. Here's the same function re-arranged to use pipelining:

In this case, we create the list on the first line, then we pipe the output of that list creation to the "List.filter" function. This uses the list as the last parameter of the "filter" function. And this is why we like to have the data parameter as the last parameter of a function -- we can easily pipe the output of a function into the input of another function.

Side note: Another reason to have the "important" parameter last is so that we can do partial application of functions -- but that's not something that we'll be talking about today.

These two ways of calling "List.filter" are equivalent. But when we use pipelining, we give ourselves a very easy way of chaining functions together.

Summing the List
The pipelining doesn't seem too useful when we just have 1 function (well, technically, we have at least 3 functions here, but it looks like 1). But it gets much more interesting when we add more functions. The last step in our problem is to sum the results. We'll just pipe the results to the "List.sum" function:

"List.sum" take a single parameter: a list of values to be added together. When we pipe our filtered list into the "sum" function, we get our expected result of 23.

I really like how easy it is to chain functions together with pipelining. It feels very natural (especially since I'm such a big fan on LINQ in C#).

Completing the Challenge
Now that we've replicated the sample, it's time to see if this works for the full list:

This gives us all the natural numbers below 1000, filters it to values evenly divisible by either 3 or 5, and then sums the result. We've previously verified the result for Euler Problem #1, so we know that this value is correct.

A Reusable Function
As a final step, let's create a function that is reusable. For this, we'll just add a declaration and a parameter:

We called this "euler1" and it takes a parameter "belowThis". This will create a list that ends just below the value passed in. This way, we can call the function with the same values that are in the problem.

Note: We don't have to declare a type for "belowThis" because F# uses type inference pretty much everywhere. Since we're using "belowThis" as an integer (by subtracting one and using it as a value for our list creation), F# determines this is an integer, so we don't have to put that in. Cool stuff (although I sometimes have issues reading code -- I'm hoping I'll get used to it, but I also worry a bit about people who are new to the environment getting frustrated).

For example, this will use all natural numbers below 10:

And here is a call for all numbers below 1000:

We can see that our output values are still correct.

And in case you're wondering, yes, it does fit in a tweet:

Wrap Up
So that takes us through Euler Problem #1 using F#. Nothing too groundbreaking here. And lots of people have solved this problem before. For me, this was a good bit of coding practice, and it helps me get more familiar with F# (which is really my goal here).

The next Euler problem uses the Fibonacci sequence. And creating a "functional" Fibonacci sequence while keeping decent performance has been a problem for me in the past. I might put that on hold a bit while I go through some of my F# books to learn more about the language and constructs. I'm sure there will be a bit of trial and error there.

This type of exploration is how we can learn new things. And even if we're not learning anything new, it helps us get more comfortable with the tools, language, and environment.

Happy Coding!

Unit Test Factory Methods: Return an Interface or a Mock?

Had a great question today regarding what to return when using factory methods with unit tests:

Should a unit test factory method return the interface or a mock of the interface?

The best way to look at this is to look at an example. Let's say that we have a class ("DataParser") that take an "ILogger" as a constructor parameter. This class would look like this:

Now in our tests, we want to test the "ParseData" method behavior. But we need an "ILogger" to satisfy the constructor parameter. In some situations we just need the "ILogger" for construction (technically, behaving as a stub), and for other situations, we need to assert against the "ILogger" (behaving as a mock).

So if we have a factory method, should it return "ILogger" or "Mock<ILogger>"? Here's what the options would look like:

Note: this code is using Moq for mocking. This mocking framework has met most of my needs over the years.

Disclaimer
Before going any further, I want to say that my "recommendation" is just my opinion -- this is the way that I prefer to do this. Roy Osherove (who wrote the excellent The Art of Unit Testing) says that we need to make a clear distinction in our code between a stub and a mock. (Also, he's not a fan of Moq as a mocking framework because it does not make that distinction.)

What I've found is that in the tests that I've written, that distinction is unneeded. So, I've chosen a direction that (hopefully) minimizes confusion and enhances readability of the code.

Picking One
One option would be to keep both of these methods and use "GetLogger" when we need a stub and "GetMockLogger" when we need a mock. I would rather minimize the number of factory methods that I have unless they are really needed, so I'm going to pick one.

Note: it's perfectly valid to keep both of these; however, I might recommend having the "GetLogger" method call the "GetMockLogger" method so that we are only creating mocks in one place.

So, let's look at both options, and then I'll give you my preference.

Option 1: Returning the Mock<ILogger>
Let's start by looking at a factory method that returns the mock object:

A test that needs a stub would look like this:

Notice that when we create the "DataParser" object on the second line, we need to use the "Object" property of our mock. This gets the actual "ILogger" object out of our mock so that we can use it as a parameter for our constructor.

I don't really like this. It requires too much knowledge of the mocking framework inside the test. If the test does not care about the mock object, I don't want it to be "polluted" with that knowledge.

Option 2: Returning ILogger
So, what if we have our factory return "ILogger"?

We still create the mock object (because we may still need the in-memory behavior of a mock), but we return the "ILogger" itself from the factory.

Then our test would look like this:

I like this much better. This test does not care about whether we have a mock or a fake (meaning, a real class that implements the interfaces and is used for testing purposes). And I think it lends to the readability: we don't have extra stuff that stops us from reading the code.

But What if We Need a Mock?
There are times that we really need a mock object. For example, in this case, we want to verify that the "ILogger.Log()" method is getting called the right number of times by our "ParseData" method. So what does that code look like?

Returning Mock<ILogger>
If we use the method that returns the mock, then our test could look like this:

In this case, we actually need the mock, because we are calling the "Verify" method on it. In Moq, the "Verify" method lets us check to see if a method was called with certain parameters or called a certain number of times (among other things). In this case, we are checking that the "Log" method is called only one time (that's the "Times.Once()" parameter).

We don't care about the parameters, which is why we have the "It.IsAny<string>()" methods in there. I won't get into the details of those right now. We'll save those for a longer article about mocking.

This code is pretty clean. So, let's look at the other option.

Returning ILogger
We can still use the method that returns "ILogger" here. That's because of one of the features of Moq. Here's what that same test looks like:

Notice that we get the "ILogger" from the factory and then pass it to the "DataParser" constructor. But since we want to use the "Verify" method, and that requires a "Mock<ILogger>" to work, we need to do a little extra work.

The last line of the "Arrange" section uses the "Mock.Get()" method. This is a static method in Moq that allows us to take an interface that has been mocked and get the original mock object back. We can see in this case, we end up with a "Mock<ILogger>", which is just what we need.

The rest of the test, including the call to "Verify" is the same as above.

The Danger
This code seems a little bit dangerous. What if "ILogger" is a fake object (instead of a mock)? Well, this code will throw an exception. "Mock.Get()" will only work with objects that were created with Moq.

This means that if we change the "GetLogger" method to return a fake instead of a mock, all of the tests that need a mock will blow up.

Am I worried about this? Not really. If I need a mock object that I'm running assertions against, then I'm probably extra aware of what's going on in the factory methods.

My Preference
So, my preference is to have a single factory method that returns an "ILogger":

Then my tests look like this:

This gives me the most readable code for the first test (where I just need a stub and don't care about asserting against the "ILogger"). This also makes writing these tests really easy. I don't have to worry about the internals of my mocking framework.

The second test is a bit more dangerous, but because I'm asserting against a mock object, I'm going to be paying closer attention to this anyway. And if I'm writing new tests that assert against the mock object, I'm going to have to know something about the mocking framework. So it makes sense to need that additional knowledge here instead of in the "simple" test.

As I noted above, this is just my preference based on my experience. I've written several different kinds of unit tests (and lots of them), and this "feels" the best to me.

Wrap Up
Your mileage may vary. It is perfectly valid to have *both* factory methods, but I prefer to keep factory methods to a minimum. And as I noted before, the distinction between stubs and mocks is more of a technical one in my world -- having the clear separation between them has not been important.

When you're new to unit testing, you'll come across lots of opinion and even more "best practices". 

Try out the ones that look interesting. If they fit into your environment, then keep them. If they don't fit, then feel free to discard them. This is part of the process of learning what works best for you. And that may be different than what works best for me.

Happy Coding!

Digit Recognizer - Grouping Items and Visualizing Errors

So, I've been making some UI changes to my Digit Recognizer project to try to make it easier to visualize the data. Last time, we used the F# code so that we could play with the code a bit. You can read about it here: Exploring the Digit Recognizer with F#.

But we were displaying the source bitmap alongside the prediction from our machine learning algorithm:

This is pretty cool, but it's a bit hard to read, and it doesn't size well. So today, we'll group the bitmap and textbox together in a button. That way, we can click on the button to show which items are incorrect:

This is one step closer to easily analyzing the data visually (which is where I'm headed with this).

The actual display output will change visually depending on what resolution you're using (I'm going to be looking at this in the future). I'm running this application at 1280x800 and showing a little under 200 digits here.

The code for this is available in GitHub: jeremybytes/digit-display -- specifically, this code references the UIAwesome branch.

Grouping the Items
Previously, I created a bitmap (to represent the source data) and a textbox (to represent the prediction) and added them to the wrap panel individually. This lead to some issues when resizing the screen (the items would not always be grouped together).

Here's the code for that (where I started):

So, I added a button that would contain both the bitmap and the textbox. Here are the button-related bits:

This creates a button and adds the items that we created earlier. Then we add the button to the wrap panel.

This keeps the items "paired" so that we don't have to worry about resizing the application and throwing off our display.

Flagging Errors
The other thing I wanted to do was add the ability to flag the incorrect items. This obviously takes human intervention. Previously, I was scanning through the screen and counting the incorrect ones. Now that I had a button, I could add in some functionality to help with that.

In the code snippet above, you'll notice that there is a "ToggleCorrectness" method hooked up to the button click event handler. Here's that code:

When we click on one of the buttons, it will toggle the background color (to light red) and also increment our error count which displays at the top of the screen. We can also toggle back to "correct" if we hit a button by accident.

There were a couple other minor changes that I had to make as well -- such as making the bitmap transparent. You can check the code if you're really curious about that.

The Result
The result of this is that we can visually see the bitmaps along with the predictions and then flag the items that are incorrect:

Here we can see that there are 6 errors in our data (there might be a couple more if you look closely -- if I couldn't tell what the digit should be, then I didn't fault the computer for getting it wrong).

This makes it easier to see the items that are incorrect. It's still a bit tedious, though. Since it needs a human (me) to flag the items, I need to scan through all of the numbers. And quite honestly, my brain gets bored easily, so I'm sure that there are some items that I'm missing.

In case you're curious, this code is using the Manhattan Distance algorithm, and it is using the full training set (over 40,000 items).

Reminder: The code for this is available in GitHub: jeremybytes/digit-display -- specifically, this code references the UIAwesome branch.

Next Steps
This is really an interim step. As I mentioned previously, I'm really interested in seeing how different algorithms behave differently, and I'm also curious about how altering the size of the training set affects both the accuracy and the speed.

One other thing I'd like to do is add an "offset" so that I can start looking at data at an arbitrary (but repeatable) location. This will make sure that I'm not just optimizing for the data that is in the "first" part of the validation set.

So my next steps are a few more UI improvements to let me pick these different variables -- right now, they are in the code, and I have to rebuild/rerun to try different scenarios. I'd really like to be able to see the different outputs without having to alter code and rebuild the application.

I've been enjoying this exploration, and I'll keep doing it even though it doesn't have specific application. Many times, when we dig into things that don't have an immediate value, we find things that are really helpful in the future.

Happy Coding!

FizzBuzz in F# in 99 Characters

I haven't done a whole lot with functional programming for a while. But at NDC Oslo, I got to hang out with the FP folks, and it inspired me to start exploring (and playing) again. I picked up my Digit Recognizer project and got the F# code integrated. (And I've done more with that project since the last article; I'll be writing that up soon.)

So, I've been playing and exploring a bit. And I put together a very compact implementation of FizzBuzz. We'll see why I was headed for "compact" a bit later.

FizzBuzz
FizzBuzz is a pretty simple programming problem. There are only a few rules:

1. Print the numbers from 1 to 100.
2. If the number is divisible by 3, print the word "Fizz".
3. If the number is divisible by 5, print the word "Buzz".
4. If the number is divisible by both 3 and 5, print "FizzBuzz".

Since this is a pretty simple problem, I've found it as a good way to get started with TDD (in C#). You can check out a video of that here: New Video: TDD Basics with C#.

Here's one way of implementing a method that fulfills the rules:

Why FizzBuzz and F#?
When I've been working with F#, I've been really interested in doing things the "functional way". I figure the more that I can do that, the more I can wrap my brain around the functional concepts that are just beyond my grasp at the moment.

But when I tried to do FizzBuzz in F#, I ran into a roadblock. The implementations that came up with were all very imperative in nature. The C# code above is pretty straightforward: we start with an empty string, append "Fizz" and/or "Buzz" if appropriate, and if we don't append either one, then we print out the original number.

But this deals with a mutable object (the "output" string).

I even talked to some of the functional folks at an even back in November, and one of the suggested solutions used if/elif/else:

This works -- it generates a list with the proper data -- but it felt too much like the code I'd written in C#. I wanted something a bit "more functional" (yes, I know that's not strictly necessary, but I'm still learning and trying to get the concepts and language features).

Help from Elixir
The reason that I'm back on this today is that I just watched the recording of Bryan Hunter's (@bryan_hunter) talk at NDC Oslo: What every Node.js developer needs to know about Elixir. He showed an Elixir implementation of FizzBuzz:

And this gave me a great idea of how I could use pattern matching in F# to do the same thing.

So, I didn't write anything original, but I translated it from Elixir to F# (which is actually a pretty good accomplishment considering my current experience with the language).

Pattern Matching in F#
So, here's the code in F#:

Let's walk through this.

First, the "[1..100]" creates a list consisting of the integers from 1 to 100.

Then we use the pipe-forward operator "|>" to pass that to the "List.map" function. The "map" function will apply a function to each of the elements in our list.

Then we have the function that uses pattern matching to get what we want. The "fun x ->" tells us that we have a function with a parameter called "x". In this case, "x" is the integer that represents the value of a list element.

Then we have the "match" expression. The first part "(x % 3, x % 5)" will create a tuple with 2 values. This uses the modulo operator "%" to get the remainder when we divide by 3 for the first value, and divide by 5 for the second value.

So if "x" is 9, our tuple would be "(0, 4)" since 9 divided by 3 has a remainder of 0, and 9 divided by 5 has a remainder of 4.

After the "with", we have the patterns that we're trying to match.

The first pattern "(0, 0)" tells us that the number is evenly divisible by both 3 and 5 (since the remainders of both after division is 0). So we want to output "FizzBuzz" here.

The next pattern "(0, _)" tells us that the number is evenly divisible by 3 (the first value). For the second value, we have an underscore. This means that we don't care what this number is. Since the number is divisible by 3, we output "Fizz". (Our example above, "(0,4)" would match this pattern.)

The next pattern "(_, 0)" tells us that the number is evenly divisible by 5 (the second value). We don't care what the first value is in this case. Since it's divisible by 5, we output "Buzz".

The last pattern "(_, _)" says that we don't care what the values are. This is a "catch all", and will simply convert the integer to a string.

Since this pattern matching is greedy (meaning the first pattern to match wins), we know that we'll get the output that we want. If we reordered things, then we would get unexpected results.

Here's the output when we run this in the REPL:

Success!

And I liked this implementation much better than using the if/elif/else. The pattern matching seemed like a "better" solution since pattern matching is such a key component of F#. This gave me a chance to use it and explore a bit.

Paring Down to 109 Characters
Since this implementation was fairly compact, I decided to see how small I could make it. So, I took out all of the white space that I could:

This isn't very readable, but it's only 109 characters. This got me within my goal.

What's the goal? Well Mathias Brandewinder (@brandewinder, who I've mentioned many times) wrote a Twitter bot that parses F# and sends back results. He showed me this at the Microsoft MVP Summit last November, and I thought it was pretty cool.

Basically, you just send a tweet to @fsibot, and it will tweet back with the result. (As an aside, Mathias showed me all of the parsing and input sanitation that he has to do to make sure that no one does anything malicious with it. It's quite a challenge.)

Since 109 characters will fit in a tweet, I sent it in:

Success!

The Purpose
Is this world changing? Absolutely not. But it is interesting. It is a bit of a challenge. And it's also a bit of fun. I had a good time exploring, and I learned a bit more about pattern matching.

BTW, I found that I actually have some extra characters. The parentheses around the patterns can be removed:

This removes several more characters (also notice that the last pattern simply has a single underscore -- this still acts as the "catch all").

This brings the total down to 99 characters:

Cool stuff.

I've found a bit of joy in the functional programming that I've been doing recently. I'm definitely going to continue. My travel schedule lightens up a bit in July. That will be a good time for deep dive.

Keep exploring, and find those things that pique your interest and make coding fun.

Happy Coding!

"Becoming a Social Developer" at NDC Oslo

I had a really amazing time at NDC Oslo last week. And I also did a brand new session using a new technique. I'll have to say that I'm happy with the way that things came out, even though I had some apprehensions about the talk.

So let's do a quick review of "Becoming a Social Developer" from NDC Oslo.

[Update: You can watch a recording of the presentation here: Becoming a Social Developer - Jeremy Clark]

A New Technique
I tried something completely new to me: hand-drawn slides. This is something that I first picked up from talking to David Neal (@reverentgeek) at That Conference last August. He recommended Dan Roam's book Show and Tell (Jeremy's review), and I found it to be a very interesting read.

The first thing that stuck out is that Roam describes several "storylines" for presentations. When looking through these, I saw that "The Drama" would be a good storyline for this particular talk. In fact, I got out my portable white board and drew up the outline:

Since this talk is basically me telling a bunch of stories (and no code at all!), I figured that I needed something interesting going on the screen, so I took another bit of advice from David and Roam and decided to hand-draw my slides.

I spent *a lot* of time on this -- trying to figure out what to write, what to draw, and how much stuff I needed to fill in a full hour. I ended up with 125 slides (YIKES!).

Here are a few samples:

Force Field

May I join you?

Fear!

What a dork!

As you can see, my drawing skills aren't all that great. I think I'll go back and redraw a few of the slides if I give this talk again, but overall, I'm happy with the result.

If you're really curious, you can download the presentation slides (warning, 125 page PDF file): Slides for Becoming a Social Developer at NDC Oslo.

The Apprehension
I was a bit apprehensive about giving this talk as a conference session. I have written articles on it (Becoming a Social Developer & On Being a Social Developer), talked about it on .NET Rocks (Episode 1187), had plenty of hallway conversations, and even had a chance to share it before the keynote at a couple of events (including Live! 360 and Code PaLOUsa).

And back when I originally drew my outline (in October 2015), I was planning it as a full conference session. But the more I thought about it, the less interested I thought people would be. It's a soft topic, and these are hard to do at a technical conference. And to make things more difficult, this would need to be toward the front of the conference to be most useful. I figured that few people would want to start off a conference by attending a soft topic -- that's when you want to dive headlong into the tech; soft topics are good when your head is full and you need a break.

However, I was very surprised with the turnout at NDC Oslo. The room was decently filled (I'm really bad at estimating numbers, so I won't try). I had the first time slot after the opening keynote. The good news is since Troy Hunt gave the keynote, I knew that everyone would be awake.

The Talk
Several people live-tweeted the talk. A big thanks to those folks. Plus, I got to spend some time with them during the rest of the week (another way to meet new friends).

*wipes sweat from forehead* pic.twitter.com/74Xa9ouaWD

— David Neal (@reverentgeek) June 8, 2016

Thx to @jeremybytes "behavior can be changed! And it gets essier with every attempt!" #ndcoslo pic.twitter.com/eriVmKTdPT

— getNext IT (@getNextIT) June 8, 2016

"If you've got a laptop open, that's basically an invisibility cloak." -@jeremybytes on making ourselves accessible pic.twitter.com/rkquZeguTf

— Erika Carlson (@eacarlson) June 8, 2016

Start the conversation #ndcoslo @jeremybytes pic.twitter.com/3eYELhjB0H

— Pavneet Singh Saund (@pavsaund) June 8, 2016

Nice presentation even for extraverts to encourage them to open the circle ☺ #ndcoslo @jeremybytes @NDC_Conferences pic.twitter.com/mN1iZct0GL

— Daniel Gaszewski (@DanielGaszewski) June 9, 2016

To see all the activity from the talk reinforced that I'm not alone in having these feelings and fears when attending developer events.

So, thank you to my friends David Neal (@reverentgeek), Sabine Bendixen (@SabineBendixen & @getNextIT), Erika Carlson (@eacarlson), Pavneet Singh Saund (@pavsaund), and Daniel Gaszewski (@DanielGaszewski).

The Results
I was very happy with the results. Several people came up to me to talk after the session, and a couple of the speakers even mentioned me in their talks later in the week.

I also know of several people who actively used the tips that I presented. It was really great to see this tweet come through on the last day of the conference:

@jeremybytes in 3rd day of #ndcoslo I need to admit your tips and mentoring on that stuff REALLY WORKS!

— Daniel Gaszewski (@DanielGaszewski) June 10, 2016

Fortunately I had a chance to talk to Daniel in person about his experiences, and I'm hoping to share more of them in the future.

In addition, the topic was featured in the NDC Oslo opening day re-cap video:



Review
Based on the response and the successes that people had meeting new people, I'm really encouraged to keep sharing this message. And although I had a bit of apprehension about the session itself, things went very well (much better than I expected): there was a good turnout, I managed to get my stories in the right order, and the timing worked out pretty close to perfectly.

I'm really looking forward to the video of the presentation. Once it's posted, I'll be sure to pass it along.

[Update: You can watch a recording of the presentation here: Becoming a Social Developer - Jeremy Clark]

And today, something interesting happened...
In my presentation, I mentioned how I have become a person who makes connections between other developers (something that is definitely not part of my nature). In particular, I talked about how I was able to connect Maggie Pint (who has an interest in date/time challenges) with Matt Johnson (who I refer to as "Mr. DateTime").

Today, Maggie announced that she has a new challenge ahead of her:

I am officially headed to Redmond to work as an engineer in the Open Source Programs office at Microsoft. Excited to try something new!

— Maggie Pint (@maggiepint) June 15, 2016

And she blames me for helping get it started:

Big thanks to @mj1856 for all the support. @jeremybytes be careful with that introducing thing you do at conferences https://t.co/9Jn1imh6Xu

— Maggie Pint (@maggiepint) June 15, 2016

@jeremybytes Thanks very much for introducing me to @maggiepint. She has been invaluable asset to @momentjs and is going to rock at MS!

— Matt Johnson (@mj1856) June 16, 2016

I'm really glad I could get the ball rolling in the right direction. I made the connection, but it was Maggie who did all the work. She continued the conversation with Matt, she got involved with open source projects and the surrounding community, and ultimately that work led to her getting a new opportunity.

You Never Know...

You never know which of these relationships turn into something bigger, and you never know which relationships may change your life.

If you want to continue the conversation and join the movement, head over to Becoming a Social Developer, sign up for the newsletter, and send in your stories.

Happy Coding!

Oh, and I lied, there was some code in the presentation...

Exploring the Digit Recognizer with F#

I haven't worked on my functional programming for a while. At NDC Oslo, I spent a bit of time with the functional folks, and I was reminded of what a great community is represented by those leaders. They are people who are curious about the world around them, who like to explore and try new things, and who love to share what they know with other people.

It inspired me to go back to a bit of my coding practice and do some more experimentation. I took some code that was written in C# and replaced it with F# code and then worked on some optimization. This let me explore the dataset and find some interesting results regarding accuracy based on the size of the training set and the algorithm used.

Previous Code
So, back in June 2014, I first did some exploration into a machine learning problem: recognizing hand-written digits. I wasn't up to the challenge at that point, so I just figured out a way to display the data (represented by a string of values from 0 to 255 that represent the "lightness" of a pixel). You can read about that here: Coding Practice: Displaying Bitmaps from Pixel Data.

This gave me an output like this:

The Original Digit Display

Then a few months ago (in April), I added the machine learning code that I got from Mathias Brandewinder's book Machine Learning Projects for .NET Developers.

This let me see the original bitmaps next to the prediction from the machine learning algorithm. You can read more about the process here: More Fun with Machine Learning: Recognizing Digits.

Here's the result of that:

Digit Display with Predictions (C# Code)

This is great because I get to see a side-by-side comparison of the hand-written digit and what the computer thinks it is.

But this was all C# code (taken from Mathias' book). I wanted to use the F# code here.

Integrating the F# Code
So, I had the F# code (also from Mathias' book). But there were a couple of challenges since I haven't worked extensively with F# projects.

If you'd like to take a look at the code, go to the GitHub project: jeremybytes/digit-display and take a look at the FSharpRecognizer branch. This project has taken on a life of its own, so I'll probably be re-organizing things in a bit.

The first is that the code that I had was in a script file. This is great for running interactively in the REPL. But it wouldn't work for what I needed. I needed a .NET library that I could call from my WPF application.

The other thing is that the original code ran the machine learning algorithm against an entire set of data so that it could get an accuracy percentage at the end. I needed to run the algorithm against one image at a time so that I could associate the prediction with the image.

The first thing I did was create an F# library in my solution. I copied the script file (.fsx) that I had and created a new F# file (.fs) from it.

I had to make some changes to the top of the file to get things to work. This was new to me since I hadn't done this before, but I managed to get a working solution.

Here's the top of the file:

Top of the F# Library File

The first thing I had to do was create a module. The way I figured this out was from Visual Studio telling me that I needed to have a module:

So, I declared a module.

Next, I needed to update where I got my data. The original script was using a hard-coded path, but I wanted to get that value from configuration (since that's what I was doing with the C# code). With a little hunting, I found "FSharp.Configuration" that let me do just that.

This gives us an AppSettings type provider (type providers are *extremely* useful in F#). The code is pretty simple:

Getting the File from Configuration

Now I had the data pointed at the right files.

The last thing that I really needed to do was create a function that would work with an individual bitmap image (or technically an integer array that represented that bitmap image). This was some new code that I needed to write.

I took a couple different shots at this, first using the "Observation" object from the original script. That contains both the integer array, plus a value that represents the actual digit. I didn't have the actual digit here since I was using a different data set (the original script used the training data with *does* have the actual digit).

This wasn't all that difficult since I had the original script code I could copy from:

A New Prediction Function

The "evaluate" method takes the classifier (our algorithm) and runs it against all of the data values. The important bit is right in the middle where it calls "classifer x.Pixels". This creates a prediction (and then it compares it to the actual value in the test data).

So, I just pulled that one piece out and created the "predict" method. This would now return a single prediction (a string) based on a single integer array.

Using the Code
Once I had this, I could go to my WPF project and replace the code that called into the C# library with calls to the F# library.

Here's the snippet of code to do that:

Using the F# Code in the C# Application

Since the data comes from a text file and is represented by a list of comma-separated integer values, I first had to do some parsing.

The first line takes that entire string and "Split"s it on the commas. This will give us an array of strings. Then the "Select" does a conversion to turn those string values (such as "50", "240", etc.) into integers. The result is an enumeration of integer values. The final method "ToArray" turns it into the integer array that we need for our function.

This syntax takes a bit of getting used to. But I've found that I've become more and more comfortable with this over the years, and I've started to prefer a fluent syntax (where we "dot" methods together) to pipe the output of one function into the input of another.

This is actually a sign that I should jump into functional programming more. The syntax in F# is a bit cleaner than the "dot" syntax that we use in C#.

After getting the integer array, we can run the "predict" function that we just created. All we have to do is pass in the integer array and the classifier that we want to use. In this case, we're using the "manhattanClassifier" -- this was copied from the script file into the F# file with no changes.

I won't lie. It took me a while to figure out the right syntax for everything here. It was the first time that I was calling F# code from a C# application.

Success!
When I did this, I got a successful output. I was able to display the bitmap side-by-side with the prediction coming from the F# library.

But...
(Everyone I know has a big but...)
The application was *SLOW*. The code with the C# library would load up 1000 records in about 3 minutes. The F# library took 3 times that long.

I figured that I would need to do some optimization. For one thing, I wasn't sure how the F# code was behaving. I was using the "manhattanClassifier" inside of a loop. I was pretty sure that the functions behind this method ran for each loop iteration. This meant loading the training set and other things like that.

I really wanted to simply change the loop that I had from a "foreach" to a "Parallel.ForEach". But that wouldn't work with the existing code. The problem is that I was creating the UI elements (the bitmap image and the text block with the predicted number) inside of the loop. So those really needed to be on the UI thread in order to work.

So, I ended up leaving this code alone for a while.

Optimization - Step 1
At NDC Oslo, I showed the code that I had to Mathias, and he worked with me to figure out where the bottleneck was in the code. When you're optimizing, you first have to figure out where the biggest problem is.

Based on stepping through the code, he suggested that we optimize the code that calculates the distance between the pixels (the so called Manhattan distance). Here's the original code:

Original F# Manhattan Distance Calculation

This function is applied between the pixels of our bitmap and the pixels of all of the data in our training file. So this gets run *a lot*.

Mathias actually suggested that we go a bit non-functional by using mutable data. This would run a bit faster:

Optimized F# Manhattan Distance Calculation

Instead of piping the data through a map function and then summing the values, we created a mutable total object that would be updated along the way.

This seems counter-intuitive to how I felt we *should* be doing things. But sometimes optimization leads us to these types of choices. I'm glad that Mathias was there to recommend this because I never would have thought of this on my own.

With this change in place, the F# code was now just as fast as the C# code. That really makes sense since the C# code is using the doing the same thing. Here's a snippet of the C# code for comparison:

C# Manhattan Distance Calculation

By looking at these 2 blocks of code, it makes sense that these would run at the same speed -- they are doing the same thing.

So I had successfully swapped out the F# code for the C# code and had the same performance in the application. But I knew that I could eke out some more performance by parallelizing things a bit.

Optimization - Step 2
The working application had one big flaw (which is a flaw that I had with the C# code as well). When the application was running, it would go into a "Not Responding" state while the data was loading up. That's because everything was happening on the UI thread. So everything was blocked until the process was complete.

This is never a good experience.

In addition, when I looked at the Task Manager, I saw that only 25% of my CPU was being used by the application (meaning, I was only using 1 of the 4 cores available on my machine).

Time to figure out how to run the calculations in parallel.

I really wanted to use the Parallel.ForEach, even if I had to move my code around a bit. But I couldn't figure out a good way to do that while still keeping things on the appropriate threads. I wanted the "predict" method to run on another thread, but I needed all of the UI element creation and interaction to happen on the UI thread.

So I went to my experience with Task. I knew that I could easily create a Task that would run on a different thread. And then I could create a continuation that ran on the UI thread. (For more information, check out my videos and articles for "I'll Get Back to You: Task, Await, and Asynchronous Methods".)

I extracted out the code that creates the UI elements into a separate method. This was originally inside the foreach loop that iterated over the data:

Creating the UI Elements

Everything in this method should run on the UI thread. To manage that, I created a task and a continuation inside the foreach loop:

Getting Tasks on the Right Threads

The first Task will run the "predict" method on a separate thread. This will keep our UI thread clear during the long processing parts.

After that, we have a continuation that calls the "CreateUIElements" method that we have above. This method will get called after the original task complete. But more importantly, since we have "TaskScheduler.FromCurrentSynchronizationContext()", this will run the "CreateUIElements" method on the UI thread of our application.

This keeps our UI elements on the UI thread and everything else on separate threads.

The Results
The result of creating the tasks is that we now use all 4 cores of my machine, and we can get CPU usage up to 100%.

In addition, our application no longer goes into a "Not Responding" state. Instead, we see the results get gradually added to the list box in our UI as the processes complete. It's not completely smooth. I think the UI thread is still getting starved a bit by the other activity, so sometimes there are pauses and then a bunch of elements get added to the UI at the same time. But the overall effect is good.

FASTER!

As we can see, this loads up the data in 1 minute, 16 seconds. This is about 3 times faster than before (it's not 4 times faster because there's some overhead for the tasks, threading, scheduling, etc.).

As a reminder, you can get the code from the GitHub project: jeremybytes/digit-display and take a look at the FSharpRecognizer branch.

More to Come
I was really excited to get the F# code working in this application. This makes me feel like I can integrate F# code into my existing applications without too much trouble. But this also opened up a lot of possibilities for more exploration.

1. Different Classifiers
In addition to the classifier that uses that Manhattan distance calculation, the F# code has a classifier that uses Euclidean distance. In the script examples that Mathias shows, the Euclidean classifier is more accurate. Now I can swap between the Manhattan classifier and Euclidean classifier to see what the actual output looks like. I'm curious to see if the Euclidean classifier simply reduces the number of errors made by the Manhattan classifier or if it makes completely different errors.

I've already done a bit of this experimentation, so look forward to an article on that soon.

2. Speed - Training Set
The Euclidean classifier is a bit slower than the Manhattan classifier -- the calculation uses a power instead of absolute subtraction. This code runs quite a bit more slowly than the code from Mathias' book, and that's because I'm using a different training set. Mathias uses a portion of the training set provided by Kaggle, but I'm using the entire 40,000 records as the training set. This significantly slows down the predictions.

I've experimented with different size training sets (which affect both performance and accuracy). So the results of that will be coming soon, too.

3. Speed - Prediction
As another way of speeding things up, Mathias suggested that there may be a way to optimize the predictions (such as short-circuiting if a value gets too high). This will require a bit more thought.

4. Speed - Reloading
Finally, I'm pretty sure that the training data is getting reloaded each time I call the "predict" function. When this code is being used in a script, it's really easy to only run part of the script so that the data only gets loaded once. But because I'm calling this in a library, I think it gets run each time. This doesn't appear to be terribly slow, but eliminating duplicate work is always a good idea.

[Update: After some more experimentation, I found that the training data is *not* being reloaded each time.]

So there's still quite a bit of work to do on this application.

Wrap Up
This process has reminded me of how much I like functional programming. I really need to do the deep dive that I've been threatening to do for the last 2 years. The good news is that I've got some downtime after the next few weeks. I think I'll use that time to go full-bore into the functional world. I've spent enough time sitting on the edge; it's time to dive in.

Happy Coding!