The Working Programmer : Fun with C#

Ted Neward | July 2014

Ted Neward Learning a new language can help developers bring new insights and new approaches to writing code in other languages, a la C#. My personal preference here is F#, because I’m an F# MVP these days. While I briefly touched on functional programming in an earlier column (bit.ly/1lPaLNr), I want to look at a new language here.

When doing this, it’s likely the code will eventually need to be written in C# (I’ll do that in the next installment). But it can still be helpful to code it in F# for three reasons:

F# can sometimes solve problems like this more easily than C#.
Thinking about a problem in a different language can often help clarify the solution before rewriting it in C#.
F# is a .NET language like its cousin C#. So you could conceivably solve it in F#, then compile it into a .NET assembly and simply call in to it from C#. (Depending on the complexity of the calculation/algorithm, it could actually be the more sane solution.)

Look at the Problem

Consider a simple problem for this type of solution. Imagine you’re working on Speedy, an application for managing personal finance. As part of the app, you need to “reconcile” transactions you’ve found online with the transactions a user has entered into the app. The goal here is to work through two lists of mostly identical data, and match the identical elements. What you do with those unmatched elements isn’t yet unspecified, but you need to capture them.

Years ago, I did some contracting for the “intuitive” company that makes what was then the most popular PC application for managing your banking. This was an actual problem I had to work on there. It was specifically for the checking account register view after downloading a user’s transactions as known by the bank. I had to reconcile those online transactions with ones the user had already entered into the app, and then ask the user about any transactions that didn’t match.

Each transaction consists of an amount, a transaction date and a descriptive “comment.” Here’s the rub: The dates didn’t always match and neither did the comments.

This means the only real credible data I could compare was the transaction amount. Fortunately, it’s pretty rare within a given month that two transactions will be absolutely identical to the penny. So this is a “good enough” solution. I’ll go back and confirm they are in fact a legit match.Just to complicate things, the two incoming lists don’t have to match in length.

An F#ing Solution

There are principles about functional languages that dominate how you “think functionally.” In this case, one of the first is they prefer recursion over iteration. In other words, while the classically trained developer will immediately want to stand up a couple of nested for loops, the functional programmer will want to recurse.

Here, I’ll take the local list of transactions and the remote list of transactions. I’ll go through the first element of each list. If they match, I’ll peel those two off their respective lists, mash them together into the result list, and recursively call again the remainder of the local and remote lists. Look at the type definitions for what I’m working with:

type Transaction =  
  {
    amount : float32;
    date : System.DateTime;
    comment : string
  }
type Register =
  | RegEntry of Transaction * Transaction

In simple terms, I’m defining two types. One is a record type, which is really an object without some of the traditional object notation. The other is a discriminated union type, which is really an object/class graph in disguise. I won’t get into the depths of the F# syntax here. There are plenty of other resources out there for that, including my book, “Professional F# 2.0” (Wrox, 2010).

Suffice it to say, these are the input types and output types, respectively. The reason I chose a discriminated union for the result will soon become apparent. Given these two type definitions, it’s pretty easy to define the outer skeleton of what I want this function to look like:

let reconcile (local : Transaction list) (remote : Transaction list) : Register list =
  []

Remember, in F# parlance, the type descriptors come after the name. So this is declaring a function that takes two Transaction lists and returns a list of Register items. As written, it stubs out to return an empty list (“[]”). This is good, because I can now stub out a few functions to test—Test-Driven Development (TDD) style—in a plain vanilla normal F# console application.

I can and should write these in a unit test framework for now, but I can accomplish essentially the same thing using System.Diagnostics.Debug.Assert and locally nested functions inside of main. Others may prefer to work with the F# REPL, either in Visual Studio or at the command line, as shown in Figure 1.

Figure 1 Create a Console Algorithm with F# REPL

[<EntryPoint>]
let main argv =
  let test1 =
    let local = [ { amount = 20.00f;
                    date = System.DateTime.Now;
                    comment = "ATM Withdrawal" } ]
    let remote = [ { amount = 20.00f;
                     date = System.DateTime.Now;
                     comment = "ATM Withdrawal" } ]
    let register = reconcile local remote
    Debug.Assert(register.Length = 1, 
      "Matches should have come back with one item")
  let test2 =
    let local = [ { amount = 20.00f;
                    date = System.DateTime.Now;
                    comment = "ATM Withdrawal" };
                  { amount = 40.00f;
                    date = System.DateTime.Now;
                    comment = "ATM Withdrawal" } ]
    let remote = [ { amount = 20.00f;
                     date = System.DateTime.Now;
                     comment = "ATM Withdrawal" } ]
    let register = reconcile local remote
    Debug.Assert(register.Length = 1, 
      "Register should have come back with one item")
  0 // Return an integer exit code

Given that I have a basic test scaffold in place, I’ll attack the recursive solution, as you can see in Figure 2.

Figure 2 Use F# Pattern Matching for a Recursive Solution

let reconcile (local : Transaction list) 
  (remote : Transaction list) : Register list =
  let rec reconcileInternal outputSoFar local remote =
    match (local, remote) with
    | [], _ -> outputSoFar
    | _, [] -> outputSoFar
    | loc :: locTail, rem :: remTail ->
      match (loc.amount, rem.amount) with
      | (locAmt, remAmt) when locAmt = remAmt ->
         reconcileInternal (RegEntry(loc, rem) :: outputSoFar) locTail remTail
      | (locAmt, remAmt) when locAmt < remAmt ->
         reconcileInternal outputSoFar locTail remTail
      | (locAmt, remAmt) when remAmt > locAmt ->
         reconcileInternal outputSoFar locTail remTail
      | (_, _) ->
         failwith("How is this possible?")
  reconcileInternal [] local remote

As you’ll notice, this makes pretty heavy use of F# pattern matching. This is conceptually similar to the C# switch block (in the same way a kitten is conceptually similar to a saber-toothed tiger). First, I define a local recursive (rec) function that’s basically the same signature as the outer function. There’s an additional parameter to carry the matched results so far.

Within that, the first match block examines both the local and remote lists. The first match clause ( [],_) says if the local list is empty, I don’t care what the remote list is (the underscore is a wildcard) because I’m done. So just return the results obtained so far. The same goes for the second match clause ( _, []).

The meat of the whole thing comes in the last match clause. This extracts the head of the local list and binds it to the value loc, puts the rest of the list into locTail, does the same for remote into rem and remTail, and then matches again. This time, I extract the amount fields from each of the two items peeled off out of the lists, and bind them into the local variables locAmt and remAmt.

For each of these match clauses, I’ll recursively invoke reconcileInternal. The key difference is what I do with the outputSoFar list before I recurse. If the locAmt and remAmt are the same, it’s a match, so I prepend a new RegEntry into the outputSoFar list before recursing. In any other case, I just ignore them and recurse. The result will be a list of RegEntry items, and that’s what’s returned to the caller.

Extend the Idea

Suppose I can’t just ignore those mismatched items. I need to put an item into the resulting list that says it was an unmatched local transaction or an unmatched remote transaction. The core algorithm still holds, I just add new items into the Register discriminated union to hold each of those possibilities, and append them into the list before recursing, as shown in Figure 3.

Figure 3 Add New Items to the Register

type Register =
  | RegEntry of Transaction * Transaction
  | MissingRemote of Transaction
  | MissingLocal of Transaction
let reconcile (local : Transaction list)
 (remote : Transaction list) : Register list =
  let rec reconcileInternal outputSoFar local remote =
    match (local, remote) with
    | [], _
    | _, [] -> outputSoFar
    | loc :: locTail, rem :: remTail ->
      match (loc.amount, rem.amount) with
      | (locAmt, remAmt) when locAmt = remAmt ->
         reconcileInternal (RegEntry(loc, rem) :: outputSoFar) locTail remTail
      | (locAmt, remAmt) when locAmt < remAmt ->
         reconcileInternal (MissingRemote(loc) :: outputSoFar) locTail remote
      | (locAmt, remAmt) when locAmt > remAmt ->
         reconcileInternal (MissingLocal(rem) :: outputSoFar) local remTail
      | _ ->
         failwith "How is this possible?"
  reconcileInternal [] local remote

Now the results will be a complete list, with MissingLocal or MissingRemote entries for each Transaction that doesn’t have a corresponding pair. Actually, this isn’t quite true. If the two lists are mismatched in length, like my test2 case earlier, the leftover items won’t be given “Missing” entries.

By taking F# as the “conceptualizing” language instead of C# and using functional programming principles, this became a pretty quick solution. F# uses extensive type inference, so in many cases while fleshing out the code, I didn’t have to determine the actual types for the parameters and return ahead of time. Recursive functions in F# will often need a type annotation to define the return type. I got away without it here because it could infer from the return type given on the outer, enclosing function.

In some cases, I could just compile this into an assembly and hand it to the C# developers. For a lot of shops, though, that’s not going to fly. So next time, I’ll convert this to C#. The boss will never know that this code actually started life as F# code.

Happy coding!

Ted Neward is the CTO at iTrellis, a consulting services company. He has written more than 100 articles and authored and coauthored a dozen books, including “Professional F# 2.0” (Wrox, 2010). He’s a C# MVP and speaks at conferences around the world. He consults and mentors regularly—reach him at ted@tedneward.com or ted@itrellis.com if you’re interested in having him come work with your team, and read his blog at blogs.tedneward.com.

Thanks to the following Microsoft technical expert for reviewing this article: Lincoln Atkinson

The Working Programmer : Fun with C#

Look at the Problem

An F#ing Solution

Extend the Idea

Additional resources