A man with a chainsaw enters a hardware shop and says to the assistant: "Two weeks ago, you told me this thing would allow me to chop down 30 trees in an hour. But I can only manage one tree. I want to return this for a refund". The assistant says "let me see" and starts the chainsaw. The visitor jumps back screaming "What's that noise?!"-An old joke
The joke opening my narrative is very relevant to the subject of this chapter: in order to achieve the benefits expected from the use of any tool, you should know how to use that tool the right way. Moreover, an advanced tool used in a wrong manner may be even less productive than the corresponding simple one used the right way. A hammer outperforms a microscope when it comes to nailing wooden boards together.
Chapter 1, Begin Thinking Functionally, should help you develop a manner of solving day-to-day software engineering problems that are usually associated with the functional paradigm. This means presenting the solution by verbs rather than nouns, avoiding the use of mutable entities to carry states, avoiding relying upon side-effects, and minimizing the amount of moving parts in the code.
In this chapter, we will cover the following topics:
The multi-paradigm nature of F#
A comparison of F# paradigms by solving the sample problem applying:
An imperative monolithic solution
An object-oriented solution
A functional solution
Properties of the functional paradigm
I will wrap up this chapter with a list of key concepts to retain and recognize, as well as skills to reuse in your functional solutions.
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):
The winning Rank #1 of TIOBE index is held by the Java programming language, which is strongly associated with the object-oriented programming paradigm
Rank #2 belongs to the C programming language, which can be considered representing as the traditional imperative procedural programming paradigm
Programming languages associated with the functional programming paradigm make it into the TIOBE index ranks only for the rank range of 21 to 50, where F# carries modest Rank #36
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:
"it empowers users and organizations to tackle complex computing problems with simple, maintainable and robust code"-(http://fsharp.org/).
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?
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
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
#load "HugeNumber.fs" brings a
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
'9' all have adjacent values after being converted to
int, the simple subtraction of
charZero from the result of converting a
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
forloop 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
let mutable currentProduct = 1provides a mutable placeholder for the product of the current chunk's digits.
The inner numerical
forloop traverses a subarray of length 5, calculating
currentProductby multiplying the intermediary result by the
intvalue of each digit having sequential number
jusing the expression
(int(number.[i + j]) - charZero). For example, if a current digit is
int('5') - int('0') = 5.
ifstatement closing the outer loop ensures that
maxProductalways contains the maximal product of already traversed chunks; hence, when the loop completes iterating,
maxProductcontains 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:
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
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
// 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
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
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:
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
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
maxaggregate 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
intfrom 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:
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.
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
intnumbers, each representing the single digit.
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.
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.reduceconverting 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.
The result of step 5 is piped into the
Seq.maxaggregate function, which produces the sought maximal product that equals
2520(7 * 3 * 6 * 4 * 5)w:
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:
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:
Given the right state upon construction the immutable cannot be invalidated it during its whole lifetime
Immutable entities are easy to test
They do not require cloning or copy constructors
Immutable entities are automatically thread-safe
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:
Take a roasted coffee
Brew two espresso shots
Top them with hot water to produce a layer of crema
Put it into a cap of 12 oz size
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
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.