A sample problem to solve

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:

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:

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:

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:

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:

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:

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.