F# 4.0 Design Patterns

This chapter, as well as the other chapters, will teach you how to look at any given software problem from the functional paradigm angle. This view may differ significantly from paradigmatic views that you may have already developed while practising other programming approches. This assumption of the required paradigmatic shift is a much anticipated scenario, taking into consideration the factor of the programming language popularity of the so called TIOBEProgramming Community index (http://www.tiobe.com/tiobe_index?page=index), which can be considered an indicator of the popularity of programming languages.

At the time of this writing (February 2016):

Nevertheless, if you've managed to read upto this point, I can safely assume that your interest in F# is not driven by its mere popularity, which, in turn, is driven by factors that do not belong to the scope of this book. For me, the bearer of an advanced degree in applied math and computer science, engineering program code within the F# ecosystem carries these intangible aesthetic qualities similar to ones of exploring a beautiful solution of a math problem or from analyzing a great chess play.

Talking seriously, I personally value most of the functional paradigm benefits of the functional code readability and maintainability. The same qualities of a typical monolithic imperative C code might be quite poor. However, are these code qualities automatically granted for anyone who has grasped mere F# syntax? Certainly not.

In addition to learning the F# syntax, the preceding point means acquiring certain skills in order to use this programming language in an idiomatic manner. F# is a multi-paradigm programming language indeed. It allows programmers to entertain many programming paradigms. The functional manner of laying out the program code can be used side by side with the imperative monolithic programming manner, or an object-oriented approach may surface when interoperability with the environment is important . Nevertheless, F# makes a claim of being a functional-first programming language. This means that the congenial programming paradigm for F# is the functional one; the language will bring to the table most benefits if it's used in a functional manner, in which case:

You may wonder what, exactly, idiomatic usage means and whether it will be possible to always use it. The best way of illustrating idiomatic F# use would be by performing a comparative study of correspondent coding examples. Let me take an arbitrary, simple problem and solve it by sticking to imperative, then to object-oriented, and finally, to functional paradigms. Then, I am going to compare solutions to highlight functional approach features. In order to make this comparison absolutely fair, the programming language of implementation in all three cases is going to be F#.

I will use as a problem for the purpose the slightly amended version of Problem 8 of Project Euler (https://projecteuler.net/problem=8):

The four adjacent digits (9989) being highlighted in the 1000-digit numbers that have the greatest product are as following: 
9 x 9 x 8 x 9 = 5832. 
 
73167176531330624919225119674426574742355349194934 
96983520312774506326239578318016984801869478851843 
85861560789112949495459501737958331952853208805511 
12540698747158523863050715693290963295227443043557 
66896648950445244523161731856403098711121722383113 
62229893423380308135336276614282806444486645238749 
30358907296290491560440772390713810515859307960866 
70172427121883998797908792274921901699720888093776 
65727333001053367881220235421809751254540594752243 
52584907711670556013604839586446706324415722155397 
53697817977846174064955149290862569321978468622482 
83972241375657056057490261407972968652414535100474 
82166370484403199890008895243450658541227588666881 
16427171479924442928230863465674813919123162824586 
17866458359124566529476545682848912883142607690042 
24219022671055626321111109370544217506941658960408 
07198403850962455444362981230987879927244284909188 
84580156166097919133875499200524063689912560717606 
05886116467109405077541002256983155200055935729725 
71636269561882670428252483600823257530420752963450 
 
Find the five adjacent digits in the same 1000-digit number that has the greatest product. What is the value of this product? 

An imperative monolithic solution

Let me begin by approaching the solution in a straightforward monolithic imperative manner: convert the 1000-character string representing the number into a character array, and then convert it into a cycle across all 996 groups of the five adjacent digits, calculating the digit product of each group and maintaining the current maximum. The final value of the current maximum will be the solution; it's that simple.

In order to remove the input number from the way, let's put it into a separate source code file, HugeNumber.fs, pulled to the solution scripts with the F# #load directive. The F# source file HugeNumber.fs is shown as follows:

[<AutoOpen>] 
module HugeNumber 
let hugeNumber = 
    "73167176531330624919225119674426574742355349194934\ 
    96983520312774506326239578318016984801869478851843\ 
    85861560789112949495459501737958331952853208805511\ 
    12540698747158523863050715693290963295227443043557\ 
    66896648950445244523161731856403098711121722383113\ 
    62229893423380308135336276614282806444486645238749\ 
    30358907296290491560440772390713810515859307960866\ 
    70172427121883998797908792274921901699720888093776\ 
    65727333001053367881220235421809751254540594752243\ 
    52584907711670556013604839586446706324415722155397\ 
    53697817977846174064955149290862569321978468622482\ 
    83972241375657056057490261407972968652414535100474\ 
    82166370484403199890008895243450658541227588666881\ 
    16427171479924442928230863465674813919123162824586\ 
    17866458359124566529476545682848912883142607690042\ 
    24219022671055626321111109370544217506941658960408\ 
    07198403850962455444362981230987879927244284909188\ 
    84580156166097919133875499200524063689912560717606\ 
    05886116467109405077541002256983155200055935729725\ 
 71636269561882670428252483600823257530420752963450" 

This file is going to be used by all variants of the problem solutions.

Then, F# script Ch1_1.fsx implementing an imperative solution will look as follows:

// Imperative monolithic solution a-la C/C++ 
#load "HugeNumber.fs" 
let number = hugeNumber.ToCharArray() 
let mutable maxProduct = 0 
let charZero = int('0') 
for i in 0..995 do 
  let mutable currentProduct = 1 
for j in 0..4 do 
  currentProduct <- currentProduct * (int(number.[i + j]) -      charZero) 
if maxProduct < currentProduct then 
  maxProduct <- currentProduct 
printfn "%s %d" "Imperative solution:" maxProduct 

The line #load "HugeNumber.fs" brings a string value HugeNumber.hugeNumber from the external code file HugeNumber.fs into the scope of this script.

The next line, let number = hugeNumber.ToCharArray() converts this string value into an array of 1000 individual characters, each representing a single digit.

The next line, let mutable maxProduct = 0 introduces a mutable int value used to carry the running tally of a maximal product of five adjacent digits.

The following line let charZero = int('0') is just a helper value used for converting a character code of a digit into an actual int value in the range of 0 to 9. It represents integer 48 indeed, not 0 as some of you may expect. But given char values of decimal digits '0' to '9' all have adjacent values after being converted to int, the simple subtraction of charZero from the result of converting a char digit x into an int will yield exactly x as an integer. More details on this matter will be given as we proceed further in this chapter.

The following seven lines of F# code are the gist of implementation:

for i in 0..995 do 
  let mutable currentProduct = 1 
for j in 0..4 do 
  currentProduct <- currentProduct * (int(number.[i + j]) -     charZero) 
if maxProduct < currentProduct then 
  maxProduct <- currentProduct 

This part of the script performs the following actions:

• The outer numerical for loop traverses the number array from the leftmost to the rightmost chunk of the five adjacent character digits, keeping the sequential number of the chunk (0,1,2,...,955) in the counter value i.

• The binding let mutable currentProduct = 1 provides a mutable placeholder for the product of the current chunk's digits.

• The inner numerical for loop traverses a subarray of length 5, calculating currentProduct by multiplying the intermediary result by the int value of each digit having sequential number j using the expression (int(number.[i + j]) - charZero). For example, if a current digit is 5, then int('5') - int('0') = 5.

• An if statement closing the outer loop ensures that maxProduct always contains the maximal product of already traversed chunks; hence, when the loop completes iterating, maxProduct contains the sought value.

Finally, the line printfn "%s %d" "Imperative solution:" maxProduct outputs the final result to the system console.

Running the script in its entirety with F# Interactive (FSI) yields the following solution:

Running an imperative solution script in F# Interactive

There are a few points that I would like to accentuate prior to covering other approaches to solving the problem as follows:

• The solution represents detailed "how-to" instructions

• The solution has been expressed in terms of low-level computer notions, such as statements, loops, and global values

• Values change along the execution, representing the changing state

• The solution code does not look structured, it just flows

An object-oriented solution

Now let me turn to the object-oriented manner of solving the same problem. It is typical for this kind of approach to hide implementation details inside instances of custom classes and manipulate them with the help of their own methods. I will use for this purpose the F# type feature representing the concept of the .NET object type also known as class (https://docs.microsoft.com/en-us/dotnet/articles/fsharp/language-reference/classes). An object-oriented solution to the problem is present in the following code (script Ch1_2.fsx):

// Object-oriented solution a-la C# with Iterator pattern 
#load "HugeNumber.fs" 
 
open System 
open System.Collections.Generic 
 
type OfDigits(digits: char[]) = 
    let mutable product = 1 
    do 
        if digits.Length > 9 then // (9 ** 10) > Int32.MaxValue 
            raise <| ArgumentOutOfRangeException 
              ("Constrained to max 9 digit numbers") 
        let charZero = int '0' in 
        for d in digits do 
            product <- product * ((int d) - charZero) 
        member this.Product 
            with get() = product 
 
type SequenceOfDigits(digits: string, itemLen: int) = 
    let collection: OfDigits[] = 
       Array.zeroCreate(digits.Length -itemLen + 1) 
    do 
      for i in 0 .. digits.Length - itemLen do 
        collection.[i] <- OfDigits(digits.[i..
           (i+itemLen-1)].ToCharArray()) 
    member this.GetEnumerator() = 
        (collection :> IEnumerable<OfDigits>).GetEnumerator() 
 
let mutable maxProduct = 1 
for item in SequenceOfDigits(hugeNumber,5) do 
    maxProduct <- max maxProduct item.Product 
 
printfn "%s %d" "Object-oriented solution:" maxProduct 

This solution is going to manipulate the objects of two classes. The first class named OfDigits represents the entity of the digit sequence, the product of which is the subject of our interest. An instance of OfDigits can be created from an array of a certain size of char elements carrying digits used as an argument to the OfDigits type constructor OfDigits(digits: char[]).

Upon its creation, each instance is associated with the product field representing the product of its digits. There is a reason for it not being possible to initialize product at once: in order to be representable as a positive integer value, the product can be constituted of nine digits or fewer (because the product of 10 or more 9 would exceed the maximum 32-bit int value 2147483647). In order to validate this, product is kept mutable and initially gets a value of 1 as given in the following line:

let mutable product = 1 

Then, after the length validity check, the OfDigits constructor provides the genuine value to the field by performing the calculation:

let charZero = int '0' in 
for d in digits do 
  product <- product * ((int d) - charZero) 

This value can be accessed via the instance property, Product as shown in the following line:

member this.Product with get() = product 

The another class required to implement the object-oriented solution represents the entity taking a string of digits of arbitrary length and represents it as a generic collection of type OfDigits, allowing enumeration in order to traverse it and find a member with the maximum Product property.

For this purpose, the class named SequenceOfDigits has been equipped with a constructor parameterized by the digits string carrying the input number's digits and the itemLen length of individual OfDigits instance arguments. During the SequenceOfDigits instance construction, all OfDigits instances are created as elements of the collection field array. The GetEnumerator() instance method allows you to enumerate this array by upcasting to the System.Collections.Generic.IEnumerable<OfDigits> interface type and delegating the call to the GetEnumerator() method of the latter in the following instance method definition:

member this.GetEnumerator() =  (collection :> IEnumerable<OfDigits>).GetEnumerator() 

Having the preceding two classes at your disposal makes composing the solution of the original problem rather simple: you construct a SequenceOfDigits instance of five digit OfDigits elements off hugeNumber and traverse it with the help of the for...in cycle, maintaining the maximum product tally similarly to the imperative solution as shown in the following code:

let mutable maxProduct = 1 
for item in SequenceOfDigits(hugeNumber,5)
  do  maxProduct <- max maxProduct item.Product 

In the end, place the result on the system console. Running the script in its entirety with F# FSI yields the result of object-oriented solution as shown in the following screenshot:

Running object-oriented solution script in F# Interactive

For those of you familiar with the object-oriented manner of approaching problem solutions, you may anticipate that the second solution rather differs from the first one:

• It is distinctively structured, with the segregation of definitions of pertinent classes from the usage of these classes

• Classes hide details of implementation, allowing usage only through exposed properties and methods

• The solution follows one of the well-known design patterns, namely the iterator pattern

• The amount of effort required for scaffolding substantially exceeds the effort required for the solution per se

A functional solution

Finally, let me turn to the solution manner that this book targets, namely, functional. Let's think of it as a series of data transformations. Let's look at it in a backward direction, from the sought solution back to the input string of digits as follows:

• The sought solution is the result of the max aggregate function application to the sequence of all products of five digit sequences.

• The sequence of all five digit sequences products is the result of the function application that maps each five digit sequence instance from the sequence of such sequences to the reduce of five digit sequence digits to their product.

• The sequence of all five digit sequences can be produced from the sequence of all initial digits by applying the F# core library windowing function Seq.windowed<'T> to the latter. In other words, this means taking a copy sequence of the first five digits from the left-hand side, placing this sequence in the output, shifting to the right of the source sequence by one digit, taking the first five digit copy and putting them after the first group in the output, shifting to the right by one digit of the source again, taking the first five digits, and so on, until there is no more possibility of taking the first five digits from the source. The output sequence of sequences is the sought function application result.

• Finally, the sequence of all initial digits is simply the initial string split by single digits, each converted into correspondent int from 0 to 9.

Each preceding step describes what transformation I want to apply to the single input argument in order to get the single result. Each next step takes the result of the previous step and treats it as its own input.

Let me show you how I usually derive the working code from the data transformation sketch similar to the preceding one with the help of the Read-Evaluate-Print-Loop (REPL) mode provided by FSI and the shrinking task dimension. The process of sequential progress toward the solution is shown in Fig.1.3, where I gradually start adding transformation steps to reproduce the data transformation process sketched earlier for a string consisting of just 10 digits "0918273645" by following these steps:

1. The input string is piped forward with the F# operator of the same name pipe-forward  |> as the second argument of Seq.map string. The result is the sequence of 10 strings, each representing a single digit.

2. The result of step 1 is piped forward with |> as the second argument of Seq.map int. Now, the result is also the sequence, but it is a sequence of 10 int numbers, each representing the single digit.

3. The result of step 2 is piped forward with |> as the second argument of Seq.windowed 5. The result is the sequence of six arrays, each representing five sequentially taken digits of the result of step 2, each time shifting the beginning of the sequence to the right by one position.

4. The result of step 3 is piped forward with |> as the second argument of Seq.map (Seq.reduce (*)). The first argument is the higher-order function Seq.reduce converting its argument, which is an array of five numbers to the product of these numbers with the help of the multiplication operator ( * ). The result of this transformation step is just six numbers, each representing the product of the elements of the corresponding digit array.

5. The result of step 5 is piped into the Seq.max aggregate function, which produces the sought maximal product that equals 2520(7 * 3 * 6 * 4 * 5)w:

The incremental process of getting to the smaller problem solution with REPL

Now, after becoming pretty confident that the thought-out solution is good, I can combine the preceding steps 1 to 5 with just another F# function composition operator >>, which just glues the result of the function to the left as an argument of the function to the right into a very compact F# script provided in the file Ch1_3.fsx as follows:

#load "HugeNumber.fs" 
hugeNumber |> (Seq.map (string >> int) >> Seq.windowed 5 
>> Seq.map (Seq.reduce (*)) >> Seq.max 
>> printfn "%s %d" "Functional solution:") 

The only difference between the preceding complete problem solution code and the smaller problem solution that I was running through a few REPL steps is the input value dimension. The final code uses the same 1000 digit hugeNumber taken from the source file HugeNumber.fs in the same manner as the imperative and object-oriented solutions did previously.

Running the script in its entirety with FSI yields the functional solution result shown in the following figure:

Running the functional solution script in F# Interactive

The code quality achieved by the functional solution, despite somewhat lengthy accompanying comments, is quite outstanding:

• It does not utilize even a single value carrying an intermediate state

• It contains just one arithmetic multiplication operator absolutely needed for product calculation

• It is extremely succinct

• It almost literally reflects the original "what to do" considerations

• It uses solely half a dozen core F# library functions combined in a certain way, and we may strongly believe that the implementations of these functions are error-free and performant

The preceding bullet points reflect pretty much all the properties typical for an idiomatic functional solution of a small-scale problem. Now I'm going to decipher these properties one by one.

The positive qualities of the approach of not using mutable program entities are well known:

I must note that F# is not 100% strict about using immutable entities. As you may have already noticed, I used values, changing the state in my imperative and object-oriented solutions earlier. But the language requires the programmer to make an extra effort to introduce a changeable state (with the mutable modifier to let binding or via ref cells, although F# 4.0 pretty much eliminates the need for the latter).

Also, the majority of data structures introduced by the language are also immutable, which means that a typical data transformation produces a new immutable instance of a data structure from the existing data structure. This consideration requires a certain caution from programmers when dealing with bulk in-memory instances, but as my experience has taught me, developers get used to this feature easily.

Considering the process of data transformations in terms of verbs rather than nouns is very typical for a functional approach as functions are intuitively associated in our brains with actions, not objects. You may notice the single data item in the script Ch1_3.fsx, which is hugeNumber. The rest are few library functions combined in a certain manner, which transform the hugeNumber data item into a line of the console output. This manner of function combination allows persons reading this code to completely ignore intermediate results of the data transformations at each point where the operator >> occurs in the expression.

The less obvious corollary of this combination is the opportunity for the F# compiler to perform a so-called fusion or the manner of code optimization by merging together some adjacent data transformation steps. For example, when adjacent steps are fused together, the amount of data traversals may decrease.

This property of the functional solution mental process is easier to demonstrate with an example. I paraphrase here the great one from the early days of F# that's been used by several insiders previously. Imagine yourself in Starbucks for Caffè Americano.

The "how" approach would be to give detailed instructions such as:

The "what" approach would be to just ask "May I have a tall Caffè Americano?".

The second approach is evidently much more succinct and minimizes an opportunity of getting a result that deviates from the desired one. If you revisit now our three preceding solutions you should spot this property there.

Another outstanding feature of the functional paradigm is generalization. By this, I mean preferring a general solution over a concrete one, when a concrete problem can be solved by applying a general solution that is accordingly parameterized. Let's turn to our sample problem for evidence of generalization. Adjusting the functional solution to a different length of digit sequences (for example, 8 instead of 5), another math operation on the group (for example, the sum instead of the product), another aggregation property (for example, minimum instead of maximum) are mere changes of parameter values for the correspondent functions. A comparison of how much the code changes will be required in case of the other approaches, which I leave for you as an exercise.

This property is specifically related to a functional approach in comparison with an object-oriented one. Recall F# script file Ch1_2.fsx, which involved custom classes encapsulating details of implementation and exposing them outside the constructor, the iterator, and the aggregated property. In comparison with the object-oriented approach, the functional approach is flat and does not hide anything; it just combines some known parts.

One of the amazing properties of a functional paradigm differentiating it from the others is the limited need for producing custom parts at the level of manipulating data structures. Usually, functional programming newbies tend to implement their own functions for each case of data transformation. This infantile sickness normally ends with finding out from practice that pretty much any transformation upon typical data structures can be expressed as a combination of filter, map, and fold operations. I will devote a substantial amount of contents in relation to this phenomenon.

Let me turn your attention to the comparison of memory consumption of the previously mentioned object-oriented and functional solutions. The object-oriented solution eagerly creates, materializes in computer memory the collection of 996 OfDigits objects; that is, its memory consumption is a linear function of the problem dimensions. In contrast to this approach, the functional solution does not require more than a single instance of OfDigits at any moment of the max aggregation, lazily producing the same 996 objects one by one according to the demand of the max aggregator function, hence having memory consumption that is constant and (almost) independent of the problem dimensions. This is a rather complex quality. If you imagine that the initial condition has suddenly changed and hugeNumber is really huge, then the object-oriented solution may become non-applicable due to the lack of required memory, while the functional solution, being agnostic to this factor, will continue to work. Generalizing this observation, the functional paradigm allows you to solve problems of a bigger scale, rather than taking other approaches by utilizing the lazy manner of data manipulation. The interesting corollary stemming from this approach is the technique of manipulating data sequences of unlimited length that do not require their complete materialization in the memory.

The following are the key concepts and the list of skills you should take away after finishing this chapter and strive for absorbing and mastering:

Avoid mutable state and achieve data transformations over immutable values and data structures. Think of programming solutions in terms of verbs rather than nouns. Avoid expressing a solution in highly detailed imperative "how" statements; use the "what to do" approach instead. Generalize: prefer a general parameterized solution to a concrete one. Strive to minimize the moving parts of your solution instead of hiding these moving parts into classes. Try expressing solutions by a few well-known facilities instead of delving into producing custom ones. When appropriate, prefer lazy data collections (sequences) over eager ones.

This process of mastering the functional manner of thinking may be framed around the following three Rs - Retain, Recognize, and Reuse. The sooner you learn to recognize idiomatic functional design patterns which I'm going to cover with a great amount of detail in this book and the sooner you reuse these patterns again and again in your day-to-day coding activities, the better functional programmer you will become.

In the upcoming chapters, I will walk you over the many idiomatic uses of F# in certain development situations. These repeated usages will represent genuine functional programming design patterns. Please keep in mind that many of these patterns only to a certain extent correlate with traditional object-oriented design patterns (https://en.wikipedia.org/wiki/Design_Patterns), as well as other architecture design patterns of software engineering (http://www.amazon.com/Patterns-Enterprise-Application-Architecture-Martin/dp/0321127420).

In the next chapter, I'll give you a 360-degree high-level view of the F# language features and parts with their origins and evolvement.