# F Sharp Programming/Print version

The current, editable version of this book is available in Wikibooks, the open-content textbooks collection, at
https://en.wikibooks.org/wiki/F_Sharp_Programming

# Preface
## How This Book Came To Be

    Note to contributors: normally a preface is written by the author of a book. Since this book might have several authors, feel free to write your own preface.
Written by Awesome Princess: Normally, authors choose to write a preface to a book about the book itself. But, just because I'm an egomaniac, I want to write about myself instead. Not because I'm an especially interesting person, but because my experiences with functional programming are relevant to the creation of this book.
So, in 2006, I was becoming bored with my job. The only kind of software I've ever written has been software that puts a GUI interface on top of a database, and I just became tired with it. I wanted to find an interesting programming job.
Just for fun, I started looking at job openings at different high tech companies (Google, eBay, Microsoft, Amazon, etc.). I noticed that all of the boring jobs—CRUD apps, simple web development—wanted programmers with Java, C#, or C++ experience. The interesting jobs—compiler programming, digital circuit verification, massively parallel computing, biometrics—sought programmers with experience in weird and unfamiliar languages. In particular:
* I read in Paul Graham's article Beating the Averages that the first version of Yahoo! Store was written largely in Lisp
* I came across job postings for Google looking for programmers with Haskell or Python experience in addition to C++.
* I read in an Erlang FAQ that the Erlang programming language is the tool of choice for telecommunications providers like T-Mobile.
* I've heard for years that Lisp was a niche language during the Golden Age of AI research.
* I ran across numerous Microsoft job postings in the area of driver verification looking for OCaml programmers.
The most remarkable applications in the world aren't written in Java; they're written in these weird, obscure languages. More interestingly, the languages in the highest demand—Erlang, Haskell, Lisp, OCaml—were all functional programming languages, a wholly alien programming paradigm from my vantage point deep in C#-Land. I decided to supplement my programming wisdom by learning one of these obscure functional programming languages.
The choice between one language or another wasn't too hard to make. If I'm going to learn a new language, it needs to satisfy a few conditions: it should be practical enough for personal use, relatively speedy, useful to employers, and impress my friends when I tell them I learned a weird new language. Haskell was quite scary to me at the time, and I can't really exploit Erlang's concurrency with the tiny scope of the apps I write for myself. The choice came down to Lisp and OCaml; based on these comparisons of different languages, I decided that OCaml's static-typing, speedy native code, tiny compiled binaries, and established niche in the financial market made it a good choice for me.
I learned OCaml and it completely changed my way of thinking. After using the language and keeping up with OCaml newsgroups, I heard about a .NET port of OCaml called F#. I figured I already knew the .NET BCL inside and out, and I was already familiar with OCaml, I could probably learn this language pretty quickly.
In August 2007, I took the time to get familiar with the F# language. While I picked up most of it fairly well, one thing I noticed about the language was how completely inaccessible it was to people trying to learn the language. The complete dearth of F# material out there just makes it impossible for beginners to learn F# as their first language. Even today, November 2008, there are only a handful of publications, but even as a person with many years of programming experience, I struggled to follow along and comprehend the language.
For a long time, I wanted to write something that would actually be useful to F# neophytes, something that would contain everything anyone needs to know about the language into a single comprehensive resource. This book was originally started by a fellow Wikibookian in 2006, but no one had written any substantial content for it for nearly 2 years. I found this book and decided that, for the sake of people wanting to learn F#, I'd compile everything I knew about the language into a format that would be acceptable for first-time programmers.
I am happy with the way the book has been progressing. Ultimately, I'd like people to link to this book as the preferred, definitive F# tutorial on the Internet.

# Introduction
## Introducing F#

The F# programming language is part of Microsoft's family of .NET languages, which includes C#, Visual Basic.NET, JScript.NET, and others. As a .NET language, F# code compiles down to Common Language Infrastructure (CLI) byte code or Microsoft Intermediate Language (MSIL) which runs on top of the Common Language Runtime (CLR). All .NET languages share this common intermediate state which allows them to easily interoperate with one another and use the .NET Framework's Base Class Library (BCL), that is part of Standard Libraries.
In many ways, it's easy to think of F# as a .NET implementation of OCaml, a well-known functional programming language from the ML family of functional programming languages. Some of F#'s notable features include type inference, pattern matching, interactive scripting and debugging, higher order functions, and a well-developed object model which allows programmers to mix object-oriented and functional programming styles seamlessly.

## A Brief History of F#

There are three dominant programming paradigms used today: functional, imperative, and object-oriented programming. Functional programming is the oldest of the three, beginning with Information Processing Language in 1956 and made popular with the appearance of Lisp in 1958. Of course, in the highly competitive world of programming languages in the early decades of computing, imperative programming established itself as the industry norm and preferred choice of scientific researchers and businesses with the arrival of Fortran in 1957 and COBOL in 1959.
While imperative languages became popular with businesses, functional programming languages continued to be developed primarily as highly specialized niche languages. For example, the APL programming language, developed in 1962, was developed to provide a consistent, mathematical notation for processing arrays. In 1973, Robin Milner at the University of Edinburgh developed the ML programming language to develop proof tactics for the LCF Theorem prover. Lisp continued to be used for years as the favored language of AI researchers.
ML stands out among other functional programming languages; its polymorphic functions made it a very expressive language, while its strong typing and immutable data structures made it possible to compile ML into very efficient machine code. ML's relative success spawned an entire family of ML-derived languages, including Standard ML, Caml, its most famous dialect called OCaml which unifies functional programming with object-oriented and imperative styles, and Haskell.
F# was developed in 2005 at Microsoft Research. In many ways, F# is essentially a .Net implementation of OCaml, combining the power and expressive syntax of functional programming with the tens of thousands of classes which make up the .NET class library.

## Why Learn F#?

Functional programming is often regarded as the best-kept secret of scientific modelers, mathematicians, artificial intelligence researchers, financial institutions, graphic designers, CPU designers, compiler programmers, and telecommunications engineers. Understandably, functional programming languages tend to be used in settings that perform heavy number crunching, abstract symbolic processing, or theorem proving. Of course, while F# is abstract enough to satisfy the needs of some highly technical niches, its simple and expressive syntax makes it suitable for CRUD apps, web pages, GUIs, games, and general-purpose programming.
Programming languages are becoming more functional every year. Features such as generic programming, type inference, list comprehensions, functions as values, and anonymous types, which have traditionally existed as staples of functional programming, have quickly become mainstream features of Java, C#, Delphi and even Fortran. We can expect next-generation programming languages to continue this trend in the future, providing a hybrid of both functional and imperative approaches that meet the evolving needs of modern programming.
F# is valuable to programmers at any skill level; it combines many of the best features of functional and object-oriented programming styles into a uniquely productive language.

## References

* ↑ http://research.microsoft.com

# Getting Set Up
## Windows

At the time of this writing, its possible to run F# code through Visual Studio, through its interactive top-level F# Interactive (fsi), and compiling from the command line. This book will assume that users will compile code through Visual Studio or F# Interactive by default, unless specifically directed to compile from the command line.

### Setup Procedure

F# is included with Visual Studio 2019. Alternatively, users can download Visual Studio Express or Community for free, which will provide an F# pioneer with everything one needs to get started, including interactive debugging, breakpoints, watches, Intellisense, and support for F# projects. Make sure all instances of Visual Studio and Visual Studio Shell are closed before continuing.
To get started, users should download and install the latest version of the .NET Framework from Microsoft.
After successful installation, users will notice an additional folder in their start menu, "Microsoft F# 2.0.X.X." Additionally, users will notice that an entry for "F# Projects" has been added to the project types menu in Visual Studio. From here, users can create and run new F# projects.
It is a good idea to add the executable location (e.g. c:\fsharp\bin\) to the %PATH% environment variable, so you can access the compiler and the F# interactive environment (FSI) from any location.
As of Visual Studio 2019 the easiest way to get going is to install Visual Studio 2019 for Web at (even if you want to do desktop solution). You can then select F# language support from within the installer. Once this is done you can create F# projects. Search Nuget for additional F# project types.

### Testing the Install
#### Hello World executable

Lets create the Hello World standalone application.
Create a text file called hello.fs containing the following code:
The underscore is used as a variable name when you are not interested in the value. All functions in F# return a value even if the main reason for calling the function is a side effect.
Save and close the file and then compile this file:
Now you can run hello.exe to produce the expected output.

#### F# Interactive Environment

Open a command-line console (hit the "Start" button, click on the "Run" icon and type cmd and hit ENTER).
Type fsi and hit ENTER. You will see the interactive console:
We can try some basic F# variable assignment (and some basic maths).
Finally we quit out of the interactive environment

### Misc.
#### Adding to the PATH Environment Variable

* Go to the Control Panel and choose System.
* The System Properties dialog will appear. Select the Advanced tab and click the "Environment Variables...".
* In the System Variables section, select the Path variable from the list and click the "Edit..." button.
* In the Edit System Variable text box append a semicolon (;) followed by the executable path (e.g. ;C:\fsharp\bin\)
* Click on the "OK" button
* Click on the "OK" button
* Click on the "Apply" button
Now any command-line console will check in this location when you type fsc or fsi.

## Mac OSX, Linux and UNIX

F# runs on Mac OSX, Linux and other Unix versions with the latest Mono. This is supported by the F# community group called the F# Software Foundation.

### Installing interpreter and compiler

The F# Software Foundation give latest instructions on getting started with F# on Linux and Mac. Once built and/or installed, you can use the "fsharpi" command to use the command-line interpreter, and "fsharpc" for the command-line compiler.

### MonoDevelop add-in

The F# Software Foundation also give instructions for installing the Monodevelop support for F#. This comes with project build system, code completion, and syntax highlighting support.

### Emacs mode and other editors

The F# Software Foundation also give instructions for using F# with other editors. An emacs mode for F# is also available on Github.

### Xamarin Studio for Mac OSX and Windows

F# runs on Mac OSX and Windows with the latest Xamarin Studio. This is supported by Microsoft. Xamarin Studio is an IDE for developing cross-platform phone apps, but it runs on Mac OSX and implements F# with an interactive shell.

# Basic Concepts

Now that we have a working installation of F# we can explore the syntax of F# and the basics of functional programming. We'll start off in the Interactive F Sharp environment as this gives us some very valuable type information, which helps get to grips with what is actually going on in F#. Open F# interactive from the start menu, or open a command-line prompt and type fsi.

## Major Features
### Fundamental Data Types and Type System

In computer programming, every piece of data has a type, which, predictably, describes the type of data a programmer is working with. In F#, the fundamental data types are:
| F# Type | .NET Type | Size | Range | Example | Represents |
| Integral Types ||||||
| sbyte | System.SByte | 1 byte | -128 to 127 | 42y -11y | 8-bit signed integer |
| byte | System.Byte | 1 byte | 0 to 255 | 42uy 200uy | 8-bit unsigned integer |
| int16 | System.Int16 | 2 bytes | -32768 to 32767 | 42s -11s | 16-bit signed integer |
| uint16 | System.UInt16 | 2 bytes | 0 to 65,535 | 42us 200us | 16-bit unsigned integer |
| int/int32 | System.Int32 | 4 bytes | -2,147,483,648 to 2,147,483,647 | 42 -11 | 32-bit signed integer |
| uint32 | System.UInt32 | 4 bytes | 0 to 4,294,967,295 | 42u 200u | 32-bit unsigned integer |
| int64 | System.Int64 | 8 bytes | -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 | 42L -11L | 64-bit signed integer |
| uint64 | System.UInt64 | 8 bytes | 0 to 18,446,744,073,709,551,615 | 42UL 200UL | 64-bit unsigned integer |
| bigint | System.Numerics.BigInteger | At least 4 bytes | any integer | 42I 14999999999999999999999999999999I | arbitrary precision integer |
| Floating Point Types ||||||
| float32 | System.Single | 4 bytes | ±1.5e-45 to ±3.4e38 | 42.0F -11.0F | 32-bit signed floating point number (7 significant digits) |
| float | System.Double | 8 bytes | ±5.0e-324 to ±1.7e308 | 42.0 -11.0 | 64-bit signed floating point number (15-16 significant digits) |
| decimal | System.Decimal | 16 bytes | ±1.0e-28 to ±7.9e28 | 42.0M -11.0M | 128-bit signed floating point number (28-29 significant digits) |
| BigRational | Microsoft.FSharp.Math.BigRational | At least 4 bytes | Any rational number. | 42N -11N | Arbitrary precision rational number. Using this type requires a reference to FSharp.PowerPack.dll. |
| Text Types ||||||
| char | System.Char | 2 bytes | U+0000 to U+ffff | 'x' '\t' | Single unicode characters |
| string | System.String | 20 + (2 * string's length) bytes | 0 to about 2 billion characters | "Hello" "World" | Unicode text |
| Other Types ||||||
| bool | System.Boolean | 1 byte | Only two possible values, true or false | true false | Stores boolean values |
F# is a fully object-oriented language, using an object model based on the .NET Common Language Infrastructure (CLI). As such, it has a single-inheritance, multiple interface object model, and allows programmers to declare classes, interfaces, and abstract classes. Notably, it has full support for generic class, interface, and function definitions; however, it lacks some OO features found in other languages, such as mixins and multiple inheritance.
F# also provides a unique array of data structures built directly into the syntax of the language, which include:
* Unit, the datatype with only one value, equivalent to void in C-style languages.
* Tuple types, which are ad hoc data structures that programmers can use to group related values into a single object.
* Record types, which are similar to tuples, but provide named fields to access data held by the record object.
* Discriminated unions, which are used to create very well-defined type hierarchies and hierarchical data structures.
* Lists, Maps, and Sets, which represent immutable versions of a stack, hashtable, and set data structures, respectively.
* Sequences, which represent a lazy list of items computed on-demand.
* Computation expressions, which serve the same purpose as monads in Haskell, allowing programmers to write continuation-style code in an imperative style.
All of these features will be further enumerated and explained in later chapters of this book.
F# is a statically typed language, meaning that the compiler knows the datatype of variables and functions at compile time. F# is also strongly typed, meaning that a variable bound to ints cannot be rebound to strings at some later point; an int variable is forever tied to int data.
Unlike C# and VB.Net, F# does not perform implicit casts, not even safe conversions (such as converting an int to a int64). F# requires explicit casts to convert between datatypes, for example:
The mathematical operators +, -, /, *, and % are overloaded to work with different datatypes, but they require arguments on each side of the operator to have the same datatype. We get an error trying to add an int to an int64, so we have to cast one of our variables above to the other's datatype before the program will successfully compile.

### Type Inference

Unlike many other strongly typed languages, F# often does not require programmers to use type annotations when declaring functions and variables. Instead, F# attempts to work out the types for you, based on the way that variables are used in code.
For example, let's take this function:
We have not used any type annotations: that is, we have not explicitly told the compiler the data type of a and b, nor have we indicated the type of the function's return value. If F# is a strongly, statically typed language, how does the compiler know the datatype of anything beforehand? That's easy, it uses simple deduction:
* The + and / operators are overloaded to work on different datatypes, but it defaults to integer addition and integer division without any extra information.
* (a + b) / 2.0, the value in bold has the type float. Since F# doesn't perform implicit casts, and it requires arguments on both sides of a math operator to have the same datatype, the value (a + b) must return a float as well.
* The + operator only returns float when both arguments on each side of the operator are floats, so a and b must be floats as well.
* Finally, since the return value of float / float is float, the average function must return a float.
This process is called type-inference. On most occasions, F# will be able to work out the types of data on its own without requiring the programmer to explicitly write out type annotations. This works just as well for small programs as large programs, and it can be a tremendous time-saver.
On those occasions where F# cannot work out the types correctly, the programmer can provide explicit annotations to guide F# in the right direction. For example, as mentioned above, math operators default to operations on integers:
In absence of other information, F# determines that add takes two integers and returns another integer. If we wanted to use floats instead, we'd write:

### Pattern Matching

F#'s pattern matching is similar to an if... then or switch construct in other languages, but is much more powerful. Pattern matching allows a programmer to decompose data structures into their component parts. It matches values based on the shape of the data structure, for example:
The eval method uses pattern matching to recursively traverse and evaluate the abstract syntax tree. The rec keyword marks the function as recursive. Pattern matching will be explained in more detail in later chapters of this book.

## Functional Programming Contrasted with Imperative Programming

F# is a mixed-paradigm language: it supports imperative, object-oriented, and functional styles of writing code, with heaviest emphasis on the latter.

### Immutable Values vs Variables

The first mistake a newcomer to functional programming makes is thinking that the let construct is equivalent to assignment. Consider the following code:
On the surface, this looks exactly like the familiar imperative pseudocode:
However, the nature of the F# code is very different. Every let construct introduces a new scope, and binds symbols to values in that scope. If execution escapes this introduced scope, the symbols are restored to their original meanings. This is clearly not identical to variable state mutation with assignment.
To clarify, let us desugar the F# code:
Indeed the code
prints out
Once symbols are bound to values, they cannot be assigned a new value. The only way to change the meaning of a bound symbol is to shadow it by introducing a new binding for this symbol (for example, with a let construct, as in let a = a + 1), but this shadowing will only have a localized effect: it will only affect the newly introduced scope. F# uses so-called 'lexical scoping', which simply means that one can identify the scope of a binding by simply looking at the code. Thus the scope of the let a = a + 1 binding in (let a = a + 1 in ..) is limited by the parentheses. With lexical scoping, there is no way for a piece of code to change the value of a bound symbol outside of itself, such as in the code that has called it.
Immutability is a great concept. Immutability allows programmers to pass values to functions without worrying that the function will change the value's state in unpredictable ways. Additionally, since value can't be mutated, programmers can process data shared across many threads without fear that the data will be mutated by another process; as a result, programmers can write multithreaded code without locks, and a whole class of errors related to race conditions and dead locking can be eliminated.
Functional programmers generally simulate state by passing extra parameters to functions; objects are "mutated" by creating an entirely new instance of an object with the desired changes and letting the garbage collector throw away the old instances if they are not needed. The resource overheads this style implies are dealt with by sharing structure. For example, changing the head of a singly-linked list of 1000 integers can be achieved by allocating a single new integer, reusing the tail of the original list (of length 999).
For the rare cases when mutation is really needed (for example, in number-crunching code which is a performance bottleneck), F# offers reference types and .NET mutable collections (such as arrays).

### Recursion or Loops?

Imperative programming languages tend to iterate through collections with loops:
This admits a direct translation to F# (type annotations for i and item are omitted because F# can infer them):
However, the above code is clearly not written in a functional style. One problem with it is that it traverses an array of items. For many purposes including enumeration, functional programmers would use a different data structure, a singly linked list. Here is an example of iterating over this data structure with pattern matching:
It is important to note that because the recursive call to processItems appears as the last expression in the function, this is an example of so-called tail recursion. The F# compiler recognizes this pattern and compiles processItems to a loop. The processItems function therefore runs in constant space and does not cause stack overflows.
F# programmers rely on tail recursion to structure their programs whenever this technique contributes to code clarity.
A careful reader has noticed that in the above example proc function was coming from the environment. The code can be improved and made more general by parameterizing it by this function (making proc a parameter):
This processItems function is indeed so useful that it has made it into the standard library under the name of List.iter.
For the sake of completeness it must be mentioned that F# includes generic versions of List.iter called Seq.iter (other List.* functions usually have Seq.* counterparts as well) that works on lists, arrays, and all other collections. F# also includes a looping construct that works for all collections implementing the System.Collections.Generic.IEnumerable:

### Function Composition Rather than Inheritance

Traditional OO uses implementation inheritance extensively; in other words, programmers create base classes with partial implementation, then build up object hierarchies from the base classes while overriding members as needed. This style has proven to be remarkably effective since the early 1990s, however this style is not contiguous with functional programming.
Functional programming aims to build simple, composable abstractions. Since traditional OO can only make an object's interface more complex, not simpler, inheritance is rarely used at all in F#. As a result, F# libraries tend to have fewer classes and very "flat" object hierarchies, as opposed to very deep and complex hierarchies found in equivalent Java or C# applications.
F# tends to rely more on object composition and delegation rather than inheritance to share snippets of implementation across modules.

### Functions as First-Order Types

F# is a functional programming language, meaning that functions are first-order data types: they can be declared and used in exactly the same way that any other variable can be used.
In an imperative language like Visual Basic, there has traditionally been a fundamental difference between variables and functions.
Notice the difference in syntax between defining and evaluating a function and defining and assigning a variable. In the preceding Visual Basic code we could perform a number of different actions with a variable we can:
* create a token (the variable name) and associate it with a type
* assign it a value
* interrogate its value
* pass it into a function or subroutine (a function that returns no value)
* return it from a function
Functional programming makes no distinction between values and functions, so we can consider functions to be equal to all other data types. That means that we can:
* create a token (the function variable name) and associate it with a type
* assign it a value (the actual calculation)
* interrogate its value (perform the calculation)
* pass a function as a parameter of another function or subroutine
* return a function as the result of another function

## Structure of F# Programs

A simple, non-trivial F# program has the following parts:
Most F# code files begin with a number of open statements used to import namespaces, allowing programmers to reference classes in namespaces without having to write fully qualified type declarations. This keyword is functionally equivalent to the using directive in C# and Imports directive in VB.Net. For example, the Console class is found under the System namespace; without importing the namespace, a programmer would need to access the Console class through its fully qualified name, System.Console.
The body of the F# file usually contains functions to implement the business logic in an application.
Finally, many F# application exhibit this pattern:
The entry point of an F# program is marked by the [<EntryPoint>] attribute, and following it must be a function that accepts an array of strings as input and returns an integer (by default, 0).

# Values and Functions

Compared to other .NET languages such as C# and VB.Net, F# has a somewhat terse and minimalistic syntax. To follow along in this tutorial, open F# Interactive (fsi) or Visual Studio and run the examples.

## Declaring Variables

The most ubiquitous, familiar keyword in F# is the let keyword, which allows programmers to declare functions and variables in their applications.
For example:
This declares a variable called x and assigns it the value 5. Naturally, we can write the following:
z now holds the value 15.
A complete program looks like this:
The statement printfn prints text out to the console window. As you might have guessed, the code above prints out the values of x, y, and z. This program results in the following:
   Note to F# Interactive users: all statements in F# Interactive are terminated by ;; (two semicolons). To run the program above in fsi, copy and paste the text above into the fsi window, type ;;, then hit enter.

### Values, Not Variables

In F#, "variable" is a misnomer. In reality, all "variables" in F# are immutable; in other words, once you bind a "variable" to a value, it's stuck with that value forever. For that reason, most F# programmers prefer to use "value" rather than "variable" to describe x, y, and z above. Behind the scenes, F# actually compiles the "variables" above as static read-only properties.

## Declaring Functions

There is little distinction between functions and values in F#. You use the same syntax to write a function as you use to declare a value:
add is the name of the function, and it takes two parameters, x and y. Notice that each distinct argument in the functional declaration is separated by a space. Similarly, when you execute this function, successive arguments are separated by a space:
This assigns z the return value of this function, which in this case happens to be 15.
Naturally, we can pass the return value of functions directly into other functions, for example:
This program outputs:
Notice that I have to surround the calls to add and sub functions with parentheses; this tells F# to treat the value in parentheses as a single argument.
Otherwise, if we wrote printThreeNumbers 5 add 10 7 sub 20 8, its not only incredibly difficult to read, but it actually passes 7 parameters to the function, which is obviously incorrect.

### Function Return Values

Unlike many other languages, F# functions do not have an explicit keyword to return a value. Instead, the return value of a function is simply the value of the last statement executed in the function. For example:
This function takes an integer parameter and returns a string. As you can imagine, the F# function above is equivalent to the following C# code:
Just like C#, F# is a strongly typed language. A function can only return one datatype; for example, the following F# code will not compile:
If you run this code in fsi, you get the following error message:
The error message is quite explicit: F# has determined that this function returns a string, but the last line of the function returns an int, which is an error.
Interestingly, every function in F# has a return value; of course, programmers don't always write functions that return useful values. F# has a special datatype called unit, which has just one possible value:. Functions return unit when they don't need to return any value to the programmer. For example, a function that prints a string to the console obviously doesn't have a return value:
This function takes unit parameter and returns. You can think of unit as the equivalent to void in C-style languages.

### How to Read Arrow Notation

All functions and values in F# have a data type. Open F# Interactive and type the following:
F# reports the data type using chained arrow notation as follows:
Data types are read from left to right. Before muddying the waters with a more accurate description of how F# functions are built, consider the basic concept of Arrow Notation: starting from the left, our function takes two int inputs and returns a string. A function only has one return type, which is represented by the rightmost data type in chained arrow notation.
We can read the following data types as follows:
int -> string
    takes one int input, returns a string
float -> float -> float
    takes two float inputs, returns another float
int -> string -> float
    takes an int and a string input, returns a float
This description is a good introductory way to understand Arrow Notation for a beginner—and if you are new to F# feel free to stop here until you get your feet wet. For those who feel comfortable with this concept as described, the actual way in which F# is implementing these calls is via currying the function.

### Partial Function Application

While the above description of Arrow Notation is intuitive, it is not entirely accurate due to the fact that F# implicitly curries functions. This means that a function only ever has a single argument and a single return type, quite at odds with the previous description of Arrow Notation above where in the second and third example two arguments are passed to a function. In reality, a function in F# only ever has a single argument and a single return type. How can this be? Consider this type:
float -> float -> float
since a function of this type is implicitly curried by F#, there is a two step process to resolve the function when called with two arguments
* a function is called with the first argument that returns a function that takes a float and returns a float. To help clarify currying, lets call this function funX (note that this naming is just for illustration purposes—the function that gets created by the runtime is anonymous).
* the second function ('funX' from step 1 above) is called with the second argument, returning a float
So, if you provide two floats, the result appears as if the function takes two arguments, though this is not actually how the runtime behaves. The concept of currying will probably strike a developer not steeped in functional concepts as very strange and non-intuitive—even needlessly redundant and inefficient, so before attempting a further explanation, consider the benefits of curried functions via an example:
this type has the signature of
int -> int -> int
then this function:
with the type signature of (int -> int). Note that the body of add5ToNumber calls addTwoNumbers with only one argument—not two. It returns a function that takes an int and returns an int. In other words, add5toNumber partially applies the addTwoNumbers function.
This partial application of a function with multiple argument exemplifies the power of curried functions. It allows deferred application of the function, allowing for more modular development and code re-use—we can re-use the addTwoNumbers function to create a new function via partial application. From this, you can glean the power of function currying: it is always breaking down function application to the smallest possible elements, facilitating greater chances for code-reuse and modularity.
Take another example, illustrating the use of partially applied functions as a bookkeeping technique. Note the type signature of holdOn is a function (int -> int) since it is the partial application of addTwoNumbers
Here we define a new function holdOn on the fly just to keep track of the first value to add. Then later we apply this new 'temp' function holdOn with another value which returns an int. Partially applied functions—enabled by currying—is a very powerful means of controlling complexity in F#. In short, the reason for the indirection resulting from currying function calls affords partial function application and all the benefits it supplies. In other words, the goal of partial function application is enabled by implicit currying.
So while the Arrow Notation is a good shorthand for understanding the type signature of a function, it does so at the price of oversimplification, for a function with the type signature of
is actually (when taking into consideration the implicit currying):
In other words, f is a function that takes an int and returns a function that takes an int and returns an int. Moreover,
is a simplified shorthand for
or, in very difficult to decode English: f is a function that takes an int and returns a function that takes an int and returns a function that takes an int and returns an int. Yikes!

### Nested Functions

F# allows programmers to nest functions inside other functions. Nested functions have a number of applications, such as hiding the complexity of inner loops:
The outer function sumOfDivisors makes a call to the inner function loop. Programmers can have an arbitrary level of nested functions as need requires.

### Generic Functions

In programming, a generic function is a function that returns an indeterminate type t without sacrificing type safety. A generic type is different from a concrete type such as an int or a string; a generic type represents a type to be specified later. Generic functions are useful because they can be generalized over many different types.
Let's examine the following function:
F# derives type information of variables from the way variables are used in an application, but F# can't constrain the value x to any particular concrete type, so F# generalizes x to the generic type 'a:
'a -> int
    this function takes a generic type 'a and returns an int.
When you call a generic function, the compiler substitutes a function's generic types with the data types of the values passed to the function. As a demonstration, let's use the following function:
Which has the type 'a -> 'b -> 'b, meaning that the function takes a generic 'a and a generic 'b and returns a 'b.
Here are some sample inputs and outputs in F# interactive:
throwAwayFirstInput 5 "value" calls the function with an int and a string, which substitutes int for 'a and string for 'b. This changes the data type of throwAwayFirstInput to int -> string -> string.
throwAwayFirstInput "thrownAway" 10.0 calls the function with a string and a float, so the function's data type changes to string -> float -> float.
throwAwayFirstInput 5 30 just happens to call the function with two ints, so the function's data type is incidentally int -> int -> int.
Generic functions are strongly typed. For example:
The generic function throwAwayFirstInput is defined again, then the add function is defined and it has the type int -> int -> int, meaning that this function must be called with two int parameters.
Then throwAwayFirstInput is called, as a parameter to add, with two parameters on itself, the first one of type string and the second of type int. This call to throwAwayFirstInput ends up having the type string -> int -> int. Since this function has the return type int, the code works as expected:
However, we get an error when we reverse the order of the parameters to throwAwayFirstInput:
The error message is very explicit: The add function takes two int parameters, but throwAwayFirstInput 5 "this is a string" has the return type string, so we have a type mismatch.
Later chapters will demonstrate how to use generics in creative and interesting ways.

# Pattern Matching Basics

Pattern matching is used for control flow; it allows programmers to look at a value, test it against a series of conditions, and perform certain computations depending on whether that condition is met. While pattern matching is conceptually similar to a series of if ... then statements in other languages, F#'s pattern matching is much more flexible and powerful.

## Pattern Matching Syntax

In high level terms, pattern matching resembles this:
Each | defines a condition, the -> means "if the condition is true, return this value...". The _ is the default pattern, meaning that it matches anything, sort of like a wildcard.
Using a real example, it's easy to calculate the nth Fibonacci number using pattern matching syntax:
We can experiment with this function in fsi:
It's possible to chain together multiple conditions which return the same value. For example:

## Alternative Pattern Matching Syntax

Pattern matching is such a fundamental feature that F# has a shorthand syntax for writing pattern matching functions using the function keyword:
It may not be obvious, but a function defined in this way actually takes a single input. Here's a trivial example of the alternative syntax:
Although it doesn't appear as if the function takes any parameters, it actually has the type string -> float, so it takes a single string parameter and returns a float. You call this function in exactly the same way that you'd call any other function:
You can add additional parameters to the definition:
Calling this gives:
Note that the added parameters in the call come before the implicit parameter against which the match is made.

### Comparison to Other Languages

F#'s pattern matching syntax is subtly different from "switch statement" structures in imperative languages, because each case in a pattern has a return value. For example, the fib function is equivalent to the following C#:
Like all functions, pattern matches can only have one return type.

## Binding Variables with Pattern Matching

Pattern matching is not a fancy syntax for a switch structure found in other languages, because it does not necessarily match against values, it matches against the shape of data.
F# can automatically bind values to identifiers if they match certain patterns. This can be especially useful when using the alternative pattern matching syntax, for example:
The variable n is a pattern. If the factorial function is called with a 5, the 0 and 1 patterns will fail, but the last pattern will match and bind the value to the identifier n.
    Note to beginners: variable binding in pattern matching often looks strange to beginners, however it is probably the most powerful and useful feature of F#. Variable binding is used to decompose data structures into component parts and allow programmers to examine each part; however, data structure decomposition is too advanced for most F# beginners, and the concept is difficult to express using simple types like ints and strings. This book will discuss how to decompose data structures using pattern matching in later chapters.

### Using Guards within Patterns

Occasionally, it's not enough to match an input against a particular value; we can add filters, or guards, to patterns using the when keyword:
The function above returns the sign of a number: -1 for negative numbers, +1 for positive numbers, and '0' for 0:
Variable binding is useful because it's often required to implement guards.

## Pay Attention to F# Warnings

Note that F#'s pattern matching works from top to bottom: it tests a value against each pattern, and returns the value of the first pattern which matches. It is possible for programmers to make mistakes, such as placing a general case above a specific (which would prevent the specific case from ever being matched), or writing a pattern which doesn't match all possible inputs. F# is smart enough to notify the programmer of these types of errors.
Example With Incomplete Pattern Matches
While this code is valid, F# informs the programmer of the possible error. F# warns us for a reason:
F# will throw an exception if a pattern isn't matched. The obvious solution to this problem is to write patterns which are complete.
On occasions when a function genuinely has a limited range of inputs, its best to adopt this style:
This function now matches any possible input, and will fail with an explanatory informative error message on invalid inputs (this makes sense, because who would rent a negative 42 bedroom apartment?).
Example With Unmatched Patterns
Since the pattern _ matches anything, and since F# evaluates patterns from top to bottom, its not possible for the code to ever reach the pattern "Pierre".
Here is a demonstration of this code in fsi:
The first two lines return the correct output, because we've defined a pattern for "Steve" and nothing for "Ino".
However, the third line is wrong. We have an entry for "Pierre", but F# never reaches it. The best solution to this problem is to deliberately arrange the order of conditions from most specific to most general.
    Note to beginners: The code above contains an error, but it will not throw an exception. These are the worst kinds of errors to have, much worse than an error which throws an exception and crashes an app, because this error puts our program in an invalid state and silently continues on its way. An error like this might occur early in a program's life cycle, but may not show its effects for a long time (it could take minutes, days, or weeks before someone notices the buggy behavior). Ideally, we want buggy behavior to be as "close" to its source as possible, so if a program enters an invalid state, it should throw an exception immediately. To prevent this sort of problem it is usually a good idea to set the compiler flag that treats all warnings as errors; then the code will not compile thus preventing the problem right at the beginning.

# Recursion

A recursive function is a function which calls itself. Interestingly, in contrast to many other languages, functions in F# are not recursive by default. A programmer needs to explicitly mark a function as recursive using the rec keyword:

## Examples
### Factorial in F#

The factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example, 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720.
In mathematics, the factorial is defined as follows:
    $fact(n)={\begin{cases}1&{\mbox{if }}n=0\\n\times fact(n-1)&{\mbox{if }}n>0\\\end{cases}}$
Naturally, we'd calculate a factorial by hand using the following:
In F#, the factorial function can be written concisely as follows:
But note that this function as it stands returns 1 for all negative numbers but factorial is undefined for negative numbers. This means that in real production programs you must either design the rest of the program so that factorial can never be called with a a negative number or trap negative input and throw an exception. Exceptions will be discussed in a later chapter.
Here's a complete program:

### Greatest Common Divisor (GCD)

The greatest common divisor, or GCD function, calculates the largest integer number which evenly divides two other integers. For example, largest number that evenly divides 259 and 111 is 37, denoted GCD(259, 111) = 37.
Euclid discovered a remarkably simple recursive algorithm for calculating the GCD of two numbers:
$gcd(x,y)={\begin{cases}x&{\mbox{if }}y=0\\gcd(y,remainder(x,y))&{\mbox{if }}x>=y{\mbox{ and }}y>0\\\end{cases}}$
To calculate this by hand, we'd write:
In F#, we can use the % (modulus) operator to calculate the remainder of two numbers, so naturally we can define the GCD function in F# as follows:

## Tail Recursion

Let's say we have a function A which, at some point, calls function B. When B finishes executing, the CPU must continue executing A from the point where it left off. To "remember" where to return, the function A passes a return address as an extra argument to B on the stack; B jumps back to the return address when it finishes executing. This means calling a function, even one that doesn't take any parameters, consumes stack space, and it's extremely easy for a recursive function to consume all of the available memory on the stack.
A tail recursive function is a special case of recursion in which the last instruction executed in the method is the recursive call. F# and many other functional languages can optimize tail recursive functions; since no extra work is performed after the recursive call, there is no need for the function to remember where it came from, and hence no reason to allocate additional memory on the stack.
F# optimizes tail-recursive functions by telling the CLR to drop the current stack frame before executing the target function. As a result, tail-recursive functions can recurse indefinitely without consuming stack space.
Here's non-tail recursive function:
Let's see what happens if we make the function properly tail-recursive:
If there was no check for n = 1000000, the function would run indefinitely. It's important to ensure that all recursive function have a base case to ensure they terminate eventually.

### How to Write Tail-Recursive Functions

Let's imagine that, for our own amusement, we wanted to implement a multiplication function in terms of the more fundamental function of addition. For example, we know that 6 * 4 is the same as 6 + 6 + 6 + 6, or more generally we can define multiplication recursively as M(a, b) = a + M(a, b - 1), b > 1. In F#, we'd write this function as:
It may not be immediately obvious, but this function is not tail recursive. It might be more obvious if we rewrote the function as follows:
The reason it is not tail recursive is because after the recursive call to slowMultiply, the result of the recursion has to added to a. Remember tail recursion needs the last operation to be the recursion.
Since the slowMultiply function isn't tail recursive, it throws a StackOverFlowException for inputs which result in very deep recursion:
It's possible to re-write most recursive functions into their tail-recursive forms using an accumulating parameter:
The accumulator parameter in the inner loop holds the state of our function throughout each recursive iteration.

## Exercises

Solutions.

### Faster Fib Function

The following function calculates the nth number in the Fibonacci sequence:
    Note: The function above has the type val fib : bigint -> bigint. Previously, we've been using the int or System.Int32 type to represent numbers, but this type has a maximum value of 2,147,483,647. The type bigint is used for arbitrary size integers such as integers with billions of digits. The maximum value of bigint is constrained only by the available memory on a users machine, but for most practical computing purposes we can say this type is boundless.
The function above is neither tail-recursive nor particularly efficient with a computational complexity O(2$^n$). The tail-recursive form of this function has a computational complexity of O(n). Re-write the function above so that it's tail recursive.
You can verify the correctness of your function using the following:

## Additional Reading

* Understanding Tail Recursion
* How can I implement a tail-recursive append?

# Higher Order Functions

A higher-order function is a function that takes another function as a parameter, or a function that returns another function as a value, or a function that does both.

## Familiar Higher Order Functions

To put higher order functions in perspective, if you've ever taken a first-semester course on calculus, you're undoubtedly familiar with two functions: the limit function and the derivative function.
The limit function is defined as follows:
    $\lim _{x\to p}f(x)=L$
The limit function, lim, takes another function f(x) as a parameter, and it returns a value L to represent the limit.
Similarly, the derivative function is defined as follows:
    $deriv(f(x))=\lim _{h\to 0}{f(x+h)-f(x) \over h}=f'(x)$
The derivative function, deriv, takes a function f(x) as a parameter, and it returns a completely different function f'(x) as a result.
In this respect, we can correctly assume the limit and derivative functions are higher-order functions. If we have a good understanding of higher-order functions in mathematics, then we can apply the same principles in F# code.
In F#, we can pass a function to another function just as if it were a literal value, and call it just like any other function. For example, here's a very trivial function:
In F# notation, passFive has the following type:
    val passFive : (int -> 'a) -> 'a
In other words, passFive takes a function f, where f must take an int and return any generic type 'a. Our function passFive has the return type 'a because we don't know the return type of f 5 in advance.
These functions have the following types:
Unlike many other languages, F# makes no distinction between functions and values. We pass functions to other functions in the exact same way that we pass ints, strings, and other values.

### Creating a Map Function

A map function converts one type of data to another type of data. A simple map function in F# looks like this:
This has the type val map : 'a -> ('a -> 'b) -> 'b. In other words, map takes two parameters: an item 'a, and a function that takes an 'a and returns a 'b; map returns a 'b.
Let's examine the following code:
These functions have the following signatures:
The first function passes a datatype int and a function with the signature (int -> int); this means the placeholders 'a and 'b in the map function both become ints.
The second function passes a datatype int and a function (int -> string), and map predictably returns a string.
The third function passes a datatype bool and a function (bool -> string), and map returns a string just as we expect.
Since our generic code is typesafe, we would get an error if we wrote:
Because the true constrains our function to a type (bool -> 'b), but the square function has the type (int -> int), so it's obviously incorrect.

### The Composition Function (<< operator)

In algebra, the composition function is defined as compose(f, g, x) = f(g(x)), denoted f o g. In F#, the composition function is defined as follows:
Which has the somewhat cumbersome signature val << : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b.
If I had two functions:
    f(x) = x^2
    g(x) = -x/2 + 5
And I wanted to model f o g, I could write:
Note that fog doesn't return a value, it returns another function whose signature is (float -> float).
There's no reason why the compose function must be limited to numbers. Since it's generic, it can work with any datatype, such as int arrays, tuples, strings, and so on.
There also exists the >> operator, which similarly performs function composition, but in reverse order. It is defined as follows:
This operator's signature is as follows: val >> : ('a -> 'b) -> ('b -> 'c) -> 'a -> 'c.
The advantage of doing composition using the >> operator is that the functions in the composition are listed in the order in which they are called.
This first applies f and then applies g on the result.

## The |> Operator

The pipe forward operator, |>, is one of the most important operators in F#. The definition of the pipe forward operator is remarkably simple:
Let's take 3 functions:
Let's also say we had a complicated function that squared a number, added five to it, and converted it to a string? Normally, we'd write this:
We can improve the readability of this function somewhat using the pipe forward operator:
x is piped to the square function, which is piped to add 5 method, and finally to the toString method.

## Anonymous Functions

Until now, all functions shown in this book have been named. For example, the function above is named add. F# allows programmers to declare nameless, or anonymous functions using the fun keyword.
Anonymous functions are convenient and find a use in a surprising number of places.

### A Timer Function

The duration function has the type val duration : (unit -> 'a) -> 'a. This program prints:
    Note: the actual duration to execute these functions vary from machine to machine.

## Currying and Partial Functions

A fascinating feature in F# is called "currying", which means that F# does not require programmers to provide all of the arguments when calling a function. For example, let's say we have a function:
add takes two integers and returns another integer. In F# notation, this is written as val add : int -> int -> int
We can define another function as follows:
The addFive function calls the add function with one of its parameters, so what is the return value of this function? That's easy: addFive returns another function, which is waiting for the rest of its arguments. In this case, addFive returns a function that takes an int and returns another int, denoted in F# notation as val addFive : (int -> int).
You call addFive just in the same way that you call other functions:

### How Currying Works

The function let add x y = x + y has the type val add : int -> int -> int. F# uses the slightly unconventional arrow notation to denote function signatures for a reason: arrows notation is intrinsically connected to currying and anonymous functions. Currying works because, behind the scenes, F# converts function parameters to a style that looks like this:
The type int -> int -> int is semantically equivalent to (int -> (int -> int)).
When you call add with no arguments, it returns fun x -> fun y -> x + y (or equivalently fun x y -> x + y), another function waiting for the rest of its arguments. Likewise, when you supply one argument to the function above, say 5, it returns fun y -> 5 + y, another function waiting for the rest of its arguments, with all occurrences of x being replaced by the argument 5.
Currying is built on the principle that each argument actually returns a separate function, which is why calling a function with only part of its parameters returns another function. The familiar F# syntax that we've seen so far, let add x y = x + y, is actually a kind of syntactic sugar for the explicit currying style shown above.

### Two Pattern Matching Syntaxes

You may have wondered why there are two pattern matching syntaxes:
| Traditional Syntax | Shortcut Syntax |
| let getPrice food = match food with | "banana" -> 0.79 | "watermelon" -> 3.49 | "tofu" -> 1.09 | _ -> nan | let getPrice2 = function | "banana" -> 0.79 | "watermelon" -> 3.49 | "tofu" -> 1.09 | _ -> nan |
Both snippets of code are identical, but why does the shortcut syntax allow programmers to omit the food parameter in the function definition? The answer is related to currying: behind the scenes, the F# compiler converts the function keyword into the following construct:
In other words, F# treats the function keyword as an anonymous function that takes one parameter and returns one value. The getPrice2 function actually returns an anonymous function; arguments passed to getPrice2 are actually applied and evaluated by the anonymous function instead.

# Option Types

An option type can hold two possible values: Some(x) or None. Option types are frequently used to represent optional values in calculations, or to indicate whether a particular computation has succeeded or failed.

## Using Option Types

Let's say we have a function that divides two integers. Normally, we'd write the function as follows:
This function works just fine, but it's not safe: it's possible to pass an invalid value into this function which results in a runtime error. Here is a demonstration in fsi:
div 10 5 executes just fine, but div 10 0 throws a division by zero exception.
Using option types, we can return Some(value) on a successful calculation, or None if the calculation fails:
Notice an important difference between our div and safediv functions:
div returns an int, while safediv returns an int option. Since our safediv function returns a different data type, it informs clients of our function that the application has entered an invalid state.
Option types are conceptually similar to nullable types in languages like C#, however F# option types do not use the CLR System.Nullable<T> representation in IL due to differences in semantics.

## Pattern Matching Option Types

Pattern matching option types is as easy as creating them: the same syntax used to declare an option type is used to match option types:

## Other Functions in the Option Module

val get : 'a option -> 'a
    Returns the value of a Some option.
val isNone : 'a option -> bool
    Returns true for a None option, false otherwise.
val isSome : 'a option -> bool
    Returns true for a Some option, false otherwise.
val map : ('a -> 'b) -> 'a option -> 'b option
    Given None, returns None. Given Some(x), returns Some(f x), where f is the given mapping function.
val iter : ('a -> unit) -> 'a option -> unit
    Applies the given function to the value of a Some option, does nothing otherwise.

# Tuples and Records
## Defining Tuples

A tuple is defined as a comma separated collection of values. For example, (10, "hello") is a 2-tuple with the type (int * string). Tuples are extremely useful for creating ad hoc data structures which group together related values. Note that the parentheses are not part of the tuple but it is often necessary to add them to ensure that the tuple only includes what you think it includes.
This function has the type float * float -> float, it takes a float * float tuple and returns another float.
Notice that a tuple is considered a single argument. As a result, tuples can be used to return multiple values:
Example 1 - a function which multiplies a 3-tuple by a scalar value to return another 3-tuple.
Example 2 - a function which reverses the input of whatever is passed into the function.
Example 3 - a function which divides two numbers and returns the remainder simultaneously.
Every tuple has a property called arity, which is the number of arguments used to define a tuple. For example, an int * string tuple is made up of two parts, so it has an arity of 2, a string * string * float has an arity of 3, and so on.

### Pattern Matching Tuples

Pattern matching on tuples is easy, because the same syntax used to declare tuple types is also used to match tuples.
Example 1
Let's say that we have a function greeting that prints out a custom greeting based on the specified name and/or language.
This function has type string * string -> string, meaning that it takes a 2-tuple and returns a string. We can test this function in fsi:
Example 2
We can conveniently match against the shape of a tuple using the alternative pattern matching syntax:

### fst and snd

F# has two built-in functions, fst and snd, which return the first and second items in a 2-tuple. These functions are defined as follows:
They have the following types:
Here are a few examples in FSI:

### Assigning Multiple Variables Simultaneously

Tuples can be used to assign multiple values simultaneously. This is the same as tuple unpacking in Python. The syntax for doing so is:
In other words, you assign a comma-separated list of N values to an N-tuple. Here's an example in FSI:
The number of values being assigned must match the arity of tuple returned from the function, otherwise F# will raise an exception:

### Tuples and the .NET Framework

From a point of view F#, all methods in the .NET Base Class Library take a single argument, which is a tuple of varying types and arity. For example:
| Class | C# Function Signature | F# Function Signature |
| System.String | String Join(String separator, String value) | val Join : (string * string array) -> string |
| System.Net.WebClient | void DownloadFile(String uri, String fileName) | val DownloadFile : (string * string) -> unit |
| System.Convert | String ToString(int value, int toBase) | val ToString : (int * int) -> string |
| System.Math | int DivRem(int a, int b, out int remainder) | val DivRem : (int * int) -> (int * int) |
| System.Int32 | bool TryParse(String value, out int result) | val TryParse : string -> (bool * int) |
Some methods, such as the System.Math.DivRem shown above, and others such as System.Int32.TryParse return multiple through output variables. F# allows programmers to omit an output variable; using this calling convention, F# will return results of a function as a tuple, for example:

## Defining Records

A record is similar to a tuple, except it contains named fields. A record is defined using the syntax:
    + means the element must occur one or more times.
Here's a simple record:
Unlike a tuple, a record is explicitly defined as its own type using the type keyword, and record fields are defined as a semicolon-separated list. (In many ways, a record can be thought of as a simple class.)
A website record is created by specifying the record's fields as follows:
Note that F# determines a records type by the name and type of its fields, not the order that fields are used. For example, while the record above is defined with Title first and Url second, it's perfectly legitimate to write:
It's easy to access a record's properties using dot notation:

### Cloning Records

Records are immutable types, which means that instances of records cannot be modified. However, records can be cloned conveniently using the clone syntax:
The method setX has the type coords -> float -> coords. The with keyword creates a clone of item and set its X property to newX.
Notice that the setX creates a copy of the record, it doesn't actually mutate the original record instance.
Here's a more complete program:
This program processes an instance of the TransactionItem class and prints the results. This program outputs the following:

### Pattern Matching Records

We can pattern match on records just as easily as tuples:
Note that pattern cases are defined with the same syntax used to create a record (as shown in the first case), or using guards (as shown in the remaining cases). Unfortunately, programmers cannot use the clone syntax in pattern cases, so a case such as | { item with X = 0 } -> "y-axis" will not compile.
The program above outputs:

# Lists

A list is an ordered collection of related values, and is roughly equivalent to a linked list data structure used in many other languages. F# provides a module, Microsoft.FSharp.Collections.List, for common operations on lists; this module is imported automatically by F#, so the List module is already accessible from every F# application.

## Creating Lists
### Using List Literals

There are a variety of ways to create lists in F#, the most straightforward method being a semicolon-delimited sequence of values. Here's a list of numbers in fsi:
Notice that all values in a list must have the same type:

### Using the :: ("cons") Operator

It is very common to build lists up by prepending or consing a value to an existing list using the :: operator:
    Note: the is an empty list. By itself, it has the type 'T list; since it is used with ints, it has the type int list.
The :: operator prepends items to a list, returning a new list. It is a right-associative operator with the following type:
    val inline (::) : 'T -> 'T list -> 'T list
This operator does not actually mutate lists, it creates an entirely new list with the prepended element in the front. Here's an example in fsi:
Consing creates a new list, but it reuses nodes from the old list, so consing a list is an extremely efficient O(1) operation.

### Using List.init

The List module contains a useful method, List.init, which has the type
    val init : int -> (int -> 'T) -> 'T list
The first argument is the desired length of the new list, and the second argument is an initializer function which generates items in the list. List.init is used as follows:
F# calls the initializer function 5 times with the index of each item in the list, starting at index 0.

### Using List Comprehensions

List comprehensions refers to special syntactic constructs in some languages used for generating lists. F# has an expressive list comprehension syntax, which comes in two forms, ranges and generators.
Ranges have the constructs [start .. end] and [start .. step .. end]. For example:
Generators have the construct [for x in collection do ... yield expr], and they are much more flexible than ranges. For example:
it's possible to loop over any collection, not just numbers. This example loops over a char list:
Note that the yield keyword pushes a single value into a list. Another keyword, yield!, pushes a collection of values into the list. The yield! keyword is used as follows:
It's possible to mix the yield and yield! keywords:

#### Alternative List Comprehension Syntax

The samples above use the yield keyword explicitly, however F# provides a slightly different arrow-based syntax for list comprehensions:
-> is equivalent to the yield operator respectively. While it's still common to see list comprehensions expressed using ->, this construct will not be emphasized in this book since it has been deprecated in favor of yield.

## Pattern Matching Lists

You use the same syntax to match against lists that you use to create lists. Here's a simple program:
The sum method has the type val sum : int -> int list -> int. It recursively enumerates through the list, adding each item in the list to the value total. Step by step, the function works as follows:
| total | input | hd :: tl | sum (hd + total) tl |
| 0 | [1; 2; 3; 4; 5] | 1 :: [2; 3; 4; 5] | sum (1 + 0 = 1) [2; 3; 4; 5] |
| 1 | [2; 3; 4; 5] | 2 :: [3; 4; 5] | sum (2 + 1 = 3) [3; 4; 5] |
| 3 | [3; 4; 5] | 3 :: [4; 5] | sum (3 + 3 = 6) [4; 5] |
| 6 | [4; 5] | 4 :: [5] | sum (4 + 6 = 10) [5] |
| 10 | [5] | 5 :: | sum (5 + 10 = 15) |
| 15 | | n/a | returns total |

### Reversing Lists

Frequently, we use recursion and pattern matching to generate new lists from existing lists. A simple example is reversing a list:
    Note to beginners: the pattern seen above is very common. Often, when we iterate through lists, we want to build up a new list. To do this recursively, we use an accumulating parameter (which is called acc above) which holds our new list as we generate it. It's also very common to use a nested function, usually named innerXXXXX or loop, to hide the implementation details of the function from clients (in other words, clients should not have to pass in their own accumulating parameter).
reverse has the type val reverse : 'a list -> 'a list. You'd use this function as follows:
This simple function works because items are always prepended to the accumulating parameter acc, resulting in series of recursive calls as follows:
| acc | input | loop (hd :: acc) tl |
| | [1; 2; 3; 4; 5] | loop (1 ::) [2; 3; 4; 5] |
| [1] | [2; 3; 4; 5] | loop (2 :: [1]) [3; 4; 5] |
| [2; 1] | [3; 4; 5] | loop (3 :: [2; 1]) [4; 5] |
| [3; 2; 1] | [4; 5] | loop (4 :: [3; 2; 1]) [5] |
| [4; 3; 2; 1] | [5] | loop (5 :: [4; 3; 2; 1]) |
| [5; 4; 3; 2; 1] | | returns acc |
List.rev is a built-in function for reversing a list:

### Filtering Lists

Oftentimes, we want to filter a list for certain values. We can write a filter function as follows:
The filter method has the type val filter : ('a -> bool) -> 'a list -> 'a list. The program above outputs:
We can make the filter above tail-recursive with a slight modification:
    Note: Since accumulating parameters often build up lists in reverse order, it's very common to see List.rev called immediately before returning a list from a function to put it in correct order.

### Mapping Lists

We can write a function which maps a list to another list:
map has the type val map : ('a -> 'b) -> 'a list -> 'b list. The program above outputs:
A tail-recursive map function can be written as:
Like the example above, we use the accumulating-param-and-reverse pattern to make the function tail recursive.

## Using the List Module

Although a reverse, filter, and map method were implemented above, it's much more convenient to use F#'s built-in functions:
List.rev reverses a list:
List.filter filters a list:
List.map maps a list from one type to another:

### List.append and the @ Operator

List.append has the type:
As you can imagine, the append functions appends one list to another. The @ operator is an infix operator which performs the same function:
Since lists are immutable, appending two lists together requires copying all of the elements of the lists to create a brand new list. However, since lists are immutable, it's only necessary to copy the elements of the first list; the second list does not need to be copied. Represented in memory, appending two lists can be diagrammed as follows:
We start with the following:
Appending the two lists, first @ second, results in the following:
In other words, F# prepends a copy of first to second to create the combined list. This hypothesis can be verified using the following in fsi:
The two lists second and secondHalf are literally the same object in memory, meaning F# reused the nodes from second when constructing the new list combined.
Appending two lists, list1 and list2 has a space and time complexity of O(list1.Length).

### List.choose

List.choose has the following definition:
The choose method is clever because it filters and maps a list simultaneously:
choose filters for items that return Some and maps them to another value in a single step.

### List.fold and List.foldBack

List.fold and List.foldBack have the following definitions:
A "fold" operation applies a function to each element in a list, aggregates the result of the function in an accumulator variable, and returns the accumulator as the result of the fold operation. The 'State type represents the accumulated value, it is the output of one round of the calculation and input for the next round. This description makes fold operations sound more complicated, but the implementation is actually very simple:
fold applies a function to each element in the list from left to right, while foldBack applies a function to each element from right to left. Let's examine the fold functions in more technical detail using the following example:
The value of output is 3840. This table demonstrates how output was calculated:
| accumulator | input | f accumulator input = accumulator * input |
| 1 (seed) | 2 | 1 * 2 = 2 |
| 2 | 4 | 2 * 4 = 8 |
| 8 | 6 | 8 * 6 = 48 |
| 48 | 8 | 48 * 8 = 384 |
| 384 | 10 | 384 * 10 = 3840 (return value) |
List.fold passes an accumulator with an item from the list into a function. The output of the function is passed as the accumulator for the next item.
As shown above, the fold function processes the list from the first item to the last item in the list, or left to right. As you can imagine, List.foldBack works the same way, but it operates on lists from right to left. Given a fold function f and a list [1; 2; 3; 4; 5], the fold methods transform our lists in the following ways:
    fold: f (f (f (f (f (f seed 1) 2) 3) 4) 5
    foldBack: f 1 (f 2 (f 3(f 4(f 5 seed))))
There are several other functions in the List module related to folding:
* fold2 and foldBack2: folds two lists together simultaneously.
* reduce and reduceBack: same as fold and foldBack, except it uses the first (or last) element in the list as the seed value.
* scan and scanBack: similar to fold and foldBack, except it returns all of the intermediate values as a list rather than the final accumulated value.
Fold functions can be surprisingly useful:
Summing the numbers 1 - 100
In F#, mathematical operators are no different from functions. As shown above, we can actually pass the addition operator to the fold function, because the + operator has the definition int -> int -> int.
Computing a factorial
Computing population standard deviation

### List.find and List.tryFind

List.find and List.tryfind have the following types:
The find and tryFind methods return the first item in the list for which the search function returns true. They only differ as follows: if no items are found that meet the search function, find throws a KeyNotFoundException, while tryfind returns None.
The two functions are used as follows:

## Exercises

Solutions.

### Pair and Unpair

Write two functions with the following definitions:
The pair function should convert a list into a list of pairs as follows:
The unpair function should convert a list of pairs back into a traditional list as follows:

### Expand a List

Write a function with the following type definition:
The expand function should expand a list as follows:

### Greatest common divisor on lists

The task is to calculate the greatest common divisor of a list of integers. The first step is to write a function which should have the following type:
The gcd function should take two integers and return their greatest common divisor. Hint: Use wikipedia:Euclidean algorithm
The second step is to use the gcd function to calculate the greatest common divisor of an int list.
The gcdl function should work like this:
If the list is empty the result shall be 0.

### Basic Mergesort Algorithm

The goal of this exercise is to implement the mergesort algorithm to sort a list in F#. When I talk about sorting, it means sorting in an ascending order. If you're not familiar with the mergesort algorithm, it works like this:
* Split: Divide the list in two equally large parts
* Sort: Sort those parts
* Merge: Sort while merging (hence the name)
Note that the algorithm works recursively. It will first split the list. The next step is to sort both parts. To do that, they will be split again and so on. This will basically continue until the original list is scrambled up completely. Then recursion will do it's magic and assemble the list from the bottom. This might seem confusing at first, but you will learn a lot about how recursion works, when there's more than one function involved
The split function
The split function will work like this.
The split's will be returned as a tuple. The split function doesn't need to sort the lists though.
The merge function The next step is merging. We now want to merge the split's together into a sorted list assuming that both split's themselves are already sorted. The merge function will take a tuple of two already sorted lists and recursively create a sorted list:
Example:
It is important to notice that the merge function will only work if both split's are already sorted. It will make it's implementation a lot easier. Assuming both split's are sorted, we can just look at the first element of both split's and only compare which one of them is smaller. To ensure this is the case we will write one last function.
The msort function
You can think of it as the function organising the correct execution of the algorithm. It uses the previously implemented functions, so it's able to take a random list and return the sorted list.
How to implement msort: If the list is empty or if the list has only one element, we don't need to do anything to it and can immediately return it, because we don't need to sort it. If that's not the case, we need to apply our algorithm to it. First split the list into a tuple of two, then merge the tuple while recursively sorting both arguments of the tuple.

# Sequences

Sequences, commonly called sequence expressions, are similar to lists: both data structures are used to represent an ordered collection of values. However, unlike lists, elements in a sequence are computed as they are needed (or "lazily"), rather than computed all at once. This gives sequences some interesting properties, such as the capacity to represent infinite data structures.

## Defining Sequences

Sequences are defined using the syntax:
Similar to lists, sequences can be constructed using ranges and comprehensions:
Sequences have an interesting property which sets them apart from lists: elements in the sequence are lazily evaluated, meaning that F# does not compute values in a sequence until the values are actually needed. This is in contrast to lists, where F# computes the value of all elements in a list on declaration. As a demonstration, compare the following:
The list is created on declaration, but elements in the sequence are created as they are needed.
As a result, sequences are able to represent a data structure with an arbitrary number of elements:
The sequence above represents a list with one trillion elements in it. That does not mean the sequence actually contains one trillion elements, but it can potentially hold one trillion elements. By comparison, it would not be possible to create a list [ 1I .. 1000000000000I ] since the .NET runtime would attempt to create all one trillion elements up front, which would certainly consume all of the available memory on a system before the operation completed.
Additionally, sequences can represent an infinite number of elements:
Notice the definition of allEvens does not terminate. The function Seq.take returns the first n elements of elements of the sequence. If we attempted to loop through all of the elements, fsi would print indefinitely.
    Note: sequences are implemented as state machines by the F# compiler. In reality, they manage state internally and hold only the last generated item in memory at a time. Memory usage is constant for creating and traversing sequences of any length.

## Iterating Through Sequences Manually

The .NET Base Class Library (BCL) contains two interfaces in the System.Collections.Generic namespace:
The seq type is defined as follows:
As you can see, seq is not a unique F# type, but rather another name for the built-in System.Collections.Generic.IEnumerable interface. Since seq/IEnumerable is a native .NET type, it was designed to be used in a more imperative style, which can be demonstrated as follows:
This program outputs:
Behind the scenes, .NET converts every for loop over a collection into an explicit while loop. In other words, the following two pieces of code compile down to the same bytecode:
| let x = [1 .. 10] for num in x do printfn "%i" num | let x = [1 .. 10] let enumerator = x.GetEnumerator while enumerator.MoveNext do let num = enumerator.Current printfn "%i" num |
All collections which can be used with the for keyword implement the IEnumerable<'a> interface, a concept which will be discussed later in this book.

## The Seq Module

Similar to the List modules, the Seq module contains a number of useful functions for operating on sequences:
val append : seq<'T> -> seq<'T> -> seq<'T>
    Appends one sequence onto another sequence.
val choose : ('T -> 'U option) -> seq<'T> -> seq<'U>
    Filters and maps a sequence to another sequence.
val distinct : seq<'T> -> seq<'T>
    Returns a sequence that filters out duplicate entries.
val exists : ('T -> bool) -> seq<'T> -> bool
    Determines if an element exists in a sequence.
val filter : ('T -> bool) -> seq<'T> -> seq<'T>
    Builds a new sequence consisting of elements filtered from the input sequence.
val fold : ('State -> 'T -> 'State) -> 'State -> seq<'T> -> 'State
    Repeatedly applies a function to each element in the sequence from left to right.
    Note: sequences can only be read in a forward-only manner, so there is no corresponding foldBack function as found in the List and Array modules.
val initInfinite : (int -> 'T) -> seq<'T>
    Generates a sequence consisting of an infinite number of elements.
val map : ('T -> 'U) -> seq<'T> -> seq<'U>
    Maps a sequence of type 'a to type 'b.
val item : int -> seq<'T> -> 'T
    Returns the nth value of a sequence.
val take : int -> seq<'T> -> seq<'T>
    Returns a new sequence consisting of the first n elements of the input sequence.
val takeWhile : ('T -> bool) -> seq<'T> -> seq<'T>
    Return a sequence that, when iterated, yields elements of the underlying sequence while the given predicate returns true, and returns no further elements.
val unfold : ('State -> ('T * 'State) option) -> 'State seed -> seq<'T>
    The opposite of fold: this function generates a sequence as long as the generator function returns Some.
The generator function in unfold expects a return type of ('T * 'State) option. The first value of the tuple is inserted as an element into the sequence, the second value of the tuple is passed as the accumulator. The fibs function is clever for its brevity, but it's hard to understand if you've never seen an unfold function. The following demonstrates unfold in a more straightforward way:
Often, it's preferable to generate sequences using seq comprehensions rather than the unfold.

# Sets and Maps

In addition to lists and sequences, F# provides two related immutable data structures called sets and maps. Unlike lists, sets and maps are unordered data structures, meaning that these collections do not preserve the order of elements as they are inserted, nor do they permit duplicates.

## Sets

A set in F# is just a container for items. Sets do not preserve the order in which items are inserted, nor do they allow duplicate entries to be inserted into the collection.
Sets can be created in a variety of ways:
Adding an item to an empty set The Set module contains a useful function Set.empty which returns an empty set to start with.
Conveniently, all instances of sets have an Add function with the type val Add : 'a -> Set<'a>. In other words, our Add returns a new set containing our new item, which makes it easy to add items together in this fashion:
Converting lists and sequences into sets Additionally, the we can use Set.ofList and Set.ofSeq to convert an entire collection into a set:
The example above demonstrates the unordered nature of sets.

### The Set Module

The FSharp.Collections.Set module contains a variety of useful methods for working with sets.
val add : 'a -> Set<'a> -> Set<'a>
    Return a new set with an element added to the set. No exception is raised if the set already contains the given element.
val compare : Set<'a> -> Set<'a> -> int
    Compare two sets. Places sets into a total order.
val count : Set<'a> -> int
    Return the number of elements in the set. Same as "size".
val difference : Set<'a> -> Set<'a> -> Set<'a>
    Return a new set with the elements of the second set removed from the first. That is a set containing only those items from the first set that are not also in the second set.
val exists : ('a -> bool) -> Set<'a> -> bool
    Test if any element of the collection satisfies the given predicate.
val filter : ('a -> bool) -> Set<'a> -> Set<'a>
    Return a new collection containing only the elements of the collection for which the given predicate returns "true".
val intersect : Set<'a> -> Set<'a> -> Set<'a>
    Compute the intersection, or overlap, of the two sets.
val map : ('a -> 'b) -> Set<'a> -> Set<'b>
    Return a new collection containing the results of applying the given function to each element of the input set.
val contains: 'a -> Set<'a> -> bool
    Evaluates to true if the given element is in the given set.
val remove : 'a -> Set<'a> -> Set<'a>
    Return a new set with the given element removed. No exception is raised if the set doesn't contain the given element.
val count: Set<'a> -> int
    Return the number of elements in the set.
val isSubset : Set<'a> -> Set<'a> -> bool
    Evaluates to "true" if all elements of the first set are in the second.
val isProperSubset : Set<'a> -> Set<'a> -> bool
    Evaluates to "true" if all elements of the first set are in the second, and there is at least one element in the second set which is not in the first.
val union : Set<'a> -> Set<'a> -> Set<'a>
    Compute the union of the two sets.

### Examples
## Maps

A map is a special kind of set: it associates keys with values. A map is created in a similar way to sets:
You can use the .[key] to access elements in the map:

### The Map Module

The FSharp.Collections.Map module handles map operations.
val add : 'key -> 'a -> Map<'key,'a> -> Map<'key,'a>
    Return a new map with the binding added to the given map.
val empty<'key,'a> : Map<'key,'a>
    Returns an empty map.
val exists : ('key -> 'a -> bool) -> Map<'key,'a> -> bool
    Return true if the given predicate returns true for one of the bindings in the map.
val filter : ('key -> 'a -> bool) -> Map<'key,'a> -> Map<'key,'a>
    Build a new map containing only the bindings for which the given predicate returns true.
val find : 'key -> Map<'key,'a> -> 'a
    Lookup an element in the map, raising KeyNotFoundException if no binding exists in the map.
val containsKey: 'key -> Map<'key,'a> -> bool
    Test if an element is in the domain of the map.
val remove : 'key -> Map<'key,'a> -> Map<'key,'a>
    Remove an element from the domain of the map. No exception is raised if the element is not present.
val tryFind : 'key -> Map<'key,'a> -> 'a option
    Lookup an element in the map, returning a Some value if the element is in the domain of the map and None if not.

### Examples
## Set and Map Performance

F# sets and maps are implemented as immutable AVL trees, an efficient data structure which forms a self-balancing binary tree. AVL trees are well-known for their efficiency, in which they can search, insert, and delete elements in the tree in O(log n) time, where n is the number of elements in the tree.

# Discriminated Unions

Discriminated unions, also called tagged unions, represent a finite, well-defined set of choices. Discriminated unions are often the tool of choice for building up more complicated data structures including linked lists and a wide range of trees.

## Creating Discriminated Unions

Discriminated unions are defined using the following syntax:
By convention, union names start with a lowercase character, and union cases are written in PascalCase.

## Union Basics: an On/Off switch

Let's say we have a light switch. For most of us, a light switch has two possible states: the light switch can be ON, or it can be OFF. We can use an F# union to model our light switch's state as follows:
We've defined a union called switchstate which has two cases, On and Off. You can create and use instances of switchstate as follows:
This program has the following types:
It outputs the following:
Notice that we create an instance of switchstate simply by using the name of its cases; this is because, in a literal sense, the cases of a union are constructors. As you may have guessed, since we use the same syntax for constructing objects as for matching them, we can pattern match on unions in the following way:
The function toggle has the type val toggle : switchstate -> switchstate.
This program has the following output:

## Holding Data In Unions: a dimmer switch

The example above is kept deliberately simple. In fact, in many ways, the discriminated union defined above doesn't appear much different from an enum value. However, let's say we wanted to change our light switch model into a model of a dimmer switch, or in other words a light switch that allows users to adjust a lightbulb's power output from 0% to 100% power.
We can modify our union above to accommodate three possible states: On, Off, and an adjustable value between 0 and 100:
We've added a new case, Adjustable of float. This case is fundamentally the same as the others, except it takes a single float value in its constructor:
This program outputs:

## Creating Trees

Discriminated unions can easily model a wide variety of trees and hierarchical data structures.
For example, let's consider the following binary tree:
Each node of our tree contains exactly two branches, and each branch can either be an integer or another tree. We can represent this tree as follows:
We can create an instance of the tree above using the following code:
This program outputs the following:
Very often, we want to recursively enumerate through all of the nodes in a tree structure. For example, if we wanted to count the total number of Leaf nodes in our tree, we can use:
This program outputs:

## Generalizing Unions For All Datatypes

Note that our binary tree above only operates on integers. It is possible to construct unions that are generalized to operate on all possible data types. We can modify the definition of our union to the following:
We can use the union defined above to define a binary tree of any data type:
The functions above have the following types:
This program outputs:

## Examples
### Built-in Union Types

F# has several built-in types derived from discriminated unions, some of which have already been introduced in this tutorial. These types include:

### Propositional Logic

The ML family of languages, which includes F# and its parent language OCaml, were originally designed for the development of automated theorem provers. Union types allow F# programmers to represent propositional logic remarkably concisely. To keep things simple, let's limit our propositions to four possible cases:
Let's say we had a series of propositions and wanted to determine whether they evaluate to true or false. We can easily write an eval function by recursively enumerating through a propositional statement as follows:
The eval function has the type val eval : proposition -> bool.
Here is a full program using the eval function:
This program outputs the following:

## Additional Reading

Theorem Proving Examples (OCaml)

# Mutable Data

All of the data types and values in F# seen so far have been immutable, meaning the values cannot be reassigned another value after they've been declared. However, F# allows programmers to create variables in the true sense of the word: variables whose values can change throughout the lifetime of the application.

## mutable Keyword

The simplest mutable variables in F# are declared using the mutable keyword. Here is a sample using fsi:
As shown above, the <- operator is used to assign a mutable variable a new value. Notice that variable assignment actually returns unit as a value.
The mutable keyword is frequently used with record types to create mutable records:

### Limitations of Mutable Variables

Mutable variables are somewhat limited: before F# 4.0, mutables were inaccessible outside of the scope of the function where they are defined. Specifically, this means its not possible to reference a mutable in a subfunction of another function. Here's a demonstration in fsi:

## Ref cells

Ref cells get around some of the limitations of mutables. In fact, ref cells are very simple datatypes which wrap up a mutable field in a record type. Ref cells are defined by F# as follows:
The F# library contains several built-in functions and operators for working with ref cells:
The ref function is used to create a ref cell, the ! operator is used to read the contents of a ref cell, and the := operator is used to assign a ref cell a new value. Here is a sample in fsi:
Since ref cells are allocated on the heap, they can be shared across multiple functions:
The withSideEffects function has the type val withSideEffects : string ref -> unit.
This program outputs the following:
The withSideEffects function is named as such because it has a side-effect, meaning it can change the state of a variable in other functions. Ref Cells should be treated like fire. Use it cautiously when it is absolutely necessary but avoid it in general. If you find yourself using Ref Cells while translating code from C/C++, then ignore efficiency for a while and see if you can get away without Ref Cells or at worst using mutable. You would often stumble upon a more elegant and more maintanable algorithm

### Aliasing Ref Cells

    Note: While imperative programming uses aliasing extensively, this practice has a number of problems. In particular it makes programs hard to follow since the state of any variable can be modified at any point elsewhere in an application. Additionally, multithreaded applications sharing mutable state are difficult to reason about since one thread can potentially change the state of a variable in another thread, which can result in a number of subtle errors related to race conditions and dead locks.
A ref cell is very similar to a C or C++ pointer. Its possible to point to two or more ref cells to the same memory address; changes at that memory address will change the state of all ref cells pointing to it. Conceptually, this process looks like this:
Let's say we have 3 ref cells looking at the same address in memory:
cell1, cell2, and cell3 are all pointing to the same address in memory. The .contents property of each cell is 7. Let's say, at some point in our program, we execute the code cell1 := 10, this changes the value in memory to the following:
By assigning cell1.contents a new value, the variables cell2 and cell3 were changed as well. This can be demonstrated using fsi as follows:

## Encapsulating Mutable State

F# discourages the practice of passing mutable data between functions. Functions that rely on mutation should generally hide its implementation details behind a private function, such as the following example in FSI:

# Control Flow

In all programming languages, control flow refers to the decisions made in code that affect the order in which statements are executed in an application. F#'s imperative control flow elements are similar to those encountered in other languages.

## Imperative Programming in a Nutshell

Most programmers coming from a C#, Java, or C++ background are familiar with an imperative style of programming which uses loops, mutable data, and functions with side-effects in applications. While F# primarily encourages the use of a functional programming style, it has constructs which allow programmers to write code in a more imperative style as well. Imperative programming can be useful in the following situations:
* Interacting with many objects in the .NET Framework, most of which are inherently imperative.
* Interacting with components that depend heavily on side-effects, such as GUIs, I/O, and sockets.
* Scripting and prototyping snippets of code.
* Initializing complex data structures.
* Optimizing blocks of code where an imperative version of an algorithm is more efficient than the functional version.

## if/then Decisions

F#'s if/then/elif/else construct has already been seen earlier in this book, but to introduce it more formally, the if/then construct has the following syntaxes:
Like all F# blocks, the scope of an if statement extends to any code indented under it. For example:
This program prints:

### Working With Conditions

F# has three boolean operators:
| Symbol | Description | Example |
| && | Logical AND (infix, short-circuited) | true && false (* returns false *) |
| || | Logical OR (infix, short-circuited) | true || false (* returns true *) |
| not | Logical NOT | not false (* returns true *) |
The && and || operators are short-circuited, meaning the CLR will perform the minimum evaluation necessary to determine whether the condition will succeed or fail. For example, if the left side of an && evaluates to false, then there is no need to evaluate the right side; likewise, if the left side of a || evaluates to true, then there is no need to evaluate the right side of the expression.
Here is a demonstration of short-circuiting in F#:
The alwaysTrue and alwaysFalse methods return true and false respectively, but they also have a side-effect of printing a message to the console whenever the functions are evaluated.
This program outputs the following:
As you can see above, the expression alwaysTrue && alwaysFalse evaluates both sides of the expression. alwaysFalse && alwaysTrue only evaluates the left side of the expression; since the left side returns false, its unnecessary to evaluate the right side.

## for Loops Over Ranges

for loops are traditionally used to iterate over a well-defined integer range. The syntax of a for loop is defined as:
Here's a trivial program which prints out the numbers 1 - 10:
This program outputs:
This code takes input from the user to compute an average:
This program outputs:

## for Loops Over Collections and Sequences

Its often convenient to iterate over collections of items using the syntax:
For example, we can print out a shopping list in fsi:

## while Loops

As the name suggests, while loops will repeat a block of code indefinitely while a particular condition is true. The syntax of a while loop is defined as follows:
We use a while loop when we don't know how many times to execute a block of code. For example, lets say we wanted the user to guess a password to a secret area; the user could get the password right on the first try, or the user could try millions of passwords, we just don't know. Here is a short program that requires a user to guess a password correctly in at most 3 attempts:
This program outputs the following:

# Arrays

Arrays are a ubiquitous, familiar data structure used to represent a group of related, ordered values. Unlike F# data structures, arrays are mutable, meaning the values in an array can be changed after the array has been created.

## Creating Arrays

Arrays are conceptually similar to lists. Naturally, arrays can be created using many of the same techniques as lists:

### Array comprehensions

F# supports array comprehensions using ranges and generators in the same style and format as list comprehensions:

### System.Array Methods

There are several methods in the System.Array module for creating arrays:
val zeroCreate : int arraySize -> 'T
    Creates an array with arraySize elements. Each element in the array holds the default value for the particular data type (0 for numbers, false for bools, null for reference types).
val create : int -> 'T value -> 'T
    Creates an array with arraySize elements. Initializes each element in the array with value.
val init : int arraySize -> (int index -> 'T) initializer -> 'T
    Creates an array with arraySize elements. Initializes each element in the array with the initializer function.

## Working With Arrays

Elements in an array are accessed by their index, or position in an array. Array indexes always start at 0 and end at array.length - 1. For example, lets take the following array:
This list contains 5 items. The first index is 0, and the last index is 4.
We can access items in the array using the .[index] operator, also called indexer notation. Here is the same array in fsi:
Instances of arrays have a Length property which returns the number of elements in the array:
Arrays are mutable data structures, meaning we can assign elements in an array new values at any point in our program:
If you try to access an element outside the range of an array, you'll get an exception:

### Array Slicing

F# supports a few useful operators which allow programmers to return "slices" or subarrays of an array using the .[start..finish] operator, where one of the start and finish arguments may be omitted.
Note that array slices generate a new array, rather than altering the existing array. This requires allocating new memory and copying elements from our source array into our target array. If performance is a high priority, it is generally more efficient to look at parts of an array using a few index adjustments.

### Multi-dimensional Arrays

A multi-dimensional array is literally an array of arrays. Conceptually, it's not any harder to work with these types of arrays than single-dimensional arrays (as shown above). Multi-dimensional arrays come in two forms: rectangular and jagged arrays.

#### Rectangular Arrays

A rectangular array, which may be called a grid or a matrix, is an array of arrays, where all of the inner arrays have the same length. Here is a simple 2x3 rectangular array in fsi:
This array has 2 rows, and each row has 3 columns. To access elements in this array, you use the .[row,col] operator:
Here's a simple program to demonstrate how to use and iterate through multidimensional arrays:
This program outputs the following:
In additional to the Array2D module, F# has an Array3D module to support 3-dimensional arrays as well.
    Note It's possible to create arrays with more than 3 dimensions using the System.Array.CreateInstance method, but it's generally recommended to avoid creating arrays with huge numbers of elements or dimensions, since it is very hard to manage, and also can quickly consume all of the available memory on a machine.

#### Jagged arrays

A jagged array is an array of arrays, except each row in the array does not necessarily need to have the same number of elements:
You use the .[index] operator to access items in the array. Since each element contains another array, it's common to see code that resembles .[row].[col]:
    Note: Notice that the data type of a rectangular array is 'a[,], but the data type of a jagged array is 'a array array. This results because a rectangular array stores data "flat", whereas a jagged array is literally an array of pointers to arrays. Since these two types of arrays are stored differently in memory, F# treats 'a[,] and 'a array array as two different, non-interchangeable data types. As a result, rectangular and jagged arrays have slightly different syntax for element access.
    Rectangular arrays are stored in a slightly more efficient manner and generally perform better than jagged arrays, although there may not be a perceptible difference in most applications. However, it's worth noting performance differences between the two in benchmark tests.

### Using the Array Module

There are two array modules, System.Array and Microsoft.FSharp.Collections.Array, developed by the .NET BCL designers and the creators of F# respectively. Many of the methods and functions in the F# Array module are similar to those in the List module.
val append : 'T first -> 'T second -> 'T
    Returns a new array with elements consisting of the first array followed by the second array.
val choose : ('T item -> 'U option) -> 'T input -> 'U
    Filters and maps an array, returning a new array consisting of all elements which returned Some.
val copy : 'T input -> 'T
    Returns a copy of the input array.
val fill : 'T input -> int start -> int end -> 'T value -> unit
    Assigns value to all the elements between the start and end indexes.
val filter : ('T -> bool) -> 'T -> 'T
    Returns a new array consisting of items filtered out of the input array.
val fold : ('State -> 'T -> 'State) -> 'State -> 'T input -> 'State
    Accumulates left to right over an array.
val foldBack : ('T -> 'State -> 'State) -> 'T input -> 'State -> 'State
    Accumulates right to left over an array.
val iter : ('T -> unit) -> 'T input -> unit
    Applies a function to all of the elements of the input array.
val length : 'T -> int
    Returns the number of items in an array.
val map : ('T -> 'U) -> 'T -> 'U
    Applies a mapping function to each element in the input array to return a new array.
val rev : 'T input -> 'T
    Returns a new array with the items in reverse order.
val sort : 'T -> 'T
    Sorts a copy of an array.
val sortInPlace : 'T -> unit
    Sorts an array in place. Note that the sortInPlace method returns unit, indicating the sortInPlace mutates the original array.
val sortBy : ('T -> 'T -> int) -> 'T -> 'T
    Sorts a copy of an array based on the sorting function.
val sub : 'T -> int start -> int end -> 'T
    Returns a sub array based on the given start and end indexes.

## Differences Between Arrays and Lists

* Lists
** Immutable, allows new lists to share nodes with other lists.
** List literals.
** Pattern matching.
** Supports mapping and folding.
** Linear lookup time.
** No random access to elements, just "forward-only" traversal.
* Arrays
** Array literals.
** Constant lookup time.
** Good spacial locality of reference ensures efficient lookup time.
** Indexes indicate the position of each element relative to others, making arrays ideal for random access.
** Supports mapping and folding.
** Mutability prevents arrays from sharing nodes with other elements in an array.
** Not resizable.

### Representation in Memory

Items in an array are represented in memory as adjacent values in memory. For example, lets say we create the following int array:
    [| 15; 5; 21; 0; 9 |]
Represented in memory, our array resembles something like this:
Each int occupies 4 bytes of memory. Since our array contains 5 elements, the operating systems allocate 20 bytes of memory to hold this array (4 bytes * 5 elements = 20 bytes). The first element in the array occupies memory 100-103, the second element occupies 104-107, and so on.
We know that each element in the array is identified by its index or position in the array. Literally, the index is an offset: since the array starts at memory location 100, and each element in the array occupies a fixed amount of memory, the operating system can know the exact address of each element in memory using the formula:
    Start memory address of element at index n = StartPosition of array + (n * length of data type)
    End memory address of element at index n = Start memory address + length of data type
In layman's terms, this means we can access the nth element of an array in constant time, or in O(1) operations. This is in contrast to lists, where accessing the nth element requires O(n) operations.
With the understanding that elements in an array occupy adjacent memory locations, we can deduce two properties of arrays:
* Creating arrays requires programmers to specify the size of the array up front, otherwise, the operating system won't know how many adjacent memory locations to allocate.
* Arrays are not resizable, because memory locations before the first element or beyond the last element may hold data used by other applications. An array is only "resized" by allocating a new block of memory and copying all of the elements from the old array into the new array.

# Mutable Collections

The .NET BCL comes with its own suite of mutable collections which are found in the System.Collections.Generic namespace. These built-in collections are very similar to their immutable counterparts in F#.

## List<'T> Class

The List<'T> class represents a strongly typed list of objects that can be accessed by index. Conceptually, this makes the List<'T> class similar to arrays. However, unlike arrays, Lists can be resized and don't need to have their size specified on declaration.
.NET lists are created using the new keyword and calling the list's constructor as follows:
It's easy to tell that .NET lists are mutable because their Add methods return unit rather than returning another list.

### Underlying Implementation

Behind the scenes, the List<'T> class is just a fancy wrapper for an array. When a List<'T> is constructed, it creates an 4-element array in memory. Adding the first 4 items is an O(1) operation. However, as soon as the 5th element needs to be added, the list doubles the size of the internal array, which means it has to reallocate new memory and copy elements in the existing list; this is a O(n) operation, where n is the number of items in the list.
The List<'T>.Count property returns the number of items currently held in the collection, the List<'T>.Capacity collection returns the size of the underlying array. This code sample demonstrates how the underlying array is resized:
If you know the maximum size of the list beforehand, it is possible to avoid the performance hit by calling the List<'T>(size : int) constructor instead. The following sample demonstrates how to add 1000 items to a list without resizing the internal array:

## LinkedList<'T> Class

A LinkedList<'T> represented a doubly-linked sequence of nodes which allows efficient O(1) inserts and removal, supports forward and backward traversal, but its implementation prevents efficient random access. Linked lists have a few valuable methods:
Note that these methods return a LinkedListNode<'T>, not a new LinkedList<'T>. Adding nodes actually mutates the LinkedList object:
The Stack<'T> and Queue<'T> classes are special cases of a linked list (they can be thought of as linked lists with restrictions on where you can add and remove items).

### Stack<'T> Class

A Stack<'T> only allows programmers prepend/push and remove/pop items from the front of a list, which makes it a last in, first out (LIFO) data structure. The Stack<'T> class can be thought of as a mutable version of the F# list.
A stack of coins could be represented with this data structure. If we stacked coins one on top another, the first coin in the stack is at the bottom of the stack, and the last coin in the stack appears at the top. We remove coins from top to bottom, so the last coin added to the stack is the first one removed.

### Queue<'T> Class

A Queue<'T> only allows programmers to append/enqueue to the rear of a list and remove/dequeue from the front of a list, which makes it a first in, first out (FIFO) data structure.
A line of people might be represented by a queue: people add themselves to the rear of the line, and are removed from the front. The first person to stand in line is the first person to be served.

## HashSet<'T>, and Dictionary<'TKey, 'TValue> Classes

The HashSet<'T> and Dictionary<'TKey, 'TValue> classes are mutable analogs of the F# set and map data structures and contain many of the same functions.
Using the HashSet<'T>
Using the Dictionary<'TKey, 'TValue>

## Differences Between .NET BCL and F# Collections

The major difference between the collections built into the .NET BCL and their F# analogs is, of course, mutability. The mutable nature of BCL collections dramatically affects their implementation and time-complexity:
| .NET Data Structure | Insert | Remove | Lookup | F# Data Structure | Insert | Remove | Lookup |
| List | O(1) / O(n)* | O(n) | O(1) (by index) / O(n) (linear) | No built-in equivalent | No built-in equivalent | No built-in equivalent | No built-in equivalent |
| LinkedList | O(1) | O(1) | O(n) | No built-in equivalent | No built-in equivalent | No built-in equivalent | No built-in equivalent |
| Stack | O(1) | O(1) | O(n) | List | O(1) | n/a | O(n) |
| Queue | O(1) | O(1) | O(n) | No built-in equivalent | No built-in equivalent | No built-in equivalent | No built-in equivalent |
| HashSet | O(1) / O(n)* | O(1) | O(1) | Set | O(log n) | O(log n) | O(log n) |
| Dictionary | O(1) / O(n)* | O(1) | O(1) | Map | O(log n) | O(log n) | O(log n) |
    * These classes are built on top of internal arrays. They may take a performance hit as the internal arrays are periodically resized when adding items.
    Note: the Big-O notation above refers to the time-complexity of the insert/remove/retrieve operations relative to the number of items in the data structure, not the relative amount of time required to evaluate the operations relative to other data structures. For example, accessing arrays by index vs. accessing dictionaries by key have the same time complexity, O(1), but the operations do not necessarily occur in the same amount of time.

# Input and Output

Input and output, also called I/O, refers to any kind of communication between two hardware devices or between the user and the computer. This includes printing text out to the console, reading and writing files to disk, sending data over a socket, sending data to the printer, and a wide variety of other common tasks.
This page is not intended to provide an exhaustive look at .NET's I/O methods (readers seeking exhaustive references are encouraged to review the excellent documentation on the System.IO namespace on MSDN). This page will provide a cursory overview of some of the basic methods available to F# programmers for printing and working with files.

## Working with the Console
### With F#

By now, you're probably familiar with the printf, printfn, sprintf and its variants in the Printf module. However, just to describe these methods more formally, these methods are used for printf-style printing and formatting using % markers as placeholders:
Print methods take a format string and a series of arguments, for example:
Methods in the Printf module are type-safe. For example, attempting to use substitute an int placeholder with a string results in a compilation error:
According to the F# documentation, % placeholders consist of the following:
    %[flags][width][.precision][type]
[flags] (optional)
Valid flags are:
    0: add zeros instead of spaces to make up the required width
    '-': left justify the result within the width specified
    '+': add a '+' character if the number is positive (to match a '-' sign for negatives)
    ' ': add an extra space if the number is positive (to match a '-' sign for negatives)
[width] (optional)
The optional width is an integer indicating the minimal width of the result. For instance, %6d prints an integer, prefixing it with spaces to fill at least 6 characters. If width is '*', then an extra integer argument is taken to specify the corresponding width.
    any number
[.precision] (optional)
Represents the number of digits after a floating point number.
[type] (required)
The following placeholder types are interpreted as follows:
Programmers can print to the console using the printf method, however F# recommends reading console input using the System.Console.ReadLine method.

### With .NET

.NET includes its own notation for format specifiers. .NET format strings are untyped. Additionally, .NET's format strings are designed to be extensible, meaning that a programmer can implement their own custom format strings. Format placeholders have the following form:
    {index[, length][:formatString]}
For example, using the String.Format method in fsi:
See Number Format Strings, Date and Time Format Strings, and Enum Format Strings for a comprehensive reference on format specifiers for .NET.
Programmers can read and write to the console using the System.Console class:

## System.IO Namespace

The System.IO namespace contains a variety of useful classes for performing basic I/O.

### Files and Directories

The following classes are useful for interrogating the host filesystem:
* The System.IO.File class exposes several useful members for creating, appending, and deleting files.
* System.IO.Directory exposes methods for creating, moving, and deleting directories.
* System.IO.Path performs operations on strings which represent file paths.
* System.IO.FileSystemWatcher which allows users to listen to a directory for changes.

### Streams

A stream is a sequence of bytes. .NET provides some classes which allow programmers to work with streams including:
* System.IO.StreamReader which is used to read characters from a stream.
* System.IO.StreamWriter which is used to write characters to a stream.
* System.IO.MemoryStream which creates an in-memory stream of bytes.

# Exception Handling

When a program encounters a problem or enters an invalid state, it will often respond by throwing an exception. Left to its own devices, an uncaught exception will crash an application. Programmers write exception handling code to rescue an application from an invalid state.

## Try/With

Let's look at the following code:
This code is syntactically valid, and it has the correct types. However, it can fail at run time if we give it a bad input:
This program outputs the following:
The string monkeys does not represent a number, so the conversion fails with an exception. We can handle this exception using F#'s try... with, a special kind of pattern matching construct:
This program outputs the following:
It is, of course, wholly possible to catch multiple types of exceptions in a single with block. For example, according to the MSDN documentation, the System.Int32.Parse(s : string) method will throw three types of exceptions:
ArgumentNullException
    Occurs when s is a null reference.
FormatException
    Occurs when s does not represent a numeric input.
OverflowException
    Occurs when s represents number greater than or less than Int32.MaxValue or Int32.MinValue (i.e. the number cannot be represented with a 32-bit signed integer).
We can catch all of these exceptions by adding additional match cases:
Its not necessary to have an exhaustive list of match cases on exception types, as the uncaught exception will simply move to the next method in the stack trace.

## Raising Exceptions

The code above demonstrates how to recover from an invalid state. However, when designing F# libraries, its often useful to throw exceptions to notify users that the program encountered some kind of invalid input. There are several standard functions for raising exceptions:
For example:

## Try/Finally

Normally, an exception will cause a function to exit immediately. However, a finally block will always execute, even if the code throws an exception:
This program will output the following:
Notice that our finally block executed in spite of the exception. Finally blocks are used most commonly to clean up resources, such as closing an open file handle or closing a database connection (even in the event of an exception, we do not want to leave file handles or database connections open):

### use Statement

Many objects in the .NET framework implement the System.IDisposable interface, which means the objects have a special method called Dispose to guarantee deterministic cleanup of unmanaged resources. It's considered a best practice to call Dispose on these types of objects as soon as they are no longer needed.
Traditionally, we'd use a try/finally block in this fashion:
However, this can be occasionally bulky and cumbersome, especially when dealing with many objects which implement the IDisposable interface. F# provides the keyword use as syntactic sugar for the pattern above. An equivalent version of the code above can be written as follows:
The scope of a use statement is identical to the scope of a let statement. F# will automatically call Dispose on an object when the identifier goes out of scope.

## Defining New Exceptions

F# allows us to easily define new types of exceptions using the exception declaration. Here's an example using fsi:
We can pattern match on our new existing exception type just as easily as any other exception:

## Exception Handling Constructs

| Construct | Kind | Description |
| raise expr | F# library function | Raises the given exception |
| failwith expr | F# library function | Raises the System.Exception exception |
| try expr with rules | F# expression | Catches expressions matching the pattern rules |
| try expr finally expr | F# expression | Execution the finally expression both when the computation is successful and when an exception is raised |
| | :? ArgumentException | F# pattern rule | A rule matching the given .NET exception type |
| | :? ArgumentException as e | F# pattern rule | A rule matching the given .NET exception type, binding the name e to the exception object value |
| | Failure(msg) -> expr | F# pattern rule | A rule matching the given data-carrying F# exception |
| | exn -> expr | F# pattern rule | A rule matching any exception, binding the name exn to the exception object value |
| | exn when expr -> expr | F# pattern rule | A rule matching the exception under the given condition, binding the name exn to the exception object value |

# Operator Overloading

Operator overloading allows programmers to provide new behavior for the default operators in F#. In practice, programmers overload operators to provide a simplified syntax for objects which can be combined mathematically.

## Using Operators

You've already used operators:
Here + is example of using a mathematical addition operator.

## Operator Overloading

Operators are functions with special names, enclosed in brackets. They must be defined as static class members. Here's an example on declaring + operator on complex numbers:
In FSI, we can add two complex numbers as follows:

## Defining New Operators

In addition to overloading existing operators, its possible to define new operators. The names of custom operators can only be one or more of the following characters:
F# supports two types of operators: infix operators and prefix operators.

### Infix operators

An infix operator takes two arguments, with the operator appearing in between both arguments (i.e. arg1 {op} arg2). We can define our own infix operators using the syntax:
In addition to mathematical operators, F# has a variety of infix operators defined as part of its library, for example:
Let's say we're writing an application which performs a lot of regex matching and replacing. We can match text using Perl-style operators by defining our own operators as follows:
This program outputs the following:

### Prefix Operators

Prefix operators take a single argument which appears to the right side of the operator ({op}argument). You've already seen how the ! operator is defined for ref cells:
Let's say we're writing a number crunching application, and we wanted to define some operators that work on lists of numbers. We might define some prefix operators in fsi as follows:

# Classes

In the real world, an object is a "real" thing. A cat, person, computer, and a roll of duct tape are all "real" things in the tangible sense. When we think about these things, we can broadly describe them in terms of a number of attributes:
* Properties: a person has a name, a cat has four legs, computers have a price tag, duct tape is sticky.
* Behaviors: a person reads the newspaper, cats sleep all day, computers crunch numbers, duct tape attaches things to other things.
* Types/group membership: an employee is a type of person, a cat is a pet, a Dell and Mac are types of computers, duct tape is part of the broader family of adhesives.
In the programming world, an "object" is, in the simplest of terms, a model of something in the real world. Object-oriented programming (OOP) exists because it allows programmers to model real-world entities and simulate their interactions in code. Just like their real-world counterparts, objects in computer programming have properties and behaviors, and can be classified according to their type.
While we can certainly create objects that represents cats, people, and adhesives, objects can also represent less concrete things, such as a bank account or a business rule.
Although the scope of OOP has expanded to include some advanced concepts such as design patterns and the large-scale architecture of applications, this page will keep things simple and limit the discussion of OOP to data modeling.

## Defining an Object

Before an object is created, its properties and functions should be defined. You define properties and methods of an object in a class. There are actually two different syntaxes for defining a class: an implicit syntax and an explicit syntax.

### Implicit Class Construction

Implicit class syntax is defined as follows:
    Elements in brackets are optional, elements followed by a * may appear zero or more times.
This syntax above is not as daunting as it looks. Here's a simple class written in implicit style:
The code above defines a class called Account, which has three properties and two methods. Let's take a closer look at the following:
The underlined code is called the class constructor. A constructor is a special kind of function used to initialize the fields in an object. In this case, our constructor defines two values, number and holder, which can be accessed anywhere in our class. You create an instance of Account by using the new keyword and passing the appropriate parameters into the constructor as follows:
Additionally, let's look at the way a member is defined:
The x above is an alias for the object currently in scope. Most OO languages provide an implicit this or self variable to access the object in scope, but F# requires programmers to create their own alias.
After we can create an instance of our Account, we can access its properties using .propertyName notation. Here's an example in FSI:

#### Example

Let's use this class in a real program:
The program has the following types:
The program outputs the following:

#### Example using the do keyword

The do keyword is used for post-constructor initialization. For example, to create an object which represents a stock, it is necessary to pass in the stock symbol and initialize the rest of the properties in our constructor:
This program has the following types:
This program outputs the following (your outputs will vary):
    Note: It's possible to have any number of do statements in a class definition, although there's no particular reason to need more than one.

### Explicit Class Definition

Classes written in explicit style follow this format:
Here's a class defined using the explicit syntax:
Each val defines a field in our object. Unlike other object-oriented languages, F# does not implicitly initialize fields in a class to any value. Instead, F# requires programmers to define a constructor and explicitly initialize each field in their object with a value.
We can perform some post-constructor processing using a then block as follows:
Notice that we have to add an alias after our constructor, new (x1, y1, x2, y2) as this), to access the fields of our object being constructed. Each time we create a Line object, the constructor will print to the console. We can demonstrate this using fsi:

#### Example Using Two Constructors

Since the constructor is defined explicitly, we have the option to provide more than one constructor.
This program has the following types:
Notice that our val fields are included in the public interface of our class definition.
This program outputs the following:

### Differences Between Implicit and Explicit Syntaxes

As you've probably guessed, the major difference between the two syntaxes is related to the constructor: the explicit syntax forces a programmer to provide explicit constructor(s), whereas the implicit syntax fuses the primary constructor with the class body. However, there are a few other subtle differences:
* The explicit syntax does not allow programmers to declare let and do bindings.
* Even though val fields can be used in the implicit syntax, they must have the attribute [<DefaultValue>] and be mutable. It is more convenient to use let bindings in this case. Public member accessors can be added when they need to be public.
* In the implicit syntax, the primary constructor parameters are visible throughout the whole class body. By using this feature, it is not necessary to write code that copies constructor parameters to instance members.
* While both syntaxes support multiple constructors, when you declare additional constructors with the implicit syntax, they must call the primary constructor. In the explicit syntax all constructors are declared with new and there is no primary constructor that needs to be referenced from others.
| Class with primary (implicit) constructor | Class with only explicit constructors |
| // The class body acts as a constructor type Car1(make : string, model : string) = class // x.Make and x.Model are property getters // (explained later in this chapter) // Notice how they can access the // constructor parameters directly member x.Make = make member x.Model = model // This is an extra constructor. // It calls the primary constructor new = Car1("default make", "default model") end | type Car2 = class // In this case, we need to declare // all fields and their types explicitly val private make : string val private model : string // Notice how field access differs // from parameter access member x.Make = x.make member x.Model = x.model // Two constructors new (make : string, model : string) = { make = make model = model } new = { make = "default make" model = "default model" } end |
In general, its up to the programmer to use the implicit or explicit syntax to define classes. However, the implicit syntax is used more often in practice as it tends to result in shorter, more readable class definitions.

### Class Inference

F#'s #light syntax allows programmers to omit the class and end keywords in class definitions, a feature commonly referred to as class inference or type kind inference. For example, there is no difference between the following class definitions:
| Class Inference | Class Explicit |
| type Product(make : string, model : string) = member x.Make = make member x.Model = model | type Car(make : string, model : string) = class member x.Make = make member x.Model = model end |
Both classes compile down to the same bytecode, but the code using class inference allows us to omit a few unnecessary keywords.
Class inference and class explicit styles are considered acceptable. At the very least, when writing F# libraries, don't define half of your classes using class inference and the other half using class explicit style—pick one style and use it consistently for all of your classes throughout your project.

## Class Members
### Instance and Static Members

There are two types of members you can add to an object:
* Instance members, which can only be called from an object instance created using the new keyword.
* Static members, which are not associated with any object instance.
The following class has a static method and an instance method:
We invoke a static method using the form className.methodName. We invoke instance methods by creating an instance of our class and calling the methods using classInstance.methodName. Here is a demonstration in fsi:
We can, of course, invoke instance methods from objects passed into static methods, for example, let's say we add a Copy method to our object defined above:
We can experiment with this method in fsi:
Object.ReferenceEquals is a static method on the System.Object class which determines whether two objects instances are the same object. As shown above, our Copy method takes an instance of SomeClass and accesses its Prop property.
When should you use static methods rather than instance methods?
When the designers of the .NET framework were designing the System.String class, they had to decide where the Length method should go. They had the option of making the property an instance method (s.Length) or making it static (String.GetLength(s)). The .NET designers chose to make Length an instance method because it is an intrinsic property of strings.
On the other hand, the String class also has several static methods, including String.Concat which takes a list of string and concatenates them all together. Concatenating strings is instance-agnostic, its does not depend on the instance members of any particular strings.
The following general principles apply to all OO languages:
* Instance members should be used to access properties intrinsic to an object, such as stringInstance.Length.
* Instance methods should be used when they depend on state of a particular object instance, such as stringInstance.Contains.
* Instance methods should be used when its expected that programmers will want to override the method in a derived class.
* Static methods should not depend on a particular instance of an object, such as Int32.TryParse.
* Static methods should return the same value as long as the inputs remain the same.
* Constants, which are values that don't change for any class instance, should be declared as a static members, such as System.Boolean.TrueString.

### Getters and Setters

Getters and setters are special functions which allow programmers to read and write to members using a convenient syntax. Getters and setters are written using this format:
Here's a simple example using fsi:
Getters and setters are used to expose private members to outside world. For example, our Num property allows users to read/write to the internal num variable. Since getters and setters are glorified functions, we can use them to sanitize input before writing the values to our internal variables. For example, we can modify our IntWrapper class to constrain our to values between 0 and 10 by modifying our class as follows:
We can use this class in fsi:

### Adding Members to Records and Unions

Its just as easy to add members to records and union types as well.
Record example:
Union example

## Generic classes

Classes which take generic types can be created:
We can use this class in FSI as follows:
Generic classes help programmers generalize classes to operate on multiple different types. They are used in fundamentally the same way as all other generic types already seen in F#, such as Lists, Sets, Maps, and union types.

## Pattern Matching Objects

While it's not possible to match objects based on their structure in quite the same way that we do for lists and union types, F# allows programmers to match on types using the syntax:
Here's an example which uses type-testing:
This program outputs:

# Inheritance

Many object-oriented languages use inheritance extensively in the .NET BCL to construct class hierarchies.

## Subclasses

A subclass is, in the simplest terms, a class derived from a class which has already been defined. A subclass inherits its members from a base class in addition to adding its own members. A subclass is defined using the inherit keyword as shown below:
Our simple class hierarchy looks like this:
The Student and Worker subclasses both inherit the Name and Greet methods from the Person base class. This can be demonstrated in fsi:
.NET's object model supports single-class inheritance, meaning that a subclass is limited to one base class. In other words, its not possible to create a class which derives from Student and Employee simultaneously.

### Overriding Methods

Occasionally, you may want a derived class to change the default behavior of methods inherited from the base class. For example, the output of the .ToString method above isn't very useful. We can override that behavior with a different implementation using the override:
We've overridden the default implementation of the ToString method, causing it to print out a person's name.
Methods in F# are not overridable by default. If you expect users will want to override methods in a derived class, you have to declare your method as overridable using the abstract and default keywords as follows:
Our class Person provides a Greet method which may be overridden in derived classes. Here's an example of these two classes in fsi:

### Abstract Classes

An abstract class is one which provides an incomplete implementation of an object, and requires a programmer to create subclasses of the abstract class to fill in the rest of the implementation. For example, consider the following:
The first thing you'll notice is the AbstractClass attribute, which tells the compiler that our class has some abstract members. Additionally, you notice two abstract members, Draw and Area don't have an implementation, only a type signature.
We can't create an instance of Shape because the class hasn't been fully implemented. Instead, we have to derive from Shape and override the Draw and Area methods with a concrete implementation:
Now we have several different implementations of the Shape class. We can experiment with these in fsi:

## Working With Subclasses
### Up-casting and Down-casting

A type cast is an operation which changes the type of an object from one type to another. This is not the same as a map function, because a type cast does not return an instance of a new object, it returns the same instance of an object with a different type.
For example, let's say B is a subclass of A. If we have an instance of B, we are able to cast as an instance of A. Since A is upward in the class hierarchy, we call this an up-cast. We use the :> operator to perform upcasts:
Up-casting is considered "safe", because a derived class is guaranteed to have all of the same members as an ancestor class. We can, if necessary, go in the opposite direction: we can down-cast from an ancestor class to a derived class using the :?> operator:
Since intAsObj holds an int boxed as an obj, we can downcast to an int as needed. However, we cannot downcast to a string because it is an incompatible type. Down-casting is considered "unsafe" because the error isn't detectable by the type-checker, so an error with a down-cast always results in a runtime exception.

#### Up-casting example

This program has the following types:
This program outputs:

### Public, Private, and Protected Members
# Interfaces

An object's interface refers to all of the public members and functions that a function exposes to consumers of the object. For example, take the following:
This class contains several public, private, and internal members. However, consumers of this class can only access the public members; when a consumer uses this class, they see the following interface:
Notice the _birthday, _lastEaten, _foodsEaten, UpdateFoodsEaten, and ResetLastEaten members are inaccessible to the outside world, so they are not part of this object's public interface.
All interfaces you've seen so far have been intrinsically tied to a specific object. However, F# and many other OO languages allow users to define interfaces as stand-alone types, allowing us to effectively separate an object's interface from its implementation.

## Defining Interfaces

According to the F# specification, interfaces are defined with the following syntax:
    Note: The interface/end tokens can be omitted when using the #light syntax option, in which case Type Kind Inference (§10.1) is used to determine the kind of the type. The presence of any non-abstract members or constructors means a type is not an interface type.
For example:

## Using Interfaces

Since they only define a set of public method signatures, users need to create an object to implement the interface. Here are three classes which implement the ILifeForm interface in fsi:
Typically, we call an interface an abstraction, and any class which implements the interface as a concrete implementation. In the example above, ILifeForm is an abstraction, whereas Dog, Monkey, and Ninja are concrete implementations.
Its worth noting that interfaces only define instance members signatures on objects. In other words, they cannot define static member signatures or constructor signatures.

### What are interfaces used for and how to use them?

Interfaces are a mystery to newbie programmers (after all, what's the point of creating a type with no implementation?), however they are essential to many object-oriented programming techniques. Interfaces allow programmers to generalize functions to all classes which implement a particular functionality, which is described by the interface, even if those classes don't necessarily descend from one another.
For example, the Dog, Monkey, and Ninja classes defined above contain behavior that is shared, which we defined in the ILifeForm interface. As the code shows, how the individual classes talk or eat is not defined, but for each class that implements the interface we know that they can eat and speak and have a name. Now we can write a method that accepts just the interface ILifeForm and we need not worry about how it is implemented, if it is implemented (it always is, the compiler takes care of that) or what type of object it really is. Any other class that implements the same interface, regardless of its other methods, is then automatically supported by this method as well.
Note that in F#, interfaces are implemented explicitly, whereas in C# they are often implemented implicitly. As a consequence, to call a function or method that expects an interface, you have to make an explicit cast:
You can simplify this by letting the compiler help find the proper interface by using the _ placeholder:

### Implementing Interfaces with Object Expressions

Interfaces are extremely useful for sharing snippets of implementation logic between other classes, however it can be very cumbersome to define and implement a new class for ad hoc interfaces. Object expressions allow users to implement interfaces on anonymous classes using the following syntax:
Using a concrete example, the .NET BCL has a method called System.Array.Sort<T>(T array, IComparer<T>), where IComparer<T> exposes a single method called Compare. Let's say we wanted to sort an array on an ad hoc basis using this method; rather than litter our code with one-time use classes, we can use object expressions to define anonymous classes on the fly:

### Implementing Multiple Interfaces

Unlike inheritance, its possible to implement multiple interfaces:
Its just as easy to implement multiple interfaces in object expressions as well.

### Interface Hierarchies

Interfaces can extend other interfaces in a kind of interface hierarchy. For example:
When users create a concrete implementation of IFeline, they are required to provide implementations for all of the methods defined in the IAnimal, IComparable, and ILifeForm interfaces.
    Note: Interface hierarchies are occasionally useful, however deep, complicated hierarchies can be cumbersome to work with.

## Examples
### Generalizing a function to many classes

This program has the following types:
This program outputs the following:

### Using interfaces in generic type definitions

We can constrain generic types in class and function definitions to particular interfaces. For example, let's say that we wanted to create a binary tree which satisfies the following property: each node in a binary tree has two children, left and right, where all of the child nodes in left are less than all of its parent nodes, and all of the child nodes in right are greater than all of its parent nodes.
We can implement a binary tree with these properties defining a binary tree which constrains our tree to the IComparable<T> interface.
    Note: .NET has a number of interfaces defined in the BCL, including the very important IComparable<T> interface. IComparable exposes a single method, objectInstance.CompareTo(otherInstance), which should return 1, -1, or 0 when the objectInstance is greater than, less than, or equal to otherInstance respectively. Many classes in the .NET framework already implement IComparable, including all of the numeric data types, strings, and datetimes.
For example, using fsi:

### Simple dependency injection

Dependency injection refers to the process of supplying an external dependency to a software component. For example, let's say we had a class which, in the event of an error, sends an email to the network administrator, we might write some code like this:
The Process method creates an instance of Emailer, so we can say that the Processor class depends on the Emailer class.
Let's say we're testing our Processor class, and we don't want to be sending emails to the network admin all the time. Rather than comment out the lines of code we don't want to run while we test, its much easier to substitute the Emailer dependency with a dummy class instead. We can achieve that by passing in our dependency through the constructor:
Now, we create a processor and pass in the kind of FailureNotifier we're interested in. In test environments, we'd use new Processor(new DummyNotifier); in production, we'd use new Processor(new EmailNotifier) or new Processor(new LogfileNotifier(@"C:\log.txt")).
To demonstrate dependency injection using a somewhat contrived example, the following code in fsi shows how to hot swap one interface implementation with another:

# Events

Events allow objects to communicate with one another through a kind of synchronous message passing. Events are simply hooks to other functions: objects register callback functions to an event, and these callbacks will be executed when (and if) the event is triggered by some object.
For example, let's say we have a clickable button which exposed an event called Click. We can register a block of code, something like fun -> printfn "I've been clicked!", to the button's click event. When the click event is triggered, it will execute the block of code we've registered. If we wanted to, we could register an indefinite number of callback functions to the click event—the button doesn't care what code is trigged by the callbacks or how many callback functions are registered to its click event, it blindly executes whatever functions are hooked to its click event.
Event-driven programming is natural in GUI code, as GUIs tend to consist of controls which react and respond to user input. Events are, of course, useful in non-GUI applications as well. For example, if we have an object with mutable properties, we may want to notify another object when those properties change.

## Defining Events

Events are created and used through F#'s Event class. To create an event, use the Event constructor as follows:
To allow listeners to hook onto our event, we need to expose the nameChanged field as a public member using the event's Publish property:
Now, any object can listen to the changes on the person method. By convention and Microsoft's recommendation, events are usually named Verb or VerbPhrase, as well as adding tenses like Verbed and Verbing to indicate post- and pre-events.

## Adding Callbacks to Event Handlers

Its very easy to add callbacks to event handlers. Each event handler has the type IEvent<'T> which exposes several methods:
val Add : event:('T -> unit) -> unit
    Connect a listener function to the event. The listener will be invoked when the event is fired.
val AddHandler : 'del -> unit
    Connect a handler delegate object to the event. A handler can be later removed using RemoveHandler. The listener will be invoked when the event is fired.
val RemoveHandler : 'del -> unit
    Remove a listener delegate from an event listener store.
Here's an example program:
This program outputs the following:
    Note: When multiple callbacks are connected to a single event, they are executed in the order they are added. However, in practice, you should not write code with the expectation that events will trigger in a particular order, as doing so can introduce complex dependencies between functions. Event-driven programming is often non-deterministic and fundamentally stateful, which can occasionally be at odds with the spirit of functional programming. Its best to write callback functions which do not modify state, and do not depend on the invocation of any prior events.

## Working with EventHandlers Explicitly
### Adding and Removing Event Handlers

The code above demonstrates how to use the IEvent<'T>.add method. However, occasionally we need to remove callbacks. To do so, we need to work with the IEvent<'T>.AddHandler and IEvent<'T>.RemoveHandler methods, as well as .NET's built-in System.Delegate type.
The function person.NameChanged.AddHandler has the type val AddHandler : Handler<'T> -> unit, where Handler<'T> inherits from System.Delegate. We can create an instance of Handler as follows:
This program outputs the following:

### Defining New Delegate Types

F#'s event handling model is a little different from the rest of .NET. If we want to expose F# events to different languages like C# or VB.NET, we can define a custom delegate type which compiles to a .NET delegate using the delegate keyword, for example:
The convention obj * NameChangingEventArgs corresponds to the .NET naming guidelines which recommend that all events have the type val eventName : (sender : obj * e : #EventArgs) -> unit.

### Use existing .NET WPF Event and Delegate Types

Try using existing .NET WPF Event and Delegate, example, ClickEvent and RoutedEventHandler. Create F# Windows Application .NET project with referring these libraries (PresentationCore PresentationFramework System.Xaml WindowsBase). The program will display a button in a window. Clicking the button will display the button's content as string.

## Passing State To Callbacks

Events can pass state to callbacks with minimal effort. Here is a simple program which reads a file in blocks of characters:
This program has the following types:
Since our event has the type IEvent<int>, we can pass int data as state to listening callbacks. This program outputs the following:

## Retrieving State from Callers

A common idiom in event-driven programming is pre- and post-event handling, as well as the ability to cancel events. Cancellation requires two-way communication between an event handler and a listener, which we can easily accomplish through the use of ref cells or mutable members:
This program has the following types:
This program outputs the following:
If we need to pass a significant amount of state to listeners, then its recommended to wrap the state in an object as follows:
By convention, custom event parameters should inherit from System.EventArgs, and should have the suffix EventArgs.

## Using the Event Module

F# allows users to pass event handlers around as first-class values in fundamentally the same way as all other functions. The Event module has a variety of functions for working with event handlers:
val choose : ('T -> 'U option) -> IEvent<'del,'T> -> IEvent<'U> (requires delegate and 'del :> Delegate)
    Return a new event which fires on a selection of messages from the original event. The selection function takes an original message to an optional new message.
val filter : ('T -> bool) -> IEvent<'del,'T> -> IEvent<'T> (requires delegate and 'del :> Delegate)
    Return a new event that listens to the original event and triggers the resulting event only when the argument to the event passes the given function.
val listen : ('T -> unit) -> IEvent<'del,'T> -> unit (requires delegate and 'del :> Delegate)
    Run the given function each time the given event is triggered.
val map : ('T -> 'U) -> IEvent<'del,'T> -> IEvent<'U> (requires delegate and 'del :> Delegate)
    Return a new event which fires on a selection of messages from the original event. The selection function takes an original message to an optional new message.
val merge : IEvent<'del1,'T> -> IEvent<'del2,'T> -> IEvent<'T> (requires delegate and 'del1 :> Delegate and delegate and 'del2 :> Delegate)
    Fire the output event when either of the input events fire.
val pairwise : IEvent<'del,'T> -> IEvent<'T * 'T> (requires delegate and 'del :> Delegate)
    Return a new event that triggers on the second and subsequent triggerings of the input event. The Nth triggering of the input event passes the arguments from the N-1th and Nth triggering as a pair. The argument passed to the N-1th triggering is held in hidden internal state until the Nth triggering occurs. You should ensure that the contents of the values being sent down the event are not mutable. Note that many EventArgs types are mutable, e.g. MouseEventArgs, and each firing of an event using this argument type may reuse the same physical argument object with different values. In this case you should extract the necessary information from the argument before using this combinator.
val partition : ('T -> bool) -> IEvent<'del,'T> -> IEvent<'T> * IEvent<'T> (requires delegate and 'del :> Delegate
    Return a new event that listens to the original event and triggers the first resulting event if the application of the predicate to the event arguments returned true, and the second event if it returned false.
val scan : ('U -> 'T -> 'U) -> 'U -> IEvent<'del,'T> -> IEvent<'U> (requires delegate and 'del :> Delegate)
    Return a new event consisting of the results of applying the given accumulating function to successive values triggered on the input event. An item of internal state records the current value of the state parameter. The internal state is not locked during the execution of the accumulation function, so care should be taken that the input IEvent not triggered by multiple threads simultaneously.
val split : ('T -> Choice<'U1,'U2>) -> IEvent<'del,'T> -> IEvent<'U1> * IEvent<'U2> (requires delegate and 'del :> Delegate)
    Return a new event that listens to the original event and triggers the first resulting event if the application of the function to the event arguments returned a Choice2Of1, and the second event if it returns a Choice2Of2.
Take the following snippet:
We can rewrite this in a more functional style as follows:

# Modules and Namespaces

Modules and Namespaces are primarily used for grouping and organizing code.

## Defining Modules

No code is required to define a module. If a codefile does not contain a leading namespace or module declaration, F# code will implicitly place the code in a module, where the name of the module is the same as the file name with the first letter capitalized.
To access code in another module, simply use . notation: moduleName.member. Notice that this notation is similar to the syntax used to access static members—this is not a coincidence. F# modules are compiled as classes which only contain static members, values, and type definitions.
Let's create two files:
DataStructures.fs
Program.fs
This program outputs:
    Note: Remember, order of compilation matters in F#. Dependencies must come before dependents, so DataStructures.fs comes before Program.fs when compiling this program.
Like all modules, we can use the open keyword to give us access to the methods inside a module without fully qualifying the naming of the method. This allows us to revise Program.fs as follows:

### Submodules

Its very easy to create submodules using the module keyword:
Since the getRange method is under another module, the fully qualified name of this method is DataStructures.StackOps.getRange. We can use it as follows:
F# allows us to create a module and a type having the same name, for example the following code is perfectly acceptable:
    Note: Its possible to nest submodules inside other submodules. However, as a general principle, its best to avoid creating complex module hierarchies. Functional programming libraries tend to be very "flat" with nearly all functionality accessible in the first 2 or 3 levels of a hierarchy. This is in contrast to many other OO languages which encourage programmers to create deeply nested class libraries, where functionality might be buried 8 or 10 levels down the hierarchy.

### Extending Types and Modules

F# supports extension methods, which allow programmers to add new static and instance methods to classes and modules without inheriting from them.
Extending a Module
The Seq module contains several pairs of methods:
* iter/iteri
* map/mapi
Seq has a forall member, but does not have a corresponding foralli function, which includes the index of each sequence element. We add this missing method to the module simply by creating another module with the same name. For example, using fsi:
Extending a Type
The System.String has many useful methods, but let's say we thought it was missing a few important functions, Reverse and IsPalindrome. Since this class is marked as sealed or NotInheritable, we can't create a derived version of this class. Instead, we create a module with the new methods we want. Here's an example in fsi which demonstrates how to add new static and instance methods to the String class:

### Module Signatures

By default, all members in a module are accessible from outside the module. However, a module often contain members which should not be accessible outside itself, such as helper functions. One way to expose only a subset of a module's members is by creating a signature file for that module. (Another way is to apply .Net CLR access modifiers of public, internal, or private to individual declarations).
Signature files have the same name as their corresponding module, but end with a ".fsi" extension (f-sharp interface). Signature files always come before their implementation files, which have a corresponding ".fs" extension. For example:
DataStructures.fsi
DataStructures.fs
Program.fs
Since Stack.internal_head_tail is not defined in our interface file, the method is marked private and no longer accessible outside of the DataStructures module.
Module signatures are useful to building a code library's skeleton, however they have a few caveats. If you want to expose a class, record, or union in a module through a signature, then the signature file must expose all of the objects members, records fields, and union's cases. Additionally, the signature of the function defined in the module and it's corresponding signature in the signature file must match exactly. Unlike OCaml, F# does not allow a function in a module with the generic type 'a -> 'a -> 'a to be restricted to int -> int -> int in the signature file.

## Defining Namespaces

A namespace is a hierarchical categorization of modules, classes, and other namespaces. For example, the System.Collections namespace groups together all of the collections and data structures in the .NET BCL, whereas the System.Security.Cryptography namespace groups together all classes which provide cryptographic services.
Namespaces are primarily used to avoid name conflicts. For example, let's say we were writing an application incorporated code from several different vendors. If Vendor A and Vendor B both have a class called Collections.Stack, and we wrote the code let s = new Stack, how would the compiler know whether which stack we intended to create? Namespaces can eliminate this ambiguity by adding one more layer of grouping to our code.
Code is grouped under a namespace using the namespace keyword:
DataStructures.fsi
DataStructures.fs
Program.fs
Where is the DataStructures Module?
You may have expected the code in Program.fs above to open Princess.Collections.DataStructures rather than Princess.Collections. According to the F# spec, F# treats anonymous implementation files (which are files without a leading module or namespace declaration) by putting all code in an implicit module which matches the code's filename. Since we have a leading namespace declaration, F# does not create the implicit module.
.NET does not permit users to create functions or values outside of classes or modules. As a consequence, we cannot write the following code:
If we prefer to have a module called DataStructures, we can write this:
Or equivalently, we define a module and place it a namespace simultaneously using:

### Adding to Namespace from Multiple Files

Unlike modules and classes, any file can contribute to a namespace. For example:
DataStructures.fs
MoreDataStructures.fs
Since we have a leading namespace declaration in both files, F# does not create any implicit modules. The 'a stack, 'a tree, Stack, and Tree types are all accessible through the Princess.Collections namespace:
Program.fs

### Controlling Class and Module Accessibility

Unlike modules, there is no equivalent to a signature file for namespaces. Instead, the visibility of classes and submodules is controlled through standard accessibility modifiers:

# Units of Measure

Units of measure allow programmers to annotate floats and integers with statically-typed unit metadata. This can be handy when writing programs which manipulate floats and integers representing specific units of measure, such as kilograms, pounds, meters, newtons, pascals, etc. F# will verify that units are used in places where the programmer intended. For example, the F# compiler will throw an error if a float<m/s> is used where it expects a float<kg>.

## Use Cases
### Statically Checked Type Conversions

Units of measure are invaluable to programmers who work in scientific research, they add an extra layer of protection to guard against conversion related errors. To cite a famous case study, NASA's $125 million Mars Climate Orbiter project ended in failure when the orbiter dipped 90 km closer to Mars than originally intended, causing it to tear apart and disintegrate spectacularly in the Mars atmosphere. A post mortem analysis narrowed down the root cause of the problem to a conversion error in the orbiter's propulsion systems used to lower the spacecraft into orbit: NASA passed data to the systems in metric units, but the software expected data in Imperial units. Although there were many contributing project-management errors which resulted in the failed mission, this software bug in particular could have been prevented if the software engineers had used a type-system powerful enough to detect unit-related errors.

### Decorating Data With Contextual Information

In an article Making Code Look Wrong, Joel Spolsky describes a scenario in which, during the design of Microsoft Word and Excel, programmers at Microsoft were required to track the position of objects on a page using two non-interchangeable coordinate systems:
    In WYSIWYG word processing, you have scrollable windows, so every coordinate has to be interpreted as either relative to the window or relative to the page, and that makes a big difference, and keeping them straight is pretty important. [...]
    The compiler won’t help you if you assign one to the other and Intellisense won’t tell you bupkis. But they are semantically different; they need to be interpreted differently and treated differently and some kind of conversion function will need to be called if you assign one to the other or you will have a runtime bug. If you’re lucky. [...]
    In Excel’s source code you see a lot of rw and col and when you see those you know that they refer to rows and columns. Yep, they’re both integers, but it never makes sense to assign between them. In Word, I'm told, you see a lot of xl and xw, where xl means “horizontal coordinates relative to the layout” and xw means “horizontal coordinates relative to the window.” Both ints. Not interchangeable. In both apps you see a lot of cb meaning “count of bytes.” Yep, it’s an int again, but you know so much more about it just by looking at the variable name. It’s a count of bytes: a buffer size. And if you see xl = cb, well, blow the Bad Code Whistle, that is obviously wrong code, because even though xl and cb are both integers, it’s completely crazy to set a horizontal offset in pixels to a count of bytes.
In short, Microsoft depends on coding conventions to encode contextual data about a variable, and they depend on code reviews to enforce correct usage of a variable from its context. This works in practice, but its still possible for incorrect code to work its way it the product without the bug being detected for months.
If Microsoft were using a language with units of measure, they could have defined their own rw, col, xw, xl, and cb units of measure so that an assignment of the form int<xl> = int<cb> not only fails visual inspection, it doesn't even compile.

## Defining Units

New units of measure are defined using the Measure attribute:
Additionally, we can define types measures which are derived from existing measures as well:
    Important: Units of measure look like a data type, but they aren't. .NET's type system does not support the behaviors that units of measure have, such as being able to square, divide, or raise datatypes to powers. This functionality is provided by the F# static type checker at compile time, but units are erased from compiled code. Consequently, it is not possible to determine value's unit at runtime.
We can create instances of float and integer data which represent these units using the same notation we use with generics:
Notice the that F# automatically derives a new unit, m/s, for the value speed. Units of measure will multiply, divide, and cancel as needed depending on how they are used. Using these properties, it's very easy to convert between two units:
Units of measure are statically checked at compile time for proper usage. For example, if we use a measure where it isn't expected, we get a compilation error:
Units can be defined for integral types too:

## Dimensionless Values

A value without a unit is dimensionless. Dimensionless values are represented implicitly by writing them out without units (i.e. 7.0, -14, 200.5), or they can be represented explicitly using the <1> type (i.e. 7.0<1>, -14<1>, 200.5<1>).
We can convert dimensionless units to a specific measure by multiplying by 1<targetMeasure>. We can convert a measure back to a dimensionless unit by passing it to the built-in float or int methods:
Alternatively, its often easier (and safer) to divide away unneeded units:

## Generalizing Units of Measure

Since measures and dimensionless values are (or appear to be) generic types, we can write functions which operate on both transparently:
Since units are erased from compiled code, they are not considered a real data type, so they can't be used directly as a type parameter in generic functions and classes. For example, the following code will not compile:
F# does not infer that 'a is a unit of measure above, possibly because the following code appears correct, but it can be used in non-sensical ways:
The type 'a can be a unit of measure or a data type, but not both at the same time. F#'s type checker assumes 'a is a type parameter unless otherwise specified. We can use the [<Measure>] attribute to change the 'a to a unit of measure:

## F# PowerPack

The F# PowerPack (FSharp.PowerPack.dll) includes a number of predefined units of measure for scientific applications. These are available in the following modules:
* Microsoft.FSharp.Math.SI - a variety of predefined measures in the International System of Units (SI).
* Microsoft.FSharp.Math.PhysicalConstants - Fundamental physical constants with units of measure.

## External Resources

* Andrew Kennedy's 4-part tutorial on units of measure:
** Part 1: Introducing Units
** Part 2: Unit Conversions
** Part 3: Generic Units
** Part 4: Parameterized Types
* F# Units of Measure (MSDN)

# Caching

Caching is often useful to re-use data which has already been computed. F# provides a number of built-in techniques to cache data for future use.

## Partial Functions

F# automatically caches the value of any function which takes no parameters. When F# comes across a function with no parameters, F# will only evaluate the function once and reuse its value everytime the function is accessed. Compare the following:
Both functions accept and return the same values, but they have very different behavior. Here's a comparison of the output in fsi:
| isNebraskaCity_bad | isNebraskaCity_good |
| > let isNebraskaCity_bad city = let cities = printfn "Creating cities Set" ["Bellevue"; "Omaha"; "Lincoln"; "Papillion"] |> Set.of_list cities.Contains(city);; val isNebraskaCity_bad : string -> bool > isNebraskaCity_bad "Lincoln";; Creating cities Set val it : bool = true > isNebraskaCity_bad "Washington";; Creating cities Set val it : bool = false > isNebraskaCity_bad "Bellevue";; Creating cities Set val it : bool = true > isNebraskaCity_bad "St. Paul";; Creating cities Set val it : bool = false | > let isNebraskaCity_good = let cities = printfn "Creating cities Set" ["Bellevue"; "Omaha"; "Lincoln"; "Papillion"] |> Set.of_list fun city -> cities.Contains(city);; Creating cities Set val isNebraskaCity_good : (string -> bool) > isNebraskaCity_good "Lincoln";; val it : bool = true > isNebraskaCity_good "Washington";; val it : bool = false > isNebraskaCity_good "Bellevue";; val it : bool = true > isNebraskaCity_good "St. Paul";; val it : bool = false |
The implementation of isNebraskaCity_bad forces F# to re-create the internal set on each call. On the other hand, isNebraskaCity_good is a value initialized to the function fun city -> cities.Contains(city), so it creates its internal set once and reuses it for all successive calls.
    Note: Internally, isNebraskaCity_bad is compiled as a static function which constructs a set on every call. isNebraskaCity_good is compiled as a static readonly property, where the value is initialized in a static constructor.
This distinction is often subtle, but it can have a huge impact on an application's performance.

## Memoization

"Memoization" is a fancy word meaning that computed values are stored in a lookup table rather than recomputed on every successive call. Long-running pure functions (i.e. functions which have no side-effects) are good candidates for memoization. Consider the recursive definition for computing Fibonacci numbers:
Beyond fib 35I, the runtime of the function becomes unbearable. Each recursive call to the fib function throws away all of its intermediate calculations to fib(n - 1I) and fib(n - 2I), giving it a runtime complexity of about O(2^n). What if we kept all of those intermediate calculations around in a lookup table? Here's the memoized version of the fib function:
Much better! This version of the fib function runs almost instaneously. In fact, since we only calculate the value of any fib(n) precisely once, and dictionary lookups are an O(1) operation, this fib function runs in O(n) time.
Notice all of the memoization logic is contained in the fib function. We can write a more general function to memoize any function:
    Note: Its very important to remember that the implementation above is not thread-safe -- the dictionary should be locked before adding/retrieving items if it will be accessed by multiple threads.
    Additionally, although dictionary lookups occur in constant time, the hash function used by the dictionary can take an arbitrarily long time to execute (this is especially true with strings, where the time it takes to hash a string is proportional to its length). For this reason, it is wholly possible for a memoized function to have less performance than an unmemorized function. Always profile code to determine whether optimization is necessary and whether memoization genuinely improves performance.

## Lazy Values

The F# lazy data type is an interesting primitive which delays evaluation of a value until the value is actually needed. Once computed, lazy values are cached for reuse later:
F# uses some compiler magic to avoid evaluating the expression (printfn "I'm lazy"; 5 + 5) on declaration. Lazy values are probably the simplest form of caching, however they can be used to create some interesting and sophisticated data structures. For example, two F# data structures are implemented on top of lazy values, namely the F# Lazy List and Seq.cache method.
Lazy lists and cached sequences represent arbitrary sequences of potentially infinite numbers of elements. The elements are computed and cached the first time they are accessed, but will not be recomputed when the sequence is enumerated again. Here's a demonstration in fsi:

# Active Patterns

Active Patterns allow programmers to wrap arbitrary values in a union-like data structure for easy pattern matching. For example, its possible wrap objects with an active pattern, so that you can use objects in pattern matching as easily as any other union type.

## Defining Active Patterns

Active patterns look like functions with a funny name:
This function defines an ad hoc union data structure, where each union case namen is separated from the next by a | and the entire list is enclosed between (| and |) (humbly called "banana brackets"). In other words, the function does not have a simple name at all, it instead defines a series of union constructors.
A typical active pattern might look like this:
Even and Odd are union constructors, so our active pattern either returns an instance of Even or an instance of Odd. The code above is roughly equivalent to the following:
Active patterns can also define union constructors which take a set of parameters. For example, consider we can wrap a seq<'a> with an active pattern as follows:
This code is, of course, equivalent to the following:
You've probably noticed the immediate difference between active patterns and explicitly defined unions:
* Active patterns define an anonymous union, where the explicit union has a name (numKind, seqWrapper, etc.).
* Active patterns determine their constructor parameters using a kind of type-inference, whereas we need to explicitly define the constructor parameters for each case of our explicit union.

### Using Active Patterns

The syntax for using active patterns looks a little odd, but once you know what's going on, it's very easy to understand. Active patterns are used in pattern matching expressions, for example:
What's going on here? When the pattern matching function encounters Even, it calls (|Even|Odd|) with parameter in the match clause, it's as if you've written:
The parameter in the match clause is always passed as the last argument to the active pattern expression. Using our seq example from earlier, we can write the following:
Traditionally, seq's are resistant to pattern matching, but now we can operate on them just as easily as lists.

### Parameterizing Active Patterns

Its possible to pass arguments to active patterns, for example:
The single-case active pattern (|Contains|) wraps the String.Contains function. When we call Contains "kitty" true, F# passes "kitty" and the argument we're matching against to the (|Contains|) active pattern and tests the return value against the value true. The code above is equivalent to:
As you can see, the code using the active patterns is much cleaner and easier to read than the equivalent code using the explicitly defined union.
   Note: Single-case active patterns might not look terribly useful at first, but they can really help to clean up messy code. For example, the active pattern above wraps up the String.Contains method and allows us to invoke it in a pattern matching expression. Without the active pattern, pattern matching quickly becomes messy:

### Partial Active Patterns

A partial active pattern is a special class of single-case active patterns: it either returns Some or None. For example, a very handy active pattern for working with regex can be defined as follows:
This is equivalent to writing:
Using partial active patterns, we can test an input against any number of active patterns:
Partial active patterns don't constrain us to a finite set of cases like traditional unions do, we can use as many partial active patterns in match statement as we need.

## Additional Resources

* Introduction to Active Patterns (Internet Archive Wayback Machine) by Chris Smith
* Extensible Pattern Matching via Lightweight Language Extension by Don Syme

# Advanced Data Structures

F# comes with its own set of data structures, however its very important to know how to implement data structures from scratch.
Incidentally, hundreds of authors have written thousands of lengthy volumes on this single topic alone, so its unreasonable to provide a comprehensive picture of data structures in the short amount of space available for this book. Instead, this chapter is intended as a cursory introduction to the development of immutable data structures using F#. Readers are encouraged to use the resources listed at the bottom of this page for a more comprehensive treatment of algorithms and data structures.

## Stacks

F#'s built-in list data structure is essentially an immutable stack. While its certainly usable, for the purposes of writing exploratory code, we're going to implement a stack from scratch. We can represent each node in a stack using a simple union:
It's easy enough to create an instance of a stack using:
Each StackNode contains a value and a pointer to the next stack in the list. The resulting data structure can be diagrammed as follows:
We can create a boilerplate stack module as follows:
Let's say we wanted to add a few methods to our stack, such as a method which updates an item at a certain index. Since our nodes are immutable, we can't update our list in place; we need to copy all of the nodes up to the node we want to update.
So, we copy all of the nodes up to index 2 and reuse the remaining nodes. A function like this is very easy to write:
Appending items from one stack to the rear of another uses a similar technique. Since we can't modify stacks in place, we append two stacks by copying all of the nodes from the "front" stack and pointing the last copied node to the our "rear" stack, resulting in the following:
We can implement this function with minimal effort using the following:
Stacks are very easy to work with and implement. The principles behind copying nodes to "modify" stacks is fundamentally the same for all persistent data structures.
Complete Stack Module

## Queues
### Naive Queue

Queues aren't quite as straightforward as stacks. A naive queue can be implemented using a stack, with the caveat that:
* Items are always appended to the end of the list, and dequeued from the head of the stack.
* -OR- Items are prepended to the front of the stack, and dequeued by reversing the stack and getting its head.
We use an interface file to hide the Queue class's constructor. Although this technically satisfies the function of a queue, every dequeue is an O(n) operation where n is the number of items in the queue. There are lots of variations on the same approach, but these are often not very practical in practice. We can certainly improve on the implementation of immutable queues.

### Queue From Two Stacks

The implementation above isn't very efficient because it requires reversing our underlying data representation several times. Why not keep those reversed stacks around for future use? Rather than using one stack, we can have two stacks: a front stack f and a rear stack r.
Stack f holds items in the correct order, while stack r holds items in reverse order; this allows the first element in f to be the head of the queue, and the first element in r to be the last item in queue. So, a queue of the numbers 1 .. 6 might be represented with f = [1;2;3] and r = [6;5;4].
To enqueue a new item, prepend it to the front of r; to dequeue an item, pop it off f. Both enqueues and dequeues are O(1) operations. Of course, at some point, f will be empty and there will be no more items to dequeue; in this case, simply move all items from r to f and reverse the list. While the queue certainly has O(n) worst-case behavior, it has acceptable O(1) amortized (average case) bounds.
The code for this implementation is straight forward:
This is a simple, common, and useful implementation of an immutable queue. The magic is in the check function which maintains that f always contains items if they are available.
    Note: The queue's periodic O(n) worst case behavior can give it unpredictable response times, especially in applications which rely heavily on persistence since its possible to hit the pathological case each time the queue is accessed. However, this particular implementation of queues is perfectly adequate for the vast majority of applications which do not require persistence or uniform response times.
As shown above, we often want to wrap our underlying data structure in class for two reasons:
* To simplify the interface to the data structure. For example, clients neither know nor care that our queue uses two stacks; they only know that items in the queue obey the principle of first-in, first-out.
* To prevent clients from putting the underlying data in the data structure in an invalid state.
Beyond stacks, virtually all data structures are complex enough to require wrapping up class to hide away complex details from clients.

## Binary Search Trees

Binary search trees are similar to stacks, but each node points to two other nodes called the left and right child nodes:
Additionally, nodes in the tree are ordered in a particular way: each item in a tree is greater than all items in its left child node and less than all items in its right child node.
Since our tree is immutable, we "insert" into the tree by returning a brand new tree with the node inserted. This process is more efficient than it sounds: we copy nodes as we traverse down the tree, so we only copy nodes which are in the path of our node being inserted. Writing a binary search tree is relatively straightforward:
We're using an interface and a wrapper class to hide the implementation details of the tree from the user, otherwise the user could construct a tree which invalidates the specific ordering rules used in the binary tree.
This implementation is simple and it allows us to add and lookup any item in the tree in O(log n) best case time. However, it suffers from a pathological case: if we add items in sorted order, or mostly sorted order, then the tree can become heavily unbalanced. For example, the following code:
Results in this tree:
A tree like this isn't much better than our inefficient queue implementation above! Trees are most efficient when they have a minimum height and are as full as possible. Ideally, we'd like to represent the tree above as follows:
The minimum height of the tree is ceiling(log n + 1), where n is the number of items in the list. When we insert items into the tree, we want the tree to balance itself to maintain the minimum height. There are a variety of self-balancing tree implementations, many of which are easy to implement as immutable data structures.

### Red Black Trees

Red-black trees are self-balancing trees which attach a "color" attribute to each node in the tree. In addition to the rules defining a binary search tree, red-black trees must maintain the following set of rules:
* A node is either red or black.
* The root node is always black.
* No red node has a red child.
* Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.
We can augment our binary tree with a color field as follows:
When we insert into the tree, we need to rebalance the tree to restore the rules. In particular, we need to remove nodes with a red child. There are four cases where a red node may have a red child. They are depicted in the diagram below by the top, right, bottom, and left trees. The center tree is the balanced version.
We can modify our binary tree class as follows:
All of the magic that makes this tree work happens in the balance function. We're not performing any terribly complicated transformations to the tree, yet it comes out relatively balanced (in fact, the maximum depth of this tree is 2 * ceiling(log n + 1) ).

### AVL Trees

AVL trees are named after its two inventors, G.M. Adelson-Velskii and E.M. Landis. These trees are self-balancing because the heights of the two child subtrees of any node will only differ 0 or 1; therefore, these trees are said to be height-balanced.
An empty node in a tree has a height of 0; non-empty nodes have a height >= 1. We can store the height of each node in our tree definition:
The height of any node is equal to max(left height, right height) + 1. For convenience, we'll use the following constructor to create a tree node and initialize its height:
Inserting into an AVL tree is very similar to inserting into an unbalanced binary tree with one exception: after we insert a node, we use a series of tree rotations to re-balance the tree. Each node has an implicit property, its balance factor, which refers to the left-child's height minus the right-child's height; a positive balance factor indicates the tree is weighted on the left, negative indicates the tree is weighted on the right, otherwise the tree is balanced.
We only need to rebalance the tree when balance factor for a node is +/-2. There are four scenarios which can cause our tree to become unbalanced:
Left-left case: root balance factor = +2, left-childs balance factor = +1. Balanced by right-rotating the root node:
Left-right case: root balance factor = +2, right-child's balance factor = -1. Balanced by left-rotating the left child, then right-rotating the root (this operation is called a double right rotation):
Right-right case: root balance factor = -2, right-child's balance factor = -1. Balanced by left-rotating the root node:
Right-left case: root balance factor = -2, right-child's balance factor = +1. Balanced by right-rotating the right child, then left-rotating the root (this operation is called a double-left rotation):
With this in mind, its very easy to put together the rest of our AVL tree:
    Note: The [<GeneralizableValue>] attribute indicates to F# that the construct can give rise to generic code through type inference . Without the attribute, F# will infer the type of AvlTree.empty as the undefined type AvlTree<'_a>, resulting in a "value restriction" error at compilation.
    Optimization tip: The tree supports inserts and lookups in log(n) time, where n is the number of nodes in the tree. This is already pretty good, but we can make it faster by eliminating unnecessary comparisons. Notice when we insert a node into the left side of the tree, we can only add weight to the left child; however, the balance function checks both sides of the tree for each insert. By re-writing balance into a balance_left and balance_right function to handle, we can handle left- and right-child inserts separately. Similar optimizations are possible on the red-black tree implementation as well.
An AVL trees height is limited to 1.44 * log(n), whereas a red-black tree's height is limited to 2 * log(n). The AVL trees smaller height and more rigid balancing leads to slower insert/removal but faster retrieval than red-black trees. In practice, the difference will be hardly noticeable: a lookup on a 10,000,000 node AVL tree lookup requires at most 34 comparisons, compared to 47 comparisons on a red-black tree.

### Heaps

Binary search trees can efficiently find arbitrary elements in a set, however it can be occasionally useful to access the minimum element in set. Heaps are special data structure which satisfy the heap property: the value of every node is greater than the value of any of its child nodes. Additionally, we can keep the tree approximately balanced using the leftist property, meaning that the height of any left child heap is at least as large as its right sibling. We can hold the height of each tree in each heap node.
Finally, since heaps can be implemented as min- or max-heaps, where the root element will either be the largest or smallest element in the set, we support both types of heaps by passing in an ordering function into heap's constructor as such:
    Note: the functionality we gain by passing the comparer function into the BinaryHeap constructor approximates OCaml functors, although its not quite as elegant.
An interesting consequence of the leftist property is that elements along any path in a heap are stored in sorted order. This means we can merge any two heaps by merging their right spines and swapping children as necessary to restore the leftist property. Since each right spine contains at least as many nodes as the left spine, the height of each right spine is proportional to the logarithm of the number of elements in the heap, so merging two heaps can be performed in O(log n) time. We can implement all of the properties of our heap as follows:
This heap implements the IEnumerable<'a> interface, allowing us to iterate through it like a seq. In addition to the leftist heap shown above, its very easy to implement immutable versions of splay heaps, binomial heaps, Fibonacci heaps, pairing heaps, and a variety other tree-like data structures in F#.

## Lazy Data Structures

Its worth noting that some purely functional data structures above are not as efficient as their imperative implementations. For example, appending two immutable stacks x and y together takes O(n) time, where n is the number of elements in stack x. However, we can exploit laziness in ways which make purely functional data structures just as efficient as their imperative counterparts.
For example, its easy to create a stack-like data structure which delays all computation until its really needed:
In the example above, the append operation returns one node delays the rest of the computation, so appending two lists will occur in constant time. A printfn statement above has been added to demonstrate that we really don't compute appended values until the first time they're accessed:
Interestingly, the append method clearly runs in O(1) time because the actual appending operation is delayed until a user grabs the head of the list. At the same time, grabbing the head of the list may have the side effect of triggering, at most, one call to the append method without causing a monolithic rebuilding the rest of the data structure, so grabbing the head is itself an O(1) operation. This stack implementation supports supports constant-time consing and appending, and linear time lookups.
Similarly, implementations of lazy queues exists which support O(1) worst-case behavior for all operations.

## Additional Resources

* Purely Functional Data Structures by Chris Okasaki ISBN 978-0521663502. Highly recommended. Provides techniques and analysis of immutable data structures using SML.
* The Algorithm Design Manual by Steven S. Skiena ISBN 978-0387948607. Highly recommended. Provides language-agnostic description of a variety of algorithms, data structures, and techniques for solving hard problems in computer science.
* Tutorial on immutable data structures using C#:
** Kinds of Immutability
** A Simple Immutable Stack
** A Covariant Immutable Stack
** An Immutable Queue
** LOLZ!
** A Simple Binary Tree
** More on Binary Trees
** Even More on Binary Trees
** AVL Tree Implementation
** A Double-ended Queue
** A Working Double-ended Queue

# Reflection

Reflection allows programmers to inspect types and invoke methods of objects at runtime without knowing their data type at compile time.
At first glance, reflection seems to go against the spirit of ML as it is inherently not type-safe, so typing errors using reflection are not discovered until runtime. However, .NET's typing philosophy is best stated as static typing where possible, dynamic typing when needed, where reflection serves to bring in the most desirable behaviors of dynamic typing into the static typing world. In fact, dynamic typing can be a huge time saver, often promotes the design of more expressive APIs, and allows code to be refactored much further than possible with static typing.
This section is intended as a cursory overview of reflection, not a comprehensive tutorial.

## Inspecting Types

There are a variety of ways to inspect the type of an object. The most direct way is calling the .GetType method (inherited from System.Object) on any non-null object:
Its also possible to get type information without an actual object using the built-in typeof method:
object.GetType and typeof return an instance of System.Type, which has a variety of useful properties such as:
* val Name : string
    Returns the name of the type.
* val GetConstructors : unit -> ConstructorInfo array
    Returns an array of constructors defined on the type.
* val GetMembers : unit -> MemberInfo array
    Returns an array of members defined on the type.
* val InvokeMember : (name : string, invokeAttr : BindingFlags, binder : Binder, target : obj, args : obj) -> obj
    Invokes the specified member, using the specified binding constraints and matching the specified argument list

### Example: Reading Properties

The following program will print out the properties of any object passed into it:
This program outputs the following:

### Example: Setting Private Fields

In addition to discovering types, we can dynamically invoke methods and set properties:
Reflection is particularly remarkable in that it can read/write private fields, even on objects which appear to be immutable. In particular, we can explore and manipulate the underlying properties of an F# list:
The example above mutates the list in place and to produce a circularly linked list. In .NET, "immutable" doesn't really mean immutable and private members are mostly an illusion.
    Note: The power of reflection has definite security implications, but a full discussion of reflection security is far outside of the scope of this section. Readers are encouraged to visit the Security Considerations for Reflection article on MSDN for more information.

## Microsoft.FSharp.Reflection Namespace

While .NET's built-in reflection API is useful, the F# compiler performs a lot of magic which makes built-in types like unions, tuples, functions, and other built-in types appear strange using vanilla reflection. The Microsoft.FSharp.Reflection namespace provides a wrapper for exploring F# types.
Using fsi:

## Working With Attributes

.NET attributes and reflection go hand-in-hand. Attributes allow programmers to decorate classes, methods, members, and other source code with metadata used at runtime. Many .NET classes use attributes to annotate code in a variety of ways; it is only possible to access and interpret attributes through reflection. This section will provide a brief overview of attributes. Readers interested in a more complete overview are encouraged to read MSDN's Extending Metadata With Attributes series.
Attributes are defined using [<AttributeName>], a notation already seen in a variety of places in previous chapters of this book. The .NET framework includes a number of built-in attributes, including:
* System.ObsoleteAttribute - used to mark source code intended to be removed in future versions.
* System.FlagsAttribute - indicates that an enumeration can be treated as a bit field.
* System.SerializableAttribute - indicates that class can be serialized.
* System.Diagnostics.DebuggerStepThroughAttribute - indicates that the debugger should not step into a method unless it contains a break point.
We can create custom attributes by defining a new type which inherits from System.Attribute:
We can access attribute using reflection:
The MyAttribute class has the side-effect of printing to the console on instantiation, demonstrating that MyAttribute does not get constructed when instances of MyClass are created.

### Example: Encapsulating Singleton Design Pattern

Attributes are often used to decorate classes with any kind of ad-hoc functionality. For example, let's say we wanted to control whether single or multiple instances of classes are created based on an attribute:
This program outputs the following:
Using the attribute above, we've completely abstracted away the implementation details of the singleton design pattern, reducing it down to a single attribute. Its worth noting that the program above hard-codes a value of true or false into the attribute constructor; if we wanted to, we could pass a string representing a key from the application's config file and make class construction dependent on the config file.

# Computation Expressions

Computation expressions are easily the most difficult, yet most powerful language constructs to understand in F#.

## Monad Primer

Computation expressions are inspired by Haskell monads, which in turn are inspired by the mathematical concept of monads in category theory. To avoid all of the abstract technical and mathematical theory underlying monads, a "monad" is, in very simple terms, a scary sounding word which means execute this function and pass its return value to this other function.
    Note: The designers of F# use the term "computation expression" and "workflow" because it's less obscure and daunting than the word "monad", and because monad and computation expression, while similar, are not precisely the same thing. The author of this book prefers "monad" to emphasize the parallel between the F# and Haskell (and, strictly as an aside, it's just a neat sounding five-dollar word).
Monads in Haskell
Haskell is interesting because it's a functional programming language where all statements are executed lazily, meaning Haskell doesn’t compute values until they are actually needed. While this gives Haskell some unique features such as the capacity to define "infinite" data structures, it also makes it hard to reason about the execution of programs since you can't guarantee that lines of code will be executed in any particular order (if at all).
Consequently, it's quite a challenge to do things which need to be executed in a sequence, which includes any form of I/O, acquiring locks objects in multithreaded code, reading/writing to sockets, and any conceivable action which has a side-effect on any memory elsewhere in our application. Haskell manages sequential operations using something called a monad, which can be used to simulate state in an immutable environment.
Visualizing Monads with F#
To visualize monads, let's take some everyday F# code written in imperative style:
We can re-write the read_line and print_string functions to take an extra parameter, namely a function to execute once our computation completes. We’d end up with something that looks more like this:
If you can understand this much, then you can understand any monad.
Of course, it is perfectly reasonable to say what masochistic reason would anyone have for writing code like that? All it does it print out "Hello, Steve" to the console! After all, C#, Java, C++, or other languages we know and love execute code in exactly the order specified—in other words, monads solve a problem in Haskell which simply doesn't exist in imperative languages. Consequently, the monad design pattern is virtually unknown in imperative languages.
However, monads are occasionally useful for modeling computations which are difficult to capture in an imperative style.
The Maybe Monad
A well-known monad, the Maybe monad, represents a short-circuited computation which should "bail out" if any part of the computation fails. Using a simple example, let’s say we wanted to write a function which asks the user for 3 integer inputs between 0 and 100 (inclusive) -- if at any point, the user enters an input which is non-numeric or falls out of our range, the entire computation should be aborted. Traditionally, we might represent this kind of program using the following:
    Note: Admittedly, the simplicity of this program -- grabbing a few integers -- is ridiculous, and there are many more concise ways to write this code by grabbing all of the values up front. However, it might help to imagine that getNum was a relatively expensive operation (maybe it executes a query against a database, sends and receives data over a network, initializes a complex data structure), and the most efficient way to write this program requires us to bail out as soon as we encounter the first invalid value.
This code is very ugly and redundant. However, we can simplify this code by converting it to monadic style:
The magic is in the bind method. We extract the return value from our function input and pass it (or bind it) as the first parameter to rest.
Why use monads?
The code above is still quite extravagant and verbose for practical use, however monads are especially useful for modeling calculations which are difficult to capture sequentially. Multithreaded code, for example, is notoriously resistant to efforts to write in an imperative style; however it becomes remarkably concise and easy to write in monadic style. Let's modify our bind method above as follows:
Now our bind method will execute a function in its own thread. Using monads, we can write multithreaded code in a safe, imperative style. Here's an example in fsi demonstrating this technique:
Its interesting to notice that Google starts downloading on thread 5 and finishes on thread 11. Additionally, thread 11 is shared between Microsoft, Peta, and Google at some point. Each time we call bind, we pull a thread out of .NET's threadpool, when the function returns the thread is released back to the threadpool where another thread might pick it up again—its wholly possible for async functions to hop between any number of threads throughout their lifetime.
This technique is so powerful that it's baked into F# library in the form of the async workflow.

## Defining Computation Expressions

Computation expressions are fundamentally the same concept as seen above, although they hide the complexity of monadic syntax behind a thick layer of syntactic sugar. A monad is a special kind of class which must have the following methods: Bind, Delay, and Return.
We can rewrite our Maybe monad described earlier as follows:
We can test this class in fsi:

### Syntax Sugar

Monads are powerful, but beyond two or three variables, the number of nested functions becomes cumbersome to work with. F# provides syntactic sugar which allows us to write the same code in a more readable fashion. Workflows are evaluated using the form builder { comp-expr }. For example, the following pieces of code are equivalent:
| Sugared syntax | De-sugared syntax |
| let maybe = new MaybeBuilder let sugared = maybe { let x = 12 let! y = Some 11 let! z = Some 30 return x + y + z } | let maybe = new MaybeBuilder let desugared = maybe.Delay(fun -> let x = 12 maybe.Bind(Some 11, fun y -> maybe.Bind(Some 30, fun z -> maybe.Return(x + y + z) ) ) ) |
    Note: You probably noticed that the sugared syntax is strikingly similar to the syntax used to declare sequence expressions, seq { expr }. This is not a coincidence. In the F# library, sequences are defined as computation expressions and used as such. The async workflow is another computation expression you'll encounter while learning F#.
The sugared form reads like normal F#. The code let x = 12 behaves as expected, but what is let! doing? Notice that we say let! y = Some 11, but the value y has the type int option rather than int. The construct let! y = ... invokes a function called maybe.Bind(x, f), where the value y is bound to parameter passed into the f function.
Similarly, return ... invokes a function called maybe.Return(x). Several new keywords de-sugar to some other construct, including ones you've already seen in sequence expressions like yield and yield!, as well as new ones like use and use!.
This fsi sample shows how easy it is to use our maybe monad with computation expression syntax:
This code does the same thing as the desugared code, only its much much easier to read.

### Dissecting Syntax Sugar

According the F# spec, workflows may be defined with the following members:
| Member | Description |
| member Bind : M<'a> * ('a -> M<'b>) -> M<'b> | Required member. Used to de-sugar let! and do! within computation expressions. |
| member Return : 'a -> M<'a> | Required member. Used to de-sugar return within computation expressions. |
| member Delay : (unit -> M<'a>) -> M<'a> | Required member. Used to ensure side effects within a computation expression are performed when expected. |
| member Yield : 'a -> M<'a> | Optional member. Used to de-sugar yield within computation expressions. |
| member For : seq<'a> * ('a -> M<'b>) -> M<'b> | Optional member. Used to de-sugar for ... do ... within computation expressions. M<'b> can optionally be M<unit> |
| member While : (unit -> bool) * M<'a> -> M<'a> | Optional member. Used to de-sugar while ... do ... within computation expressions. M<'b> can optionally be M<unit> |
| member Using : 'a * ('a -> M<'b>) -> M<'b> when 'a :> IDisposable | Optional member. Used to de-sugar use bindings within computation expressions. |
| member Combine : M<'a> -> M<'a> -> M<'a> | Optional member. Used to de-sugar sequencing within computation expressions. The first M<'a> can optionally be M<unit> |
| member Zero : unit -> M<'a> | Optional member. Used to de-sugar empty else branches of if/then within computation expressions. |
| member TryWith : M<'a> -> M<'a> -> M<'a> | Optional member. Used to de-sugar empty try/with bindings within computation expressions. |
| member TryFinally : M<'a> -> M<'a> -> M<'a> | Optional member. Used to de-sugar try/finally bindings within computation expressions. |
These sugared constructs are de-sugared as follows:
| Construct | De-sugared Form |
| let pat = expr in cexpr | let pat = expr in cexpr |
| let! pat = expr in cexpr | b.Bind(expr, (fun pat -> cexpr)) |
| return expr | b.Return(expr) |
| return! expr | b.ReturnFrom(expr) |
| yield expr | b.Yield(expr) |
| yield! expr | b.YieldFrom(expr) |
| use pat = expr in cexpr | b.Using(expr, (fun pat -> cexpr)) |
| use! pat = expr in cexpr | b.Bind(expr, (fun x -> b.Using(x, fun pat -> cexpr)) |
| do! expr in cexpr | b.Bind(expr, (fun -> cexpr)) |
| for pat in expr do cexpr | b.For(expr, (fun pat -> cexpr)) |
| while expr do cexpr | b.While((fun -> expr), b.Delay( fun -> cexpr)) |
| if expr then cexpr1 else cexpr2 | if expr then cexpr1 else cexpr2 |
| if expr then cexpr | if expr then cexpr else b.Zero |
| cexpr1 cexpr2 | b.Combine(cexpr1, b.Delay(fun -> cexpr2)) |
| try cexpr with patn -> cexprn | b.TryWith(expr, fun v -> match v with (patn:ext) -> cexprn | _ raise exn) |
| try cexpr finally expr | b.TryFinally(cexpr, (fun -> expr)) |

## What are Computation Expressions Used For?

F# encourages a programming style called language oriented programming to solve problems. In contrast to general purpose programming style, language oriented programming centers around the programmers identifying problems they want to solve, then writing domain specific mini-languages to tackle the problem, and finally solve problem in the new mini-language.
Computation expressions are one of several tools F# programmers have at their disposal for designing mini-languages.
Its surprising how often computation expressions and monad-like constructs occur in practice. For example, the Haskell User Group has a collection of common and uncommon monads, including those which compute distributions of integers and parse text. Another significant example, an F# implementation of software transactional memory, is introduced on hubFS.

## Additional Resources

* Haskell.org: All About Monads - Another collection of monads in Haskell.

# Async Workflows

Async workflows allow programmers to convert single-threaded code into multi-threaded code with minimal code changes.

## Defining Async Workflows

Async workflows are defined using computation expression notation:
async { comp-exprs }
Here's an example using fsi:
Notice the return type of asyncAdd. It does not actually run a function; instead, it returns an async<int>, which is a special kind of wrapper around our function.

### The Async Module

The Async Module is used for operating on async<'a> objects. It contains several useful methods, the most important of which are:
member RunSynchronously : computation:Async<'T> * ?timeout:int -> 'T
    Run the asynchronous computation and await its result. If an exception occurs in the asynchronous computation then an exception is re-raised by this function. Run as part of the default AsyncGroup.
member Parallel : computationList:seq<Async<'T>> -> Async<'T array>
    Specify an asynchronous computation that, when run, executes all the given asynchronous computations, initially queueing each in the thread pool. If any raise an exception then the overall computation will raise an exception, and attempt to cancel the others. All the sub-computations belong to an AsyncGroup that is a subsidiary of the AsyncGroup of the outer computations.
member Start : computation:Async<unit> -> unit
    Start the asynchronous computation in the thread pool. Do not await its result. Run as part of the default AsyncGroup
Async.RunSynchronously is used to run async<'a> blocks and wait for them to return, Run.Parallel automatically runs each async<'a> on as many processors as the CPU has, and Async.Start runs without waiting for the operation to complete. To use the canonical example, downloading a web page, we can write code for downloading a web page asyncronously as follows in fsi:

### async<'a> Members

async<'a> objects are constructed from the AsyncBuilder, which has the following important members:
member Bind : p:Async<'a> * f:('a -> Async<'b>) -> Async<'b> / let!
    Specify an asynchronous computation that, when run, runs 'p', and when 'p' generates a result 'res', runs 'f res'.
member Return : v:'a -> Async<'a> / return
    Specify an asynchronous computation that, when run, returns the result 'v'
In other words, let! executes an async workflow and binds its return value to an identifier, return simply returns a result, and return! executes an async workflow and returns its return value as a result.
These primitives allow us to compose async blocks within one another. For example, we can improve on the code above by downloading a web page asyncronously and extracting its urls asyncronously as well:
Notice that let! takes an async<'a> and binds its return value to an identifier of type 'a. We can test this code in fsi:
What does let! do?
let! runs an async<'a> object on its own thread, then it immediately releases the current thread back to the threadpool. When let! returns, execution of the workflow will continue on the new thread, which may or may not be the same thread that the workflow started out on. As a result, async workflows tend to "hop" between threads, an interesting effect demonstrated explicitly here, but this is not generally regarded as a bad thing.

## Async Examples
### Parallel Map

Consider the function Seq.map. This function is synchronous, however there is no real reason why it needs to be synchronous, since each element can be mapped in parallel (provided we're not sharing any mutable state). Using a module extension, we can write a parallel version of Seq.map with minimal effort:
Parallel mapping can have a dramatic impact on the speed of map operations. We can compare serial and parallel mapping directly using the following:
This program has the following types:
This program outputs the following:
The code using pmap ran about 2.2x faster because web pages are downloaded in parallel, rather than serially.

## Concurrency with Functional Programming
### Why Concurrency Matters

For the first 50 years of software development, programmers could take comfort in the fact that computer hardware roughly doubled in power every 18 months. If a program was slow today, one could just wait a few months and the program would run at double the speed with no change to the source code. This trend continued well into the early 2000s, where commodity desktop machines in 2003 had more processing power than the fastest supercomputers in 1993. However, after the publication of a well-known article, The Free Lunch is Over: A Fundamental Turn Toward Concurrency in Software by Herb Sutter, processors have peaked at around 3.7 GHz in 2005. The theoretical cap in in computing speed is limited by the speed of light and the laws of physics, and we've very nearly reached that limit. Since CPU designers are unable to design faster CPUs, they have turned toward designing processors with multiple cores and better support for multithreading. Programmers no longer have the luxury of their applications running twice as fast with improving hardware—the free lunch is over.
Clockrates are not getting any faster, however the amount of data businesses process each year grows exponentially (usually at a rate of 10-20% per year). To meet the growing processing demands of business, the future of all software development is tending toward the development of highly parallel, multithreaded applications which take advantage of multicores processors, distributed systems, and cloud computing.

### Problems with Mutable State

Multithreaded programming has a reputation for being notoriously difficult to get right and having a rather steep learning curve. Why does it have this reputation? To put it simply, mutable shared state makes programs difficult to reason about. When two threads are mutating the same variables, it is very easy to put the variable in an invalid state.
Race Conditions
As a demonstration, here's how to increment a global variable using shared state (non-threaded version):
This works, but some programmer might notice that both calls to IncrGlobalCounter could be computed in parallel since there's no real reason to wait for one call to finish before the other. Using the .NET threading primitives in the System.Threading namespace, a programmer can re-write this as follows:
This program should do the same thing as the previous program, only it should run in ~1/2 the time. Here are the results of 5 test runs in fsi:
The program is computationally sound, but it produces a different result everytime its run. What happened?
It takes several machine instructions increment a decimal value. In particular, the .NET IL for incrementing a decimal looks like this:
Imagine that we have two threads calling this code (calls made by Thread1 and Thread2 are interleaved):
This kind of bug is called a race condition and it occurs all the time in multithreaded applications. Unlike normal bugs, race-conditions are often non-deterministic, making them extremely difficult to track down.
Usually, programmers solve race conditions by introducing locks. When an object is "locked", all other threads are forced to wait until the object is "unlocked" before they proceed. We can re-write the code above using a block access to the counter variable while each thread writes to it:
The lock guarantees each thread exclusive access to shared state and forces each thread to wait on the other while the code counter := !counter + 1m runs to completion. This function now produces the expected result.
Deadlocks
Locks force threads to wait until an object is unlocked. However, locks often lead to a new problem: Let's say we have ThreadA and ThreadB which operate on two corresponding pieces of shared state, StateA and StateB. ThreadA locks stateA and stateB, ThreadB locks stateB and stateA. If the timing is right, when ThreadA needs to access stateB, its waits until ThreadB unlocks stateB; when ThreadB needs to access stateA, it can't proceed either since stateA is locked by ThreadA. Both threads mutually block one another, and they are unable to proceed any further. This is called a deadlock.
Here's some simple code which demonstrates a deadlock:
These kinds of bugs occur all the time in multithreaded code, although they usually aren't quite as explicit as the code shown above.

### Why Functional Programming Matters

To put it bluntly, mutable state is enemy of multithreaded code. Functional programming often simplifies multithreading tremendously: since values are immutable by default, programmers don't need to worry about one thread mutating the value of shared state between two threads, so it eliminates a whole class of multithreading bugs related to race conditions. Since there are no race conditions, there's no reason to use locks either, so immutability eliminates another whole class of bugs related to deadlocks as well.

# MailboxProcessor

F#'s MailboxProcessor class is essentially a dedicated message queue running on its own logical thread of control. Any thread can send the MailboxProcessor a message asynchronously or synchronously, allowing threads to communicate between one another through message passing. The "thread" of control is actually a lightweight simulated thread implemented via asynchronous reactions to messages. This style of message-passing concurrency is inspired by the Erlang programming language.

## Defining MailboxProcessors

MailboxProcessors are created using the MailboxProcessor.Start method which has the type Start : initial:(MailboxProcessor<'msg> -> Async<unit>) * ?asyncGroup:AsyncGroup -> MailboxProcessor<'msg>:
The value inbox has the type MailboxProcessor<'msg> and represents the message queue. The method inbox.Receive dequeues the first message from the message queue and binds it to the msg identifier. If there are no messages in queue, Receive releases the thread back to the threadpool and waits for further messages. No threads are blocked while Receive waits for further messages.
We can experiment with counter in fsi:

## MailboxProcessor Methods

There are several useful methods in the MailboxProcessor class:
static member Start : initial:(MailboxProcessor<'msg> -> Async<unit>) * ?asyncGroup:AsyncGroup -> MailboxProcessor<'msg>
    Create and start an instance of a MailboxProcessor. The asynchronous computation executed by the processor is the one returned by the 'initial' function.
member Post : message:'msg -> unit
    Post a message to the message queue of the MailboxProcessor, asynchronously.
member PostAndReply : buildMessage:(AsyncReplyChannel<'reply> -> 'msg) * ?timeout:int * ?exitContext:bool -> 'reply
    Post a message to the message queue of the MailboxProcessor and await a reply on the channel. The message is produced by a single call to the first function which must build a message containing the reply channel. The receiving MailboxProcessor must process this message and invoke the Reply method on the reply channel precisely once.
member Receive : ?timeout:int -> Async<'msg>
    Return an asynchronous computation which will consume the first message in arrival order. No thread is blocked while waiting for further messages. Raise a TimeoutException if the timeout is exceeded.

## Two-way Communication

Just as easily as we can send messages to MailboxProcessors, a MailboxProcessor can send replies back to consumers. For example, we can interrogate the value of a MailboxProcessor using the PostAndReply method as follows:
The msg union wraps two types of messages: we can tell the MailboxProcessor to increment, or have it send its contents to a reply channel. The type AsyncReplyChannel<'a> exposes a single method, member Reply : 'reply -> unit. We can use this class in fsi as follows:
Notice that PostAndReply is a syncronous method.

### Encapsulating MailboxProcessors with Objects

Often, we don't want to expose the implementation details of our classes to consumers. For example, we can re-write the example above as a class which exposes a few select methods:

## MailboxProcessor Examples
### Prime Number Sieve

Rob Pike delivered a fascinating presentation at a Google TechTalk on the NewSqueak programming language. NewSqueak's approach to concurrency uses channels, analogous to MailboxProcessors, for inter-thread communication. Toward the end of the presentation, he demonstrates how to implement a prime number sieve using these channels. The following is an implementation of prime number sieve based on Pike's NewSqueak code:
counter represents an infinite list of numbers from n..infinity.
filter is simply a filter for another MailboxProcessor. Its analogous to Seq.filter.
processor is essentially an iterative filter: we seed our prime list with the first prime, 2 and a infinite list of numbers from 3..infinity. Each time we process a message, we return the prime number, then replace our infinite list with a new list which filters out all numbers divisible by our prime. The head of each new filtered list is the next prime number.
So, the first time we call Next, we get back a 2 and replace our infinite list with all numbers not divisible by two. We call next again, we get back the next prime, 3, and filter our list again for all numbers divisible by 3. We call next again, we get back the next prime, 5 (we skip 4 since its divisible by 2), and filter all numbers divisible by 5. This process repeats indefinitely. The end result is a prime number sieve with an identical implementation to the Sieve of Eratosthenes.
We can test this class in fsi:

# Lexing and Parsing

Lexing and parsing is a very handy way to convert source-code (or other human-readable input which has a well-defined syntax) into an abstract syntax tree (AST) which represents the source-code. F# comes with two tools, FsLex and FsYacc, which are used to convert input into an AST.
FsLex and FsYacc have more or less the same specification as OCamlLex and OCamlYacc, which in turn are based on the Lex and Yacc family of lexer/parser generators. Virtually all material concerned with OCamlLex/OCamlYacc can transfer seamlessly over to FsLex/FsYacc. With that in mind, SooHyoung Oh's OCamlYacc tutorial and companion OCamlLex Tutorial are the single best online resources to learn how to use the lexing and parsing tools which come with F# (and OCaml for that matter!).

## Lexing and Parsing from a High-Level View

Transforming input into a well-defined abstract syntax tree requires (at minimum) two transformations:
* A lexer uses regular expressions to convert each syntactical element from the input into a token, essentially mapping the input to a stream of tokens.
* A parser reads in a stream of tokens and attempts to match tokens to a set of rules, where the end result maps the token stream to an abstract syntax tree.
It is certainly possible to write a lexer which generates the abstract syntax tree directly, but this only works for the most simplistic grammars. If a grammar contains balanced parentheses or other recursive constructs, optional tokens, repeating groups of tokens, operator precedence, or anything which can't be captured by regular expressions, then it is easiest to write a parser in addition to a lexer.
With F#, it is possible to write custom file formats, domain specific languages, and even full-blown compilers for your new language.

## Extended Example: Parsing SQL

The following code will demonstrate step-by-step how to define a simple lexer/parser for a subset of SQL. If you're using Visual Studio, you should add a reference to FSharp.PowerPack.dll to your project. If you're compiling on the commandline, use the -r flag to reference the aforemented F# powerpack assembly.

### Step 1: Define the Abstract Syntax Tree

We want to parse the following SQL statement:
This is a pretty simple query, and while it doesn't demonstrate everything you can do with the language, it's a good start. We can model everything in this query using the following definitions in F#:
A record type neatly groups all of our related values into a single object. When we finish our parser, it should be able to convert a string in an object of type sqlStatement.

### Step 2: Define the parser tokens

A token is any single identifiable element in a grammar. Let's look at the string we're trying to parse:
So far, we have several keywords (by convention, all keywords are uppercase): SELECT, FROM, LEFT, INNER, RIGHT, JOIN, ON, WHERE, AND, OR, ORDER, BY, ASC, DESC, and COMMA.
There are also a few comparison operators: EQ, GT, GE, LT, LE.
We also have non-keyword identifiers composed of strings and numeric literals. which we’ll represent using the keyword ID, INT, FLOAT.
Finally, there is one more token, EOF, which indicates the end of our input stream.
Now we can create a basic parser file for FsYacc, name the file SqlParser.fsp:
This is boilerplate code with the section for tokens filled in.
Compile the parser using the following command line: fsyacc SqlParser.fsp
    Tips:
   * If you haven't done so already, you should add the F# bin directory to your PATH environment variable.
   * If you're using Visual Studio, you can automatically generate your parser code on each compile. Right-click on your project file and choose "Properties". Navigate to the Build Events tab, and add the following to the 'Pre-build event command line' and use the following: fsyacc "$(ProjectDir)SqlParser.fsp". Also remember to exclude this file from the build process: right-click the file, choose "Properties" and select "None" against "Build Action".
If everything works, FsYacc will generate two files, SqlParser.fsi and SqlParser.fs. You'll need to add these files to your project if they don't already exist. If you open the SqlParser.fsi file, you'll notice the tokens you defined in your .fsl file have been converted into a union type.

### Step 3: Defining the lexer rules

Lexers convert text inputs into a stream of tokens. We can start with the following boiler plate code:
This is not "real" F# code, but rather a special language used by FsLex.
The let bindings at the top of the file are used to define regular expression macros. eof is a special marker used to identify the end of a string buffer input.
rule ... = parse ... defines our lexing function, called tokenize above. Our lexing function consists of a series of rules, which has two pieces: 1) a regular expression, 2) an expression to evaluate if the regex matches, such as returning a token. Text is read from the token stream one character at a time until it matches a regular expression and returns a token.
We can fill in the remainder of our lexer by adding more matching expressions:
Notice the code between the {'s and }'s consists of plain old F# code. Also notice we are returning the same tokens (INT, FLOAT, COMMA and EOF) that we defined in SqlParser.fsp. As you can probably infer, the code lexeme lexbuf returns the string our parser matched. The tokenize function will be converted into function which has a return type of SqlParser.token.
We can fill in the rest of the lexer rules fairly easily:
Notice we've created a few maps, one for keywords and one for operators. While we certainly can define these as rules in our lexer, its generally recommended to have a very small number of rules to avoid a "state explosion".
To compile this lexer, execute the following code on the commandline: fslex SqlLexer.fsl. (Try adding this file to your project's Build Events as well.) Then, add the file SqlLexer.fs to the project. We can experiment with the lexer now with some sample input:
This program will print out a list of tokens matched by the string above.

### Step 4: Define the parser rules

A parser converts a stream of tokens into an abstract syntax tree. We can modify our boilerplate parser as follows (will not compile):
Let's examine the start: function. You can immediately see that we have a list of tokens which gives a rough outline of a select statement. In addition to that, you can see the F# code contained between {'s and }'s which will be executed when the code successfully matches—in this case, its returning an instance of the Sql.sqlStatement record.
The F# code contains "$1", "$2", :$3", etc. which vaguely resembles regex replace syntax. Each "$#" corresponds to the index (starting at 1) of the token in our matching rule. The indexes become obvious when they’re annotated as follows:
So, the start rule breaks our tokens into a basic shape, which we then use to map to our sqlStatement record. You're probably wondering where the columnList, joinList, whereClause, and orderByClause come from—these are not tokens, but are rather additional parse rules which we'll have to define. Let’s start with the first rule:
columnList matches text in the style of "a, b, c, ... z" and returns the results as a list. Notice this rule is defined recursively (also notice the order of rules is not significant). FsYacc's match algorithm is "greedy", meaning it will try to match as many tokens as possible. When FsYacc receives an ID token, it will match the first rule, but it also matches part of the second rule as well. FsYacc then performs a one-token lookahead: it the next token is a COMMA, then it will attempt to match additional tokens until the full rule can be satisfied.
    Note: The definition of columnList above is not tail recursive, so it may throw a stack overflow exception for exceptionally large inputs. A tail recursive version of this rule can be defined as follows:
    The tail-recursive version creates the list backwards, so we have to reverse when we return our final output from the parser.
We can treat the JOIN clause in the same way, however its a little more complicated:
joinList is defined in terms of several functions. This results because there are repeating groups of tokens (such as multiple tables being joined) and optional tokens (the optional "ON" clause). You've already seen that we handle repeating groups of tokens using recursive rules. To handle optional tokens, we simply break the optional syntax into a separate function, and create an empty rule to represent 0 tokens.
With this strategy in mind, we can write the remaining parser rules:

### Step 5: Piecing Everything Together

Here is the complete code for our lexer/parser:
SqlParser.fsp
SqlLexer.fsl
Program.fs
Altogether, our minimal SQL lexer/parser is about 150 lines of code (including non-trivial lines of code and whitespace). I'll leave it as an exercise for the reader to implement the remainder of the SQL language spec.
2011-03-06: I tried the above instructions with VS2010 and F# 2.0 and PowerPack 2.0. I had to make a few changes:
* Add "module SqlLexer" on the 2nd line of SqlLexer.fsl
* Change Map.of_list to Map.ofList
* Add " --module SqlParser" to the command line of fsyacc
* Add FSharp.PowerPack to get Lexing module
2011-07-06: (Sjuul Janssen) These where the steps I had to take in order to make this work.
If you get the message "Expecting a LexBuffer<char> but given a LexBuffer<byte> The type 'char' does not match the type 'byte'"
* Add "fslex.exe "$(ProjectDir)SqlLexer.fsl" --unicode" to the pre-build
* in program.fs change "let lexbuf = Lexing.from_string x" to "let lexbuf = Lexing.LexBuffer<_>.FromString x"
* in SqlLexer.fsi change "lexeme lexbuf" to "LexBuffer<_>.LexemeString lexbuf"
If you get the message that some module doesn't exist or that some module is declared multiple times. Make sure that in the solution explorer the files come in this order:
* Sql.fs
* SqlParser.fsp
* SqlLexer.fsl
* SqlParser.fsi
* SqlParser.fs
* SqlLexer.fs
* Program.fs
If you get the message "Method not found: 'System.Object Microsoft.FSharp.Text.Parsing.Tables`1.Interpret(Microsoft.FSharp.Core.FSharpFunc`2<Microsoft.FSharp.Text.Lexing.LexBuffer`1<Byte>,!0>, ..." Go to http://www.microsoft.com/download/en/details.aspx?id=15834 and reinstall Visual Studio 2010 F# 2.0 Runtime SP1 (choose for repair)
2011-07-06: (mkduffi) Could someone please provide a sample project. I have followed all of your changes but still can not build. Thanks.

### Sample

https://github.com/obeleh/FsYacc-Example
2011-07-07 (mkduffi) Thanks for posting the sample. Here is what I did to the Program.fs file:
I added a C# console project for testing and this is what is in the Program.cs file:
I had to add the YaccSample project reference as well as a reference to the FSharp.Core assembly to get this to work.
If anyone could help me figure out how to support table aliases that would be awesome.
Thanks
2011-07-08 (Sjuul Janssen) Contact me through my github account. I'm working on this and some other stuff.

# Notes for Contributors

Would-be contributors are asked to observe the following:
* We aim to present functional programming in F# in a simple manner. Many texts go into great detail about the theoretical aspects of FP (e.g. lambda calculus) fairly early on which is :
** distracting to beginners who assume that functional programming is for "boffins" only.
** unnecessary for learning how to use functional programming techniques.
* Ensure that you only use a language construct or concept after it has been explained. It is the task of any tutorial to split things up into digestable chunks. This may mean explaining or demonstrating things in a clumsier or less general way than you would like. So be it.
* Do not treat the existing text or structure as sacrosanct. If it would be better done another way then by all means do it. Remember that WikiBooks are under version control, so any mistake can always be backed out. (Having said that, major changes should probably be discussed first).
Additionally topics should be organized in a way that makes sense to first-time programmers and those who have no prior experience with functional programming languages. In particular:
* Readers should be able to start at the beginning of this book and understand each section. No page should reference code or language constructs before they are properly introduced.
* Each section should build on prior sections. In other words, this book is meant to be read in serial format: from start to finish. Readers are not expected to understand code or concepts by skipping over material.
* An emphasis should be placed on explaining writing F# code properly, rather than on syntax alone. This is extremely important, but unfortunately overlooked in many programming tutorials on the web. There's no real point learning F# if programmers only intend to transcribe C++ in a different syntax; mastering this language means mastering its idioms and functional programming style.
* Its good for articles to have a high density of short, explanatory code samples. Always accompany new concepts with code that that reader can experiment with.
The text of this page is adapted from the page for Haskell.

# Acknowledgments

The initial inspiration for this WikiBook came from reading the Haskell book.

# Exercise Solutions

This section holds the solutions to the exercises in this book.
The solutions are on separate pages to ensure that you don't inadvertently see the solution to the next problem - which would spoil all the fun!

## Basic F#
# License

F# is distributed under the Apache License.