Book Image

Learning F# Functional Data Structures and Algorithms

By : Adnan Masood
Book Image

Learning F# Functional Data Structures and Algorithms

By: Adnan Masood

Overview of this book

Table of Contents (21 chapters)
Learning F# Functional Data Structures and Algorithms
Credits
Foreword
Foreword
Foreword
About the Author
Acknowledgments
About the Reviewers
www.PacktPub.com
Preface
Index

A brief F# language primer


Even though this book is not intended to be an absolute beginner's primer to F#, if you are new to F# there are certain language fundamentals you must know in order to maximize your learning from this book. Following is a quick F# refresher on basic language constructs, keywords, and salient syntactical features that you will find useful during the course of reading this book Several of these items, especially those related to data-structures, are discussed in greater detail in the following chapters. You can download all these examples and source code from the book GitHub repository at https://github.com/adnanmasood/Learning-fsharp.

F# is a statically typed language, that is, types of the variables are known at compile time. Like all other static type languages, F# uses a type inference to resolve the variable type. F# comes with standard data types such as byte, sbyte, int16, uint16, int, uint, int64, uint64, native int, unsigned native int, float or double, float32, decimal, and bignum (System.Numerics.BigInteger). A few simple declarations with appropriate suffixes can be seen as follows:

let byte b = 10uy
let sbyte sb = -128y
let int16 i = -100s
let uint16 ui = 100us
let int = -42
let uint = 0x42u
let int64 = 238900L
let uint64 = 2,660,000,000UL
let float f = 3.14159265359
let double db = 2.718281828459045
let float32 f32 = 2.7182818
let decimal d = 3.14159265358979323846264338
let bignum gogol = 10I ** 100
let string = "nà, méi guānxi"

Similar to standard CLR data types, F# also uses the standard mathematical operators such as . Logical operators are supported along with mathematical functions such as . A detailed F# language reference, including Symbol and Operator Reference, can be found at http://msdn.microsoft.com/en-us/library/dd233228.aspx.

At this time, we would also like to briefly introduce you to one of the highly useful features of F# IDE, the REPL. REPL (Read–Eval–Print Loop) is an interactive language shell to take expression inputs, evaluate, and provide output to the users. REPL allows developers to interact with the language easily and to invoke and test expressions in real-time before writing the entire program. FSI (F Sharp Interactive) is the REPL implementation in F#. You will read more about installing and configuring FSI in Chapter 2, Now Lazily Get Over It, Again. For now you can use the command line version of FSI by invoking it directly in a console:

C:\Program Files\Microsoft F#\v4.0\fsi.exe

You can also use the #help;; directive to list other directives inside FSI.

You will see the let binding being used quite frequently for declaring variables, functions, and so on. Functions put functions in functional programming and hence, they are ubiquitous. Technically speaking, F# doesn't have any statements, it only has expressions. The following is a simple example of a function:

let cubeMe x = x * x * x;;

Instead of explicitly returning a value, F# uses a succinct syntax of returning the value of the expression last evaluated.

val cubeMe : x:int -> int
> > cubeMe 9;;
val it : int = 729

Recursive functions are defined using the keyword rec. Here is a simple implementation of a recursive Fibonacci function:

let rec fib n =
  if n <= 2 then 1
  else fib (n - 1) + fib (n - 2)

The preceding code for the Fibonacci method takes one parameter as an input. However, a function can have more than one parameters following the same code.

let Mult x y = x * y ;;

Type inference in F# is an important construct to remember. For instance, in the case of the multiplication function in the preceding line of code, F# assumes the type inference of the arguments as int. A hint can be provided to specify the appropriate data type.

let Mult (x: float) (y: float) = x * y ;;

Nested or anonymous functions are now commonplace in languages such as C# and Java. These are the special functions that reside inside another function and are not visible from an outside scope. For instance, refer to the following code snippet:

let areaOfCircle r = 
  let square r = r * r
  System.Math.PI * square r;;

However the preceding function will fail upon execution without a hint. We will see the following error on screen:

error FS0001: This expression was expected to have type   float    but here has type    int    

But the same method will work just fine if the specified data type is passed as float.

> areaOfCircle 8.0;;
val it : float = 201.0619298

Moreover, you cannot call the inner function directly. That is why the direct call to the square method will return the following error:

square 10;;
^^^^^^
error FS0039: The value or constructor 'square' is not defined

The conditionals are fundamental to any programming language. F# provides a great pattern-matching scheme along with traditional if...else expressions. The following is a simple if...else check:

let Mod10 n = 
  if n % 10 = 0 then
    printfn "Number ends in 0"
  else
    printfn "Number does not end in zero";;

The print expression will return a value. You can also see the use of elif which is used as a shortcut for else if.

Tuples are now part of a standard CLR system, but most of us remember the struggle before tuples. Tuples are the containers for potentially different types, as seen in the following code:

let t = ("cats", "dogs", System.Math.PI, 42, "C#", "Java");;
val t : string * string * float * int * string * string = ("cats", "dogs", 3.141592654, 42, "C#", "Java")

Speaking of collections, arrays in F# are mutable, fixed-sized sequences. Arrays are fixed in size and zero-indexed, with the elements encapsulated within [| … |] and separated by a semi-colon.

let GuardiansOfGalaxy = [| "Peter Quill"; "Gamora"; "Drax"; "Groot"; "Rocket"; "Ronan"; "Yondu Udonta"; "Nebula"; "Korath"; "Corpsman Dey";"Nova Prime";"The Collector";"Meredith Quill" |]

The individual elements of the array can be accessed as follows:

let iAmGroot = GuardiansOfGalaxy.[4];
val iAmGroot : string = "Rocket"

This also applies to the strings where you can access an individual element of a string as follows:

let str = "Lǎo péngyǒu, nǐ kànqǐlái hěn yǒu jīngshén."
printfn "%c" str.[9]

Arrays can be created using ranges as follows:

let OneToHundred = [|1..100|];;

They can be sliced using index (arrays are zero base indexed) as seen in the following code:

let TopThree = OneToHundred.[0..2];;

Functions in F# can be applied partially; it gets interesting here. A simple add function can be defined as follows:

let add x y = x + y;;

We can apply it partially to make it add 10 every time. Therefore, the following statement:

(add 10) 4;;

This can be bound as a method name, or a closure to be exact as seen here:

let Add10 = add 10;
val Add10 : (int -> int)

This can be explicitly called like the original method, allowing us to compose complex methods using the basic ones. Here, Add10 is a closure that takes one argument and adds 10 to it as seen in the following code:

Add10 42
> 
val it : int = 52

Closures are functionally defined as a first-class function with free variables that are bound in the lexical environment. In F#, functions are first class members of the programming society; closures encapsulate an environment for pre-bound variables and create a code block. This way we can pre-define some arguments (in this case, 10). Closure promotes reuse and helps in building complex functions from simpler ones.

With functions as the first class citizens, in F# we can create higher order functions, that is, functions upon functions. Higher order functions operate by taking a function as an argument, or by returning a function. Following are two simple functions:

let increament n = n + 1
let divideByTwo n = n / 2

Now we will define a higher order function which applies function upon function:

let InvokeThrice n (f:int->int) = f(f(f(n)))

Now we will use the InvokeThrice function, which will apply the function upon itself three times as defined in the preceding line of code:

let res = InvokeThrice 6 increament
> 
val res : int = 9

In this example, you witnessed the amazing power of declaring functions. A similar approach can be applied to division as follows:

let res = InvokeThrice 80 divideByTwo
> 
val res : int = 10

In the preceding syntax for the InvokeThrice function, you will notice the use of a lambda expression. Lambda expressions are ubiquitous in functional programming. In reality, these expressions are syntactic sugar (directives, shortcuts, or a terse way of defining something) to declare anonymous methods. A lambda expression is created using the fun keyword, that is, function, followed by arguments which are supposed to be passed to the function. This function declaration is then followed by the lambda arrow operator -> and the lambda expression which defines the body of the function. For example, instead of passing the function, I can pass the lambda expression during the InvokeThrice invocation to apply exponential operation (power 3).

let InvokeThrice n (f:double->double) = f(f(f(n)))
let x = InvokeThrice 2.0 (fun n -> n ** 3.0)

val x : double = 134217728.0

Another frequently used F# operator is pipelining |>, which allows us to push arguments onto functions. For example, check the following cubeMe method:

let cubeMe x = x * x * x;;

The preceding method can also be called as cubeMe 3 or 3 |> cubeMe.

The results will be the same. The pipelining operator allows us to do chaining such as:

2 |> cubeMe |> cubeMe |> cubeMe 
> val it : int = 134217728

This comes in handy when you build functional composites.

Mapping is a frequently used operation in functional programming. Map applies functions on a collection, and displays output as a new list, based on the result of this function. For arrays, F# provides a built-in operation called map. The map operation takes two arguments—a function and an array of elements. For example, refer to the following array of integers:

let nums = [|0..99|]

val nums : int [] =
  [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 
  //snip
  97; 98; 99|]

The following is the mapping function that will square all the elements in the array, and return a new array:

let squares = 
  nums
  |> Array.map (fun n -> n * n)

When you run the square method on nums, you get the following output:

val squares : int [] =
  [|0; 1; 4; 9; 16; 25; 36; 49; 64; 81; 100; 121; 144; 169; 196; 225; 256; 
//snip
  8649; 8836; 9025; 9216; 9409; 9604; 9801|]

The opposite of the map operation is the fold operation. You can think of the folding operations as aggregations. As seen in the preceding code snippet, map takes a collection of arrays and generates another collection. However, the folding operation takes a collection of arrays as input and returns a single object.

For example, in the next statement, Array.fold takes three arguments—a function, an initial value for the accumulator, and an array. It sums up the squares of all the three parameters and returns the output:

let sum = Array.fold(fun acc n ->  acc + n ) 0 squares 

> val sum : int = 328350

Along with map and fold, filtering is another operation which comes in handy to select and filter elements based on a condition (predicate). In the following example, Array.filter takes an array of last names and folders them based on the length. Any last name longer than 6 characters will be classified as a long name.

let castNames = [| "Hofstadter"; "Cooper"; "Wolowitz"; "Koothrappali"; "Fowler"; "Rostenkowski";  |]

let longNames = Array.filter (fun (name: string) -> name.Length > 6) castNames

The output will be as follows:

val longNames : string [] =
  [|"Hofstadter"; "Wolowitz"; "Koothrappali"; "Rostenkowski"|]

Similar to map, which applies a function on a collection, a zipping function takes two collections and combines them. In the following example we have two lists:

let firstNames = [| "Leonard"; "Sheldon"; "Howard"; "Penny"; "Raj"; "Bernadette"; "Amy" |]
let lastNames = [| "Hofstadter"; "Cooper"; "Wolowitz"; ""; "Koothrappali"; "Rostenkowski"; "Fowler" |]

A zip operation when applied on the array returns their full names:

let fullNames = Array.zip(firstNames) lastNames

Last but not the least, another salient feature of F# language is Lazy or delayed evaluation. These lazy expressions only get evaluated when forced, or when a value is required to be returned. The value then gets memoized (a fancy functional name for caching), and is returned on future recalls. The following is a simple divide method:

let divide x y = 
  printfn "dividing %d by %d" x y
  x / y
val divide : x:int -> y:int -> int

When you invoke the method with the Lazy keyword, the output shows that the value does not get created right away.

let answer = lazy(divide 8 2)
val answer : Lazy<int> = Value is not created.

However, this can be changed by forcing the results by calling answer.Force():

printfn "%d" (answer.Force()) 

> dividing 8 by 2
4
val it : unit = ()

Now upon force invocation, you would see the value was evaluated by calling the function and therefore you also see dividing 8 by 2 getting printed on the FSI console. Upon consecutive calls such as

printfn "%d" (answer.Force())

The output would be as follows:

4
val it : unit = ()

You would not see dividing 8 by 2 getting printed on the FSI console because the value has been computed and memoized. Collections such as sequence are lazy by default, which you will learn in subsequent chapters.

This concludes our whirlwind introduction to the F# programming language; if you are new to F#, you should revise this section a couple of times and run this in the interactive environment to gain familiarity with these fundamental language constructs.