Bank OCR kata in F#: user story 1 by Mark Seemann

In case my previous post left readers in doubt about whether or not I like Functional Programming (FP), this post should make it clear that I (also) love FP.

A couple of years ago I had the pleasure of performing a technical review of Real World Functional Programming, which caused me to significantly shift my C# coding style towards a more functional style.

Now I want to take the next step, so I've started doing katas in F#. In a series of blog posts, I'll share my experiences with learning F# as I go along. I'm sure that the F# gods will wince from my code, but that's OK - if any of my readers find this educational, my goal will be met.

In this post I'll start out with the first use case of the Bank OCR kata.

The core unit test #

The first thing I wanted to do was write a couple of tests to demonstrate that I could parse the input. This Parameterized Test uses xUnit.net data theories and FsUnit for the assertion:

[<Theory>]
[<InlineData("
    _  _     _  _  _  _  _ 
  | _| _||_||_ |_   ||_||_|
  ||_  _|  | _||_|  ||_| _|", 123456789)>]
[<InlineData("
    _  _     _  _  _  _  _ 
  | _| _||_||_ |_   ||_||_|
  ||_  _|  | _||_|  ||_||_|", 123456788)>]
[<InlineData("
    _  _     _  _  _  _  _ 
  | _| _||_||_ |_   ||_||_|
  | _| _|  | _||_|  ||_||_|", 133456788)>]
[<InlineData("
    _  _     _  _  _  _  _ 
  | _| _||_||_ |_   ||_|| |
  | _| _|  | _||_|  ||_||_|", 133456780)>]
let ParseToNumberReturnsCorrectResult entry expected =
    entry
    |> ParseToNumber
    |> should equal expected

One of the many nice features of F# is that it's possible to break string literals over multiple lines, so instead of having one wide, unreadable string with "\r\n" instead of line breaks, I could write the test cases directly in the test source code and keep them legible.

In the test function body itself, I pipe the entry function argument into the ParseToNumber function using the pipeline operator |>, so

entry
|> ParseToNumber

is equivalent to writing

ParseToNumber entry

However, by piping the input into the SUT and the result further on to the assertion, I achieve a very dense test method where it's fairly clear that it follows the Arrange Act Assert (AAA) pattern.

The assertion is expressed using FsUnit's F# adapter over xUnit.net. It should be clear that it states that the result (piped from the ParseToNumber function) should be equal to the expected function argument.

Implementation #

Here's the body of the ParseToNumber function:

let ParseToNumber entry =
    entry
    |> ParseToDigits
    |> Seq.map Option.get
    |> Seq.reduce (fun x y -> x * 10 + y)

If you're used to read and write C# you may be wondering about the compactness of it all. Where are all the type declarations?

F# is a strongly typed language, but it has very sophisticated type inferencing capabilities, so the compiler is able to infer that the signature is string - > int, which (in this case) is read as a function which takes a string as input and returns an integer. The equivalent C# notation would be public int ParseToNumber(string entry).

How does the F# compiler know this?

The entry parameter is easy to infer because the function body invokes the ParseToDigits function, which takes a string as input. Therefore, entry must be a string as well.

The output type is a little harder to understand, but basically it boils down to something like this: the ParseToDigits function returns a sequence (basically, an IEnumerable<T>) of integer options. The Seq.map function converts this to a sequence of integers, and the Seq.fold function aggregates that sequence into a single integer.

Don't worry if you didn't understand all that yet - I'll walk you through the body of the function now.

The entry argument is piped into the ParseToDigits function, which returns a sequence of integer options. An option is a type that either has, or doesn't have, a value, so the next step is to unwrap all the values. This is done by piping the option sequence into the Seq.map function, which is equivalent to the LINQ Select method. The Option.get method simply unwraps a single option. It will throw an exception if the value is None, but in this implementation, this is the desired behavior.

The last thing to do is to aggregate the sequence of integers into a single number. The Seq.reduce method aggregates the sequence according to a given accumulator function.

In F#, an inline code block is written with the fun keyword, but it's entirely equivalent to a C# code block, which would look like this:

(x, y) => x * 10 + y

This function basically interprets the sequence of integers as a stream of digits, so in order to arrive at the correct digital representation of the number, each accumulated result is multiplied by ten and added to the new digit.

Obviously, all the real parsing takes place in the ParseToDigits function:

let ParseToDigits (entry : string) =
    let toIntOption ocrDigit =
        match ocrDigit |> Seq.toArray with
        | [| (' ', '|', '|'); ('_', ' ', '_'); (' ', '|', '|') |] -> Some 0
        | [| (' ', ' ', ' '); (' ', ' ', ' '); (' ', '|', '|') |] -> Some 1
        | [| (' ', ' ', '|'); ('_', '_', '_'); (' ', '|', ' ') |] -> Some 2
        | [| (' ', ' ', ' '); ('_', '_', '_'); (' ', '|', '|') |] -> Some 3
        | [| (' ', '|', ' '); (' ', '_', ' '); (' ', '|', '|') |] -> Some 4
        | [| (' ', '|', ' '); ('_', '_', '_'); (' ', ' ', '|') |] -> Some 5
        | [| (' ', '|', '|'); ('_', '_', '_'); (' ', ' ', '|') |] -> Some 6
        | [| (' ', ' ', ' '); ('_', ' ', ' '); (' ', '|', '|') |] -> Some 7
        | [| (' ', '|', '|'); ('_', '_', '_'); (' ', '|', '|') |] -> Some 8
        | [| (' ', '|', ' '); ('_', '_', '_'); (' ', '|', '|') |] -> Some 9
        | _ -> None
 
    let lines = entry.Split([| "\r\n" |], StringSplitOptions.RemoveEmptyEntries)
 
    Seq.zip3 lines.[0] lines.[1] lines.[2]
    |> chunk 3
    |> Seq.map toIntOption

That may look scary, but is actually not that bad.

The function contains the nested function toIntOption which is local to the scope of ParseToDigits. One of the things I don't like that much about F# is that you have to declare and implement the details before the general flow, so you almost have to read the code backwards if you want the overview before diving into all the details.

The first thing the ParseToDigit function does is to split the input into three lines according to the specification of the kata. It uses the standard .NET String.Split method to do that.

Next, it zips each of these three lines with each other. When you zip something, you take the first element of each sequence and create a tuple out of those three elements; then the second element of each sequence, and so forth. The result is a sequence of tuples, where each tuple represents a vertical slice down a digit.

As an example, let's look at the digit 0:

 _ 
| |
|_|

The first vertical slice contains the characters ' ', '|' and '|' so that results in the tuple (' ', '|', '|'). The next vertical slice corresponds to the tuple ('_', ' ', '_') and the third (' ', '|', '|').

With me so far? OK, good.

The Seq.zip3 function produces a sequence of such tuples, but since the kata states that each digit is exactly three characters wide, it's necessary to divide that stream of tuples into chunks of three. In order to do that, I pipe the zipped sequence to the chunk function.

Seq.zip3 lines.[0] lines.[1] lines.[2]
|> chunk 3

I'll post the chunk function further down, but the result is a sequence of sequence of chars which can then be mapped with the toIntOption function.

Now that I've explained how those tuples look, the toIntOption shouldn't be too hard to understand. Each ocrDigit argument is expected to be a sequence of three tuples, so after creating an array from the sequence, the function uses pattern matching to match each tuple array to an option value.

It simply matches an array of the tuples (' ', '|', '|'); ('_', ' ', '_'); (' ', '|', '|') to the number 0 (as explained above), and so on.

If there's no match, it returns the option value None, instead of Some.

Hang on, I'm almost done. The last part of the puzzle is the chunk function:

let rec chunk size sequence =
    let skipOrEmpty size s =
        if s |> Seq.truncate size |> Seq.length >= size
        then s |> Seq.skip size
        else Seq.empty
 
    seq {
        yield sequence |> Seq.truncate size
 
        let next = sequence |> skipOrEmpty size
        if not (Seq.isEmpty next) then yield! chunk size next
        }

Just like the ParseToDigits function, the chunk function uses a nested function to do some of its work.

First of all you may notice that the function declaration uses the rec keyword, which means that this is a recursive function. FP is all about recursion, so this is just something you'll have to get used to.

The main part of the function consists of a sequence expression, denoted by the seq keyword.

First the function returns the first n elements from the sequence, in order to return the first chunk. Next, it skips that chuck and if the sequence isn't empty it recursively calls itself with the rest of the sequence.

The skipOrEmpty function is just a little helper function to work around the behavior of the Seq.skip function, which throws an exception if you ask it to skip some elements of a sequence which doesn't contain that many elements.

That's it. The code is actually quite compact, but I just took a long time explaining it all in some detail.

In a future post I'll walk through the other use cases of the Bank OCR kata.

Comments

• ← Previous
• Archive
• Next →