F Sharp Programming/Print version

From Wikibooks, open books for an open world
< F Sharp Programming
Jump to: navigation, search


F Sharp Programming

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

Permission is granted to copy, distribute, and/or modify this document under the terms of the Creative Commons Attribution-ShareAlike 3.0 License.


Contents

Preface

  Index Next: Introduction
F# : Preface


How This Book Came To Be[edit]

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 Internet.

  Index Next: Introduction



Introduction

Previous: Preface Index Next: Getting Set Up
F# : Introduction


Introducing F#[edit]

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).

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#[edit]

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.[1] 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#?[edit]

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[edit]

Previous: Preface Index Next: Getting Set Up



Getting Set Up

Previous: Introduction Index Next: Basic Concepts
F# : Getting Set Up


Windows[edit]

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[edit]

F# can integrate with existing installations of Visual Studio 2008 and is included with Visual Studio 2010. Alternatively, users can download Visual Studio Express or Community for free, which will provide an F# pioneer with everything she 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. Afterwards, download the latest version of F# from the F# homepage on Microsoft Research, then execute the installation wizard. Users should also consider downloading and installing the F# PowerPack, which contains handy extensions to the F# core library.

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 2012 the easiest way to get going is to install Visual Studio 2012 for Web at [1] (even if you want to do desktop solution). You can then install "F# Tools for Visual Studio Express 2012 for Web" from [2]. Once this is done you can create F# projects. Search Nuget for additional F# project types.

Testing the Install[edit]

Hello World executable[edit]

Lets create the Hello World standalone application.

Create a text file called hello.fs containing the following code:

(* filename: hello.fs *)
let _ = printf "Hello world"

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:

fsc -o hello.exe hello.fs

Now you can run hello.exe to produce the expected output.

F# Interactive Environment[edit]

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:

Microsoft F# Interactive, (c) Microsoft Corporation, All Rights Reserved
F# Version 1.9.6.2, compiling for .NET Framework Version v2.0.50727

Please send bug reports to fsbugs@microsoft.com
For help type #help;;

>

We can try some basic F# variable assignment (and some basic maths).

> let x = 5;;
val x : int
 
> let y = 20;;
val y : int

> y + x;;
val it : int = 25

Finally we quit out of the interactive environment

> #quit;;

Misc.[edit]

Adding to the PATH Environment Variable[edit]

  1. Go to the Control Panel and choose System.
  2. The System Properties dialog will appear. Select the Advanced tab and click the "Environment Variables...".
  3. In the System Variables section, select the Path variable from the list and click the "Edit..." button.
  4. In the Edit System Variable text box append a semicolon (;) followed by the executable path (e.g. ;C:\fsharp\bin\)
  5. Click on the "OK" button
  6. Click on the "OK" button
  7. 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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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.

Previous: Introduction Index Next: Basic Concepts



Basic Concepts

Previous: Getting Set Up Index Next: Values and Functions
F# : 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[edit]

Fundamental Data Types and Type System[edit]

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:

> let x = 5;;

val x : int = 5

> let y = 6L;;

val y : int64 = 6L

> let z = x + y;;

  let z = x + y;;
  ------------^

stdin(5,13): error FS0001: The type 'int64' does not match the type 'int'
> let z = (int64 x) + y;;

val z : int64 = 11L

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[edit]

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:

let average a b = (a + b) / 2.0

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:

> let add x y = x + y;;
val add : int -> int -> int

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:

> let add (x : float) (y : float) = x + y;;
val add : float -> float -> float

Pattern Matching[edit]

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:

type Proposition =  // type with possible expressions ... note recursion for all expressions except True
    | True          // essentially this is defining boolean logic
    | Not of Proposition
    | And of Proposition * Proposition
    | Or of Proposition * Proposition
    
let rec eval x =
    match x with
    | True -> true // syntax: Pattern-to-match -> Result
    | Not(prop) -> not (eval prop)
    | And(prop1, prop2) -> (eval prop1) && (eval prop2)
    | Or(prop1, prop2) -> (eval prop1) || (eval prop2)
    
let shouldBeFalse = And(Not True, Not True)
    
let shouldBeTrue = Or(True, Not True)
    
let complexLogic = 
    And(And(True,Or(Not(True),True)),
        Or(And(True, Not(True)), Not(True)) )
        
printfn "shouldBeFalse: %b" (eval shouldBeFalse)    // prints False
printfn "shouldBeTrue: %b" (eval shouldBeTrue)      // prints True
printfn "complexLogic: %b" (eval complexLogic)      // prints False

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[edit]

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[edit]

The first mistake a newcomer to functional programming makes is thinking that the let construct is equivalent to assignment. Consider the following code:

let a = 1
(* a is now 1 *)
let a = a + 1
(* in F# this throws an error:  Duplicate definition of value 'a' *)

On the surface, this looks exactly like the familiar imperative pseudocode:

 a = 1
 // a is 1
 a = a + 1
 // a is 2

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:

let a = 1 in  
  ((* a stands for 1 here *);
   (let a = (* a still stands for 1 here *) a + 1 in (* a stands for 2 here *));
   (* a stands for 1 here, again *))

Indeed the code

let a = 1 in  
  (printfn "%i" a;
   (let a = a + 1 in printfn "%i" a);
   printfn "%i" a)

prints out

 1 
 2
 1

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?[edit]

Imperative programming languages tend to iterate through collections with loops:

void ProcessItems(Item[] items)
{
    for(int i = 0; i < items.Length; i++)
    {
        Item myItem = items[i];
        proc(myItem); // process myItem
    }
}

This admits a direct translation to F# (type annotations for i and item are omitted because F# can infer them):

let processItems (items : Item []) = 
  for i in 0 .. items.Length - 1 do
    let item = items.[i] in
      proc item

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:

let rec processItems = function
  | []       -> ()  // empty list: end recursion
  | head :: tail -> // split list in first item (head) and rest (tail)
      proc head;
      processItems tail // recursively enumerate list

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):

let rec processItems proc = function
  | []       -> ()
  | hd :: tl ->
      proc hd;
      processItems proc tl // recursively enumerate list

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:

for item in collection do 
  process item

Function Composition Rather than Inheritance[edit]

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[edit]

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 is a fundamental difference between variables and functions.

Dim myVal as Integer
Dim myParam as Integer
myParam = 2
Public Function MyFunc(Dim param as Integer)
    MyFunc = (param * 2) + 7
End Function
myVal = MyFunc(myParam)

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 sub-routine (which is essentially 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 sub-routine
  • return a function as the result of another function

Structure of F# Programs[edit]

A simple, non-trivial F# program has the following parts:

open System
 
(* This is a
multi-line comment *)
 
// This is a single-line comment
 
let rec fib = function
    | 0 -> 0
    | 1 -> 1
    | n -> fib (n - 1) + fib (n - 2)
 
let main() =
    Console.WriteLine("fib 5: {0}", (fib 5))
 
main()

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:

let main() =
    (*
       ...
       This is the main loop.
       ...
    *)

main()
(*
   This is a top-level statement because it's
   not nested in any other functions. This calls 
   into the main method to run the main loop.
*)

In general, there is no explicit entry point in an F# application. Rather, when an F# application is compiled, the last file passed to the compiler is assumed to be the entry point, and the compiler executes all top-level statements in the file from top to bottom. While its possible to have any number of top-level statements in the entry point of a F# program, well-written F# only has a single top-level statement which calls the main loop of the application.

Previous: Getting Set Up Index Next: Values and Functions



Values and Functions

Previous: Basic Concepts Index Next: Pattern Matching Basics
F# : Declaring 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[edit]

The most ubiquitous, familiar keyword in F# is the let keyword, which allows programmers to declare functions and variables in their applications.

For example:

let x = 5

This declares a variable called x and assigns it the value 5. Naturally, we can write the following:

let x = 5
let y = 10
let z = x + y

z now holds the value 15.

A complete program looks like this:

let x = 5
let y = 10
let z = x + y

printfn "x: %i" x
printfn "y: %i" y
printfn "z: %i" z

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:

x: 5
y: 10
z: 15

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[edit]

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[edit]

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:

let add x y = x + y

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:

let z = add 5 10

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:

let add x y = x + y

let sub x y = x - y

let printThreeNumbers num1 num2 num3 =
    printfn "num1: %i" num1
    printfn "num2: %i" num2
    printfn "num3: %i" num3

printThreeNumbers 5 (add 10 7) (sub 20 8)

This program outputs:

num1: 5
num2: 17
num3: 12

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[edit]

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:

let sign num =
    if num > 0 then "positive"
    elif num < 0 then "negative"
    else "zero"

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:

string Sign(int num)
{
    if (num > 0) return "positive";
    else if (num < 0) return "negative";
    else return "zero";
}

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:

let sign num =
    if num > 0 then "positive"
    elif num < 0 then "negative"
    else 0

If you run this code in fsi, you get the following error message:

> let sign num =
    if num > 0 then "positive"
    elif num < 0 then "negative"
    else 0;;

      else 0;;
  ---------^
stdin(7,10): error FS0001: This expression was expected to have type    string    but here has type    int   

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:

let helloWorld () = printfn "hello world"

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[edit]

All functions and values in F# have a data type. Open F# Interactive and type the following:

> let addAndMakeString x y = (x + y).ToString();;

F# reports the data type using chained arrow notation as follows:

val addAndMakeString : x:int -> y:int -> string

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[edit]

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

  1. 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).
  2. 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:

let addTwoNumbers x y = x + y

this type has the signature of

int -> int -> int

then this function:

let add5ToNumber = addTwoNumbers 5

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.

> let z = add5ToNumber 6;;

val z : int = 11

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

> let holdOn = addTwoNumbers 7;;

val holdOn : (int -> int)

> let okDone = holdOn 8;;

val okDone : int = 15

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

f : int -> int -> int

is actually (when taking into consideration the implicit currying):

// curried version pseudo-code
f: int -> (int -> int)

In other words, f is a function that takes an int and returns a function that takes an int and returns an int. Moreover,

f: int -> int -> int -> int

is a simplified shorthand for

// curried version pseudo-code
f: int -> (int -> (int -> int))

or, in very difficult to decode English: f is a function that takes an int and returns a function that takes an int that returns a function that takes an int and returns an int. Yikes!

Nested Functions[edit]

F# allows programmers to nest functions inside other functions. Nested functions have a number of applications, such as hiding the complexity of inner loops:

let sumOfDivisors n =
    let rec loop current max acc =
        if current > max then
            acc
        else
            if n % current = 0 then
                loop (current + 1) max (acc + current)
            else
                loop (current + 1) max acc
    let start = 2
    let max = n / 2     (* largest factor, apart from n, cannot be > n / 2 *)
    let minSum = 1 + n  (* 1 and n are already factors of n *)
    loop start max minSum

printfn "%d" (sumOfDivisors 10)
(* prints 18, because the sum of 10's divisors is 1 + 2 + 5 + 10 = 18 *)

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[edit]

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:

let giveMeAThree x = 3

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:

let throwAwayFirstInput x y = y

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:

> let throwAwayFirstInput x y = y;;

val throwAwayFirstInput : 'a -> 'b -> 'b

> throwAwayFirstInput 5 "value";;
val it : string = "value"

> throwAwayFirstInput "thrownAway" 10.0;;
val it : float = 10.0

> throwAwayFirstInput 5 30;;
val it : int = 30

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:

let throwAwayFirstInput x y = y
let add x y = x + y

let z = add 10 (throwAwayFirstInput "this is a string" 5)

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:

> add 10 (throwAwayFirstInput "this is a string" 5);;
val it : int = 15

However, we get an error when we reverse the order of the parameters to throwAwayFirstInput:

> add 10 (throwAwayFirstInput 5 "this is a string");;

  add 10 (throwAwayFirstInput 5 "this is a string");;
  ------------------------------^^^^^^^^^^^^^^^^^^^

stdin(13,31): error FS0001: This expression has type
        string
but is here used with type
        int.

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.

Previous: Basic Concepts Index Next: Pattern Matching Basics



Pattern Matching Basics

Previous: Values and Functions Index Next: Recursion
F# : 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[edit]

In high level terms, pattern matching resembles this:

match expr with
| pat1 -> result1
| pat2 -> result2
| pat3 when expr2 -> result3
| _ -> defaultResult

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:

let rec fib n =
    match n with
    | 0 -> 0
    | 1 -> 1
    | _ -> fib (n - 1) + fib (n - 2)

We can experiment with this function in fsi:

 fib 1;;
val it : int = 1
> fib 2;;
val it : int = 1
> fib 5;;
val it : int = 5
> fib 10;;
val it : int = 55

It's possible to chain together multiple conditions which return the same value. For example:

> let greeting name =
    match name with
    | "Steve" | "Kristina" | "Matt" -> "Hello!"
    | "Carlos" | "Maria" -> "Hola!"
    | "Worf" -> "nuqneH!"
    | "Pierre" | "Monique" -> "Bonjour!"
    | _ -> "DOES NOT COMPUTE!";;

val greeting : string -> string

> greeting "Monique";;
val it : string = "Bonjour!"
> greeting "Pierre";;
val it : string = "Bonjour!"
> greeting "Kristina";;
val it : string = "Hello!"
> greeting "Sakura";;
val it : string = "DOES NOT COMPUTE!"

Alternative Pattern Matching Syntax[edit]

Pattern matching is such a fundamental feature that F# has a shorthand syntax for writing pattern matching functions using the function keyword:

let something = function
    | test1 -> value1
    | test2 -> value2
    | test3 -> value3

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:

let getPrice = function
    | "banana" -> 0.79
    | "watermelon" -> 3.49
    | "tofu" -> 1.09
    | _ -> nan (* nan is a special value meaning "not a number" *)

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:

> getPrice "tofu";;
val it : float = 1.09

> getPrice "banana";;
val it : float = 0.79

> getPrice "apple";;
val it : float = nan

Comparison To Other Languages[edit]

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#:

int fib(int n)
{
    switch(n)
    {
        case 0: return 0;
        case 1: return 1;
        default: return fib(n - 1) + fib(n - 2);
    }
}

Like all functions, pattern matches can only have one return type.

Binding Variables with Pattern Matching[edit]

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:

let rec factorial = function
    | 0 | 1 -> 1
    | n -> n * factorial (n - 1)

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[edit]

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:

let sign = function
    | 0 -> 0
    | x when x < 0 -> -1
    | x when x > 0 -> 1

The function above returns the sign of a number: -1 for negative numbers, +1 for positive numbers, and '0' for 0:

> sign -55;;
val it : int = -1

> sign 108;;
val it : int = 1

> sign 0;;
val it : int = 0

Variable binding is useful because it's often required to implement guards.

Pay Attention to F# Warnings[edit]

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

> let getCityFromZipcode zip =
    match zip with
    | 68528 -> "Lincoln, Nebraska"
    | 90210 -> "Beverly Hills, California";;

      match zip with
  ----------^^^^

stdin(12,11): warning FS0025: Incomplete pattern matches on this expression.
For example, the value '0' will not be matched

val getCityFromZipcode : int -> string

While this code is valid, F# informs the programmer of the possible error. F# warns us for a reason:

> getCityFromZipcode 68528;;
val it : string = "Lincoln, Nebraska"
> getCityFromZipcode 32566;;
Microsoft.FSharp.Core.MatchFailureException:
Exception of type 'Microsoft.FSharp.Core.MatchFailureException' was thrown.
   at FSI_0018.getCityFromZipcode(Int32 zip)
   at <StartupCode$FSI_0020>.$FSI_0020._main()
stopped due to error

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:

let apartmentPrices numberOfRooms =
    match numberOfRooms with
    | 1 -> 500.0
    | 2 -> 650.0
    | 3 -> 700.0
    | _ -> failwith "Only 1-, 2-, and 3- bedroom apartments available at this complex"

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

> let greeting name = 
    match name with
    | "Steve" -> "Hello!"
    | "Carlos" -> "Hola!"
    | _ -> "DOES NOT COMPUTE!"
    | "Pierre" -> "Bonjour";;

      | "Pierre" -> "Bonjour";;
  ------^^^^^^^^^

stdin(22,7): warning FS0026: This rule will never be matched.

val greeting : string -> string

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:

> greeting "Steve";;
val it : string = "Hello!"
> greeting "Ino";;
val it : string = "DOES NOT COMPUTE!"
> greeting "Pierre";;
val it : string = "DOES NOT COMPUTE!"

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.
Previous: Values and Functions Index Next: Recursion



Recursion

Previous: Pattern Matching Basics Index Next: Higher Order Functions
F# : Recursion and Recursive Functions


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:

let rec someFunction = ...

Examples[edit]

Factorial in F#[edit]

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:

Naturally, we'd calculate a factorial by hand using the following:

fact(6) =
        = 6 * fact(6 - 1)
        = 6 * 5 * fact(5 - 1)
        = 6 * 5 * 4 * fact(4 - 1)
        = 6 * 5 * 4 * 3 * fact(3 - 1)
        = 6 * 5 * 4 * 3 * 2 * fact(2 - 1)
        = 6 * 5 * 4 * 3 * 2 * 1 * fact(1 - 1)
        = 6 * 5 * 4 * 3 * 2 * 1 * 1
        = 720

In F#, the factorial function can be written concisely as follows:

let rec fact x =
    if x < 1 then 1
    else x * fact (x - 1)

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:

open System
 
let rec fact x =
    if x < 1 then 1
    else x * fact (x - 1)
 
(* // can also be written using pattern matching syntax:
let rec fact = function
    | n when n < 1 -> 1
    | n -> n * fact (n - 1) *)
 
Console.WriteLine(fact 6)

Greatest Common Divisor (GCD)[edit]

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:

To calculate this by hand, we'd write:

gcd(259, 111)   = gcd(111, 259% 111)
                = gcd(111, 37)
                = gcd(37, 111% 37)
                = gcd(37, 0)
                = 37

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:

open System

let rec gcd x y =
    if y = 0 then x
    else gcd y (x % y)
    
Console.WriteLine(gcd 259 111) // prints 37

Tail Recursion[edit]

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 rec count n =
    if n = 1000000 then
        printfn "done"
    else
        if n % 1000 = 0 then
            printfn "n: %i" n
        
        count (n + 1) (* recursive call *)
        () (* <-- This function is not tail recursive
              because it performs extra work (by
              returning unit) after
              the recursive call is invoked. *);;

val count : int -> unit

> count 0;;
n: 0
n: 1000
n: 2000
n: 3000
...
n: 58000
n: 59000
Session termination detected. Press Enter to restart.
Process is terminated due to StackOverflowException.

Let's see what happens if we make the function properly tail-recursive:

> let rec count n =
    if n = 1000000 then
        printfn "done"
    else
        if n % 1000 = 0 then
            printfn "n: %i" n
        
        count (n + 1) (* recursive call *);;

val count : int -> unit

> count 0;;
n: 0
n: 1000
n: 2000
n: 3000
n: 4000
...
n: 995000
n: 996000
n: 997000
n: 998000
n: 999000
done

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[edit]

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:

let rec slowMultiply a b =
    if b > 1 then
        a + slowMultiply a (b - 1)
    else
        a

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:

let rec slowMultiply a b =
    if b > 1 then
        let intermediate = slowMultiply a (b - 1) (* recursion *)
        let result = a + intermediate (* <-- additional operations *)
        result                   
    else a

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:

> let rec slowMultiply a b =
    if b > 1 then
        a + slowMultiply a (b - 1)
    else
        a;;

val slowMultiply : int -> int -> int

> slowMultiply 3 9;;
val it : int = 27

> slowMultiply 2 14;;
val it : int = 28

> slowMultiply 1 100000;;

Process is terminated due to StackOverflowException.
Session termination detected. Press Enter to restart.

It's possible to re-write most recursive functions into their tail-recursive forms using an accumulating parameter:

> let slowMultiply a b =
    let rec loop acc counter =
        if counter > 1 then
            loop (acc + a) (counter - 1) (* tail recursive *)
        else
            acc
    loop a b;;

val slowMultiply : int -> int -> int

> slowMultiply 3 9;;
val it : int = 27

> slowMultiply 2 14;;
val it : int = 28

> slowMultiply 1 100000;;
val it : int = 100000

The accumulator parameter in the inner loop holds the state of our function throughout each recursive iteration.

Exercises[edit]

Solutions.

Faster Fib Function[edit]

The following function calculates the nth number in the Fibonacci sequence:

let rec fib = function
    | n when n=0I -> 0I
    | n when n=1I -> 1I
    | n -> fib(n - 1I) + fib(n - 2I)
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(2n). 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:

fib(0I) = 0
fib(1I) = 1
fib(2I) = 1
fib(3I) = 2
fib(4I) = 3
fib(5I) = 5
fib(10I) = 55
fib(100I) = 354224848179261915075

Additional Reading[edit]

Previous: Pattern Matching Basics Index Next: Higher Order Functions



Higher Order Functions

Previous: Recursion Index Next: Option Types
F# : 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 which does both.

Familiar Higher Order Functions[edit]

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:

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:

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 was a literal value, and we call it just like we call any other function. For example, here's a very trivial function:

let passFive f = (f 5)

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.

open System

let square x = x * x

let cube x = x * x * x

let sign x =
    if x > 0 then "positive"
    else if x < 0 then "negative"
    else "zero"

let passFive f = (f 5)

printfn "%A" (passFive square)  // 25
printfn "%A" (passFive cube)    // 125
printfn "%A" (passFive sign)    // "positive"

These functions have the following types:

val square : int -> int
val cube : int -> int
val sign : int -> string
val passFive : (int -> 'a) -> 'a

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[edit]

A map function converts one type of data to another type of data. A simple map function in F# looks like this:

let map item converter = converter item

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:

open System

let map x f = f x

let square x = x * x

let cubeAndConvertToString x =
    let temp = x * x * x
    temp.ToString()
    
let answer x =
    if x = true then "yes"
    else "no"

let first = map 5 square
let second = map 5 cubeAndConvertToString
let third = map true answer

These functions have the following signatures:

val map : 'a -> ('a -> 'b) -> 'b

val square : int -> int
val cubeAndConvertToString : int -> string
val answer : bool -> string

val first : int
val second : string
val third : string

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:

let fourth = map true square

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)[edit]

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:

let inline (<<) f g x = f (g x)

Which has the somewhat cumbersome signature val << : ('b -> 'c) -> ('a -> 'b) -> 'a -> 'c.

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:

open System

let f x = x*x
let g x = -x/2.0 + 5.0

let fog = f << g

Console.WriteLine(fog 0.0) // 25
Console.WriteLine(fog 1.0) // 20.25
Console.WriteLine(fog 2.0) // 16
Console.WriteLine(fog 3.0) // 12.25
Console.WriteLine(fog 4.0) // 9
Console.WriteLine(fog 5.0) // 6.25

Note that fog doesn't return a value, it returns another function whose signature is (float -> float).

Of course, there's no reason why the compose function needs to 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:

let inline (>>) f g x = g (f x)

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.

let gof = f >> g

This will first apply f and then apply g on the result.

The |> Operator[edit]

The pipeline operator, |>, is one of the most important operators in F#. The definition of the pipeline operator is remarkably simple:

let inline (|>) x f = f x

Let's take 3 functions:

let square x = x * x
let add x y = x + y
let toString x = x.ToString()

Let's also say we had a complicated function which squared a number, added five to it, and converted it to a string? Normally, we'd write this:

let complexFunction x =
    toString (add 5 (square x))

We can improve the readability of this function somewhat using the pipeline operator:

let complexFunction x =
    x |> square |> add 5 |> toString

x is piped to the square function, which is piped to add 5 method, and finally to the toString method.

Anonymous Functions[edit]

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.

let complexFunction =
    2                            (* 2 *)
    |> ( fun x -> x + 5)         (* 2 + 5 = 7 *)
    |> ( fun x -> x * x)         (* 7 * 7 = 49 *)
    |> ( fun x -> x.ToString() ) (* 49.ToString = "49" *)

Anonymous functions are convenient and find a use in a surprising number of places.

A Timer Function[edit]

open System

let duration f = 
    let timer = new System.Diagnostics.Stopwatch()
    timer.Start()
    let returnValue = f()
    printfn "Elapsed Time: %i" timer.ElapsedMilliseconds
    returnValue
    
let rec fib = function
    | 0 -> 0
    | 1 -> 1
    | n -> fib (n - 1) + fib (n - 2)

let main() =
    printfn "fib 5: %i" (duration ( fun() -> fib 5 ))
    printfn "fib 30: %i" (duration ( fun() -> fib 30 ))

main()

The duration function has the type val duration : (unit -> 'a) -> 'a. This program prints:

Elapsed Time: 1
fib 5: 5
Elapsed Time: 5
fib 30: 832040
Note: the actual duration to execute these functions will vary from machine to machine.

Currying and Partial Functions[edit]

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:

let add x y = x + y

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:

let addFive = add 5

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:

open System

let add x y = x + y

let addFive = add 5

Console.WriteLine(addFive 12) // prints 17

How Currying Works[edit]

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:

let add = (fun x -> (fun y -> x + y) )

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[edit]

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:

let getPrice2 =
    (fun x ->
        match x with
        | "banana" -> 0.79
        | "watermelon" -> 3.49
        | "tofu" -> 1.09
        | _ -> nan)

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.

Previous: Recursion Index Next: Option Types



Option Types

Previous: Higher Order Functions Index Next: Tuples and Records
F# : 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[edit]

Let's say we have a function that divides two integers. Normally, we'd write the function as follows:

let div x y = x / y

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:

> let div x y = x / y;;

val div : int -> int -> int

> div 10 5;;
val it : int = 2

> div 10 0;;
System.DivideByZeroException: Attempted to divide by zero.
   at <StartupCode$FSI_0035>.$FSI_0035._main()
stopped due to error

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:

> let safediv x y =
    match y with
    | 0 -> None
    | _ -> Some(x/y);;

val safediv : int -> int -> int option

> safediv 10 5;;
val it : int option = Some 2

> safediv 10 0;;
val it : int option = None

Notice an important difference between our div and safediv functions:

val div : int -> int -> int
val safediv : int -> int -> int option

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[edit]

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:

> let isFortyTwo = function
    | Some(42) -> true
    | Some(_) | None -> false;;

val isFortyTwo : int option -> bool

> isFortyTwo (Some(43));;
val it : bool = false

> isFortyTwo (Some(42));;
val it : bool = true

> isFortyTwo None;;
val it : bool = false

Other Functions in the Option Module[edit]

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.
Previous: Higher Order Functions Index Next: Tuples and Records



Tuples and Records

Previous: Option Types Index Next: Lists
F# : Tuples and Records


Defining Tuples[edit]

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.

let average (a, b) =
    (a + b) / 2.0

This function has the type float * float -> float, it takes a float * float tuple and returns another float.

> let average (a, b) =
    let sum = a + b
    sum / 2.0;;

val average : float * float -> float

> average (10.0, 20.0);;
val it : float = 15.0

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.

> let scalarMultiply (s : float) (a, b, c) = (a * s, b * s, c * s);;

val scalarMultiply : float -> float * float * float -> float * float * float

> scalarMultiply 5.0 (6.0, 10.0, 20.0);;
val it : float * float * float = (30.0, 50.0, 100.0)

Example 2 - a function which reverses the input of whatever is passed into the function.

> let swap (a, b) = (b, a);;
val swap : 'a * 'b -> 'b * 'a

> swap ("Web", 2.0);;
val it : float * string = (2.0, "Web")

> swap (20, 30);;
val it : int * int = (30, 20)

Example 3 - a function which divides two numbers and returns the remainder simultaneously.

> let divrem x y =
    match y with
    | 0 -> None
    | _ -> Some(x / y, x % y);;

val divrem : int -> int -> (int * int) option

> divrem 100 20;; (* 100 / 20 = 5 remainder 0 *)
val it : (int * int) option = Some (5, 0)

> divrem 6 4;; (* 6 / 4 = 1 remainder 2 *)
val it : (int * int) option = Some (1, 2)

> divrem 7 0;; (* 7 / 0 throws a DivisionByZero exception *)
val it : (int * int) option = None

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[edit]

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.

let greeting (name, language) =
    match (name, language) with
    | ("Steve", _) -> "Howdy, Steve"
    | (name, "English") -> "Hello, " + name
    | (name, _) when language.StartsWith("Span") -> "Hola, " + name
    | (_, "French") -> "Bonjour!"
    | _ -> "DOES NOT COMPUTE"

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:

> greeting ("Steve", "English");;
val it : string = "Howdy, Steve"
> greeting ("Pierre", "French");;
val it : string = "Bonjour!"
> greeting ("Maria", "Spanish");;
val it : string = "Hola, Maria"
> greeting ("Rocko", "Esperanto");;
val it : string = "DOES NOT COMPUTE"

Example 2

We can conveniently match against the shape of a tuple using the alternative pattern matching syntax:

> let getLocation = function
    | (0, 0) -> "origin"
    | (0, y) -> "on the y-axis at y=" + y.ToString()
    | (x, 0) -> "on the x-axis at x=" + x.ToString()
    | (x, y) -> "at x=" + x.ToString() + ", y=" + y.ToString() ;;

val getLocation : int * int -> string

> getLocation (0, 0);;
val it : string = "origin"
> getLocation (0, -1);;
val it : string = "on the y-axis at y=-1"
> getLocation (5, -10);;
val it : string = "at x=5, y=-10"
> getLocation (7, 0);;
val it : string = "on the x-axis at x=7"

fst and snd[edit]

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:

let fst (a, b) = a
let snd (a, b) = b

They have the following types:

val fst : 'a * 'b -> 'a
val snd : 'a * 'b -> 'b

Here are a few examples in FSI:

> fst (1, 10);;
val it : int = 1
> snd (1, 10);;
val it : int = 10
> fst ("hello", "world");;
val it : string = "hello"
> snd ("hello", "world");;
val it : string = "world"
> fst ("Web", 2.0);;
val it : string = "Web"
> snd (50, 100);;
val it : int = 100

Assigning Multiple Variables Simultaneously[edit]

Tuples can be used to assign multiple values simultaneously. This is the same as tuple unpacking in Python. The syntax for doing so is:

let val1, val2, ... valN = (expr1, expr2, ... exprN)

In other words, you assign a comma-separated list of N values to an N-tuple. Here's an example in FSI:

> let x, y = (1, 2);;

val y : int
val x : int

> x;;
val it : int = 1

> y;;
val it : int = 2

The number of values being assigned must match the arity of tuple returned from the function, otherwise F# will raise an exception:

> let x, y = (1, 2, 3);;

  let x, y = (1, 2, 3);;
  ------------^^^^^^^^

stdin(18,13): error FS0001: Type mismatch. Expecting a
	'a * 'b
but given a
	'a * 'b * 'c.
The tuples have differing lengths of 2 and 3.

Tuples and the .NET Framework[edit]

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:

> System.Int32.TryParse("3");;
val it : bool * int = (true, 3)

> System.Math.DivRem(10, 7);;
val it : int * int = (1, 3)

Defining Records[edit]

A record is similar to a tuple, except it contains named fields. A record is defined using the syntax:

type recordName =
    { [ fieldName : dataType ] + }
+ means the element must occur one or more times.

Here's a simple record:

type website =
    { Title : string;
        Url : string }

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:

> let homepage = { Title = "Google"; Url = "http://www.google.com" };;
val homepage : website

Note that F# determines a record's 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:

> { Url = "http://www.microsoft.com/"; Title = "Microsoft Corporation" };;
val it : website = {Title = "Microsoft Corporation";
                    Url = "http://www.microsoft.com/";}

It's easy to access a record's properties using dot notation:

> let homepage = { Title = "Wikibooks"; Url = "http://www.wikibooks.org/" };;

val homepage : website

> homepage.Title;;
val it : string = "Wikibooks"

> homepage.Url;;
val it : string = "http://www.wikibooks.org/"

Cloning Records[edit]

Records are immutable types, which means that instances of records cannot be modified. However, records can be cloned conveniently using the clone syntax:

type coords = { X : float; Y : float }

let setX item newX =
    { item with X = newX }

The method setX has the type coords -> float -> coords. The with keyword creates a clone of item and set its X property to newX.

> let start = { X = 1.0; Y = 2.0 };;
val start : coords

> let finish = setX start 15.5;;
val finish : coords

> start;;
val it : coords = {X = 1.0;
                   Y = 2.0;}
> finish;;
val it : coords = {X = 15.5;
                   Y = 2.0;}

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:

type TransactionItem =
    { Name : string;
        ID : int;
        ProcessedText : string;
        IsProcessed : bool }

let getItem name id =
    { Name = name; ID = id; ProcessedText = null; IsProcessed = false }

let processItem item =
    { item with
        ProcessedText = "Done";
        IsProcessed = true }
    
let printItem msg item =
    printfn "%s: %A" msg item

let main() =
    let preProcessedItem = getItem "Steve" 5
    let postProcessedItem = processItem preProcessedItem

    printItem "preProcessed" preProcessedItem
    printItem "postProcessed" postProcessedItem
    
main()

This program processes an instance of the TransactionItem class and prints the results. This program outputs the following:

preProcessed: {Name = "Steve";
 ID = 5;
 ProcessedText = null;
 IsProcessed = false;}
postProcessed: {Name = "Steve";
 ID = 5;
 ProcessedText = "Done";
 IsProcessed = true;}

Pattern Matching Records[edit]

We can pattern match on records just as easily as tuples:

open System

type coords = { X : float; Y : float }
 
let getQuadrant = function
    | { X = 0.0; Y = 0.0 } -> "Origin"
    | item when item.X >= 0.0 && item.Y >= 0.0 -> "I"
    | item when item.X <= 0.0 && item.Y >= 0.0 -> "II"
    | item when item.X <= 0.0 && item.Y <= 0.0 -> "III"
    | item when item.X >= 0.0 && item.Y <= 0.0 -> "IV"
 
let testCoords (x, y) =
    let item = { X = x; Y = y }
    printfn "(%f, %f) is in quadrant %s" x y (getQuadrant item)
 
let main() =
    testCoords(0.0, 0.0)
    testCoords(1.0, 1.0)
    testCoords(-1.0, 1.0)
    testCoords(-1.0, -1.0)
    testCoords(1.0, -1.0)
    Console.ReadKey(true) |> ignore
 
main()

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:

(0.000000, 0.000000) is in quadrant Origin
(1.000000, 1.000000) is in quadrant I
(-1.000000, 1.000000) is in quadrant II
(-1.000000, -1.000000) is in quadrant III
(1.000000, -1.000000) is in quadrant IV
Previous: Option Types Index Next: Lists



Lists

Previous: Tuples and Records Index Next: Sequences
F# : 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[edit]

Using List Literals[edit]

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:

> let numbers = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10];;
val numbers : int list

> numbers;;
val it : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

Notice that all values in a list must have the same type:

> [1; 2; 3; 4; "cat"; 6; 7];;

  -------------^^^^^^

stdin(120,14): error FS0001: This expression has type
        string
but is here used with type
        int.

Using the :: ("cons") Operator[edit]

It is very common to build lists up by prepending or consing a value to an existing list using the :: operator:

> 1 :: 2 :: 3 :: [];;
val it : int list = [1; 2; 3]
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:

> let x = 1 :: 2 :: 3 :: 4 :: [];;
val x : int list

> let y = 12 :: x;;
val y : int list

> x;;
val it : int list = [1; 2; 3; 4]

> y;;
val it : int list = [12; 1; 2; 3; 4]

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[edit]

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:

> List.init 5 (fun index -> index * 3);;
val it : int list = [0; 3; 6; 9; 12]

> List.init 5 (fun index -> (index, index * index, index * index * index));;
val it : (int * int * int) list
= [(0, 0, 0); (1, 1, 1); (2, 4, 8); (3, 9, 27); (4, 16, 64)]

F# calls the initializer function 5 times with the index of each item in the list, starting at index 0.

Using List Comprehensions[edit]

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:

> [1 .. 10];;
val it : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

> [1 .. 2 .. 10];;
val it : int list = [1; 3; 5; 7; 9]

> ['a' .. 's'];;
val it : char list
= ['a'; 'b'; 'c'; 'd'; 'e'; 'f'; 'g'; 'h'; 'i'; 'j'; 'k'; 'l'; 'm'; 'n'; 'o';
   'p'; 'q'; 'r'; 's']

Generators have the construct [for x in collection do ... yield expr], and they are much more flexible than ranges. For example:

> [ for a in 1 .. 10 do
        yield (a * a) ];;
val it : int list = [1; 4; 9; 16; 25; 36; 49; 64; 81; 100]

> [ for a in 1 .. 3 do
    for b in 3 .. 7 do
        yield (a, b) ];;
val it : (int * int) list
= [(1, 3); (1, 4); (1, 5); (1, 6); (1, 7); (2, 3); (2, 4); (2, 5); (2, 6);
   (2, 7); (3, 3); (3, 4); (3, 5); (3, 6); (3, 7)]

> [ for a in 1 .. 100 do
    if a % 3 = 0 && a % 5 = 0 then yield a];;
val it : int list = [15; 30; 45; 60; 75; 90]

it's possible to loop over any collection, not just numbers. This example loops over a char list:

> let x = [ 'a' .. 'f' ];;

val x : char list

> [for a in x do yield [a; a; a] ];;
val it : char list list
= [['a'; 'a'; 'a']; ['b'; 'b'; 'b']; ['c'; 'c'; 'c']; ['d'; 'd'; 'd'];
   ['e'; 'e'; 'e']; ['f'; 'f'; 'f']]

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:

> [for a in 1 .. 5 do
    yield! [ a .. a + 3 ] ];;
val it : int list
= [1; 2; 3; 4; 2; 3; 4; 5; 3; 4; 5; 6; 4; 5; 6; 7; 5; 6; 7; 8]

It's possible to mix the yield and yield! keywords:

> [for a in 1 .. 5 do
    match a with
    | 3 -> yield! ["hello"; "world"]
    | _ -> yield a.ToString() ];;
val it : string list = ["1"; "2"; "hello"; "world"; "4"; "5"]

Alternative List Comprehension Syntax[edit]

The samples above use the yield keyword explicitly, however F# provides a slightly different arrow-based syntax for list comprehensions:

> [ for a in 1 .. 5 -> a * a];;
val it : int list = [1; 4; 9; 16; 25]

> [ for a in 1 .. 5 do
    for b in 1 .. 3 -> a, b];;
val it : (int * int) list
= [(1, 1); (1, 2); (1, 3); (2, 1); (2, 2); (2, 3); (3, 1); (3, 2); (3, 3);
   (4, 1); (4, 2); (4, 3); (5, 1); (5, 2); (5, 3)]

> [ for a in 1 .. 5 ->> [1 .. 3] ];;
val it : int list = [1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3]

-> and ->> are equivalent to the yield and yield! operators respectively. While it's still common to see list comprehensions expressed using -> and ->>, those constructs will not be emphasized in this book since they have been deprecated in favor of yield and yield!.

Pattern Matching Lists[edit]

You use the same syntax to match against lists that you use to create lists. Here's a simple program:

let rec sum total = function
    | [] -> total
    | hd :: tl -> sum (hd + total) tl

let main() =
    let numbers = [ 1 .. 5 ]
    let sumOfNumbers = sum 0 numbers
    printfn "sumOfNumbers: %i" sumOfNumbers
    
main()

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[edit]

Frequently, we use recursion and pattern matching to generate new lists from existing lists. A simple example is reversing a list:

let reverse l =
    let rec loop acc = function
        | [] -> acc
        | hd :: tl -> loop (hd :: acc) tl
    loop [] l
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:

> reverse [1 .. 5];;
val it : int list = [5; 4; 3; 2; 1]

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:

> List.rev [1 .. 5];;
val it : int list = [5; 4; 3; 2; 1]

Filtering Lists[edit]

Oftentimes, we want to filter a list for certain values. We can write a filter function as follows:

open System

let rec filter predicate = function
    | [] -> []
    | hd :: tl ->
        match predicate hd with
        | true -> hd::filter predicate tl
        | false -> filter predicate tl

let main() =
    let filteredNumbers = [1 .. 10] |> filter (fun x -> x % 2 = 0)
    printfn "filteredNumbers: %A" filteredNumbers
    
main()

The filter method has the type val filter : ('a -> bool) -> 'a list -> 'a list. The program above outputs:

filteredNumbers: [2; 4; 6; 8; 10]

We can make the filter above tail-recursive with a slight modification:

let filter predicate l =
    let rec loop acc = function
        | [] -> acc
        | hd :: tl ->
            match predicate hd with
            | true -> loop (hd :: acc) tl
            | false -> loop (acc) tl
    List.rev (loop [] l)
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[edit]

We can write a function which maps a list to another list:

open System

let rec map converter = function
    | [] -> []
    | hd :: tl -> converter hd::map converter tl

let main() =
    let mappedNumbers = [1 .. 10] |> map ( fun x -> (x * x).ToString() )
    printfn "mappedNumbers: %A" mappedNumbers
    
main()

map has the type val map : ('a -> 'b) -> 'a list -> 'b list. The program above outputs:

mappedNumbers: ["1"; "4"; "9"; "16"; "25"; "36"; "49"; "64"; "81"; "100"]

A tail-recursive map function can be written as:

let map converter l =
    let rec loop acc = function
        | [] -> acc
        | hd :: tl -> loop (converter hd :: acc) tl
    List.rev (loop [] l)

Like the example above, we use the accumulating-param-and-reverse pattern to make the function tail recursive.

Using the List Module[edit]

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.rev [1 .. 5];;
val it : int list = [5; 4; 3; 2; 1]

List.filter filters a list:

> [1 .. 10] |> List.filter (fun x -> x % 2 = 0);;
val it : int list = [2; 4; 6; 8; 10]

List.map maps a list from one type to another:

> [1 .. 10] |> List.map (fun x -> (x * x).ToString());;
val it : string list
= ["1"; "4"; "9"; "16"; "25"; "36"; "49"; "64"; "81"; "100"]

List.append and the @ Operator[edit]

List.append has the type:

val append : 'T list -> 'T list -> 'T list

As you can imagine, the append functions appends one list to another. The @ operator is an infix operator which performs the same function:

let first      = [1; 2; 3;]
let second     = [4; 5; 6;]
let combined1  = first @ second           (* returns [1; 2; 3; 4; 5; 6] *)
let combined2  = List.append first second (* returns [1; 2; 3; 4; 5; 6] *)

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:

   first = 1 :: 2 :: 3 :: []

   second = 4 :: 5 :: 6 :: []

Appending the two lists, first @ second, results in the following:

      first = 1 :: 2 :: 3 :: []
              \______  ______/
                     \/     
   combined = 1 :: 2 :: 3 :: second
                  (copied)

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:

> let first = [1; 2; 3;]
let second = [4; 5; 6;]
let combined = first @ second
let secondHalf = List.tail (List.tail (List.tail combined));;

val first : int list
val second : int list
val combined : int list
val secondHalf : int list

> System.Object.ReferenceEquals(second, secondHalf);;
val it : bool = true

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[edit]

List.choose has the following definition:

val choose : ('T -> 'U option) -> 'T list -> 'U list

The choose method is clever because it filters and maps a list simultaneously:

> [1 .. 10] |> List.choose (fun x ->
    match x % 2 with
    | 0 -> Some(x, x*x, x*x*x)
    | _ -> None);;
val it : (int * int * int) list
= [(2, 4, 8); (4, 16, 64); (6, 36, 216); (8, 64, 512); (10, 100, 1000)]

choose filters for items that return Some and maps them to another value in a single step.

List.fold and List.foldBack[edit]

List.fold and List.foldBack have the following definitions:

val fold : ('State -> 'T -> 'State) -> 'State -> 'T list -> 'State
val foldBack : ('T -> 'State -> 'State) -> 'T list -> 'State -> 'State

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:

(* List.fold implementation *)
let rec fold (f : 'State -> 'T -> 'State) (seed : 'State) = function
    | [] -> seed
    | hd :: tl -> fold f (f seed hd) tl
    
(* List.foldBack implementation *)
let rec foldBack (f : 'T -> 'State -> 'State) (items : 'T list) (seed : 'State) =
    match items with
    | [] -> seed
    | hd :: tl -> f hd (foldBack f tl seed)

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:

let input = [ 2; 4; 6; 8; 10 ]
let f accumulator input = accumulator * input
let seed = 1
let output = List.fold f seed input

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

let x = [ 1 .. 100 ] |> List.fold ( + ) 0 (* returns 5050 *)

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

let factorial n = [ 1I .. n ] |> List.fold ( * ) 1I
let x = factorial 13I (* returns 6227020800I *)

Computing population standard deviation

let stddev (input : float list) =
    let sampleSize = float input.Length
    let mean = (input |> List.fold ( + ) 0.0) / sampleSize
    let differenceOfSquares =
        input |> List.fold
            ( fun sum item -> sum + Math.Pow(item - mean, 2.0) ) 0.0
    let variance = differenceOfSquares / sampleSize
    Math.Sqrt(variance)

let x = stddev [ 5.0; 6.0; 8.0; 9.0 ] (* returns 1.58113883 *)

List.find and List.tryFind[edit]

List.find and List.tryfind have the following types:

val find : ('T -> bool) -> 'T list -> 'T
val tryFind : ('T -> bool) -> 'T list -> 'T option

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:

> let cities = ["Bellevue"; "Omaha"; "Lincoln"; "Papillion"; "Fremont"];;

val cities : string list =
  ["Bellevue"; "Omaha"; "Lincoln"; "Papillion"; "Fremont"]

> let findStringContaining text (items : string list) =
    items |> List.find(fun item -> item.Contains(text));;

val findStringContaining : string -> string list -> string

> let findStringContaining2 text (items : string list) =
    items |> List.tryFind(fun item -> item.Contains(text));;

val findStringContaining2 : string -> string list -> string option

> findStringContaining "Papi" cities;;
val it : string = "Papillion"

> findStringContaining "Hastings" cities;;
System.Collections.Generic.KeyNotFoundException: The given key was not present in the dictionary.
   at Microsoft.FSharp.Collections.ListModule.find[T](FastFunc`2 predicate, FSharpList`1 list)
   at <StartupCode$FSI_0007>.$FSI_0007.main@()
stopped due to error

> findStringContaining2 "Hastings" cities;;
val it : string option = None

Exercises[edit]

Solutions.

Pair and Unpair[edit]

Write two functions with the following definitions:

val pair : 'a list -> ('a * 'a) list
val unpair : ('a * 'a) list -> 'a list

The pair function should convert a list into a list of pairs as follows:

pair [ 1 .. 10 ] = [(1, 2); (3, 4); (5, 6); (7, 8); (9, 10)]
pair [ "one"; "two"; "three"; "four"; "five" ] = [("one", "two"); ("three", "four")]

The unpair function should convert a list of pairs back into a traditional list as follows:

unpair [(1, 2); (3, 4); (5, 6)] =  [1; 2; 3; 4; 5; 6]
unpair [("one", "two"); ("three", "four")] = ["one"; "two"; "three"; "four"]

Expand a List[edit]

Write a function with the following type definition:

val expand : 'a list -> 'a list list

The expand function should expand a list as follows:

expand [ 1 .. 5 ] = [ [1; 2; 3; 4; 5]; [2; 3; 4; 5]; [3; 4; 5]; [4; 5]; [5] ]
expand [ "monkey"; "kitty"; "bunny"; "rat" ] =
    [ ["monkey"; "kitty"; "bunny"; "rat"];
      ["kitty"; "bunny"; "rat"];
      ["bunny"; "rat"];
      ["rat"] ]

Greatest common divisor on lists[edit]

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:

val gcd : int -> int -> int

The gcd function should take two integers and return their greatest common divisor. Hint: Use Euler's algorithm

gcd 15 25 = 5

The second step is to use the gcd function to calculate the greatest common divisor of an int list.

val gcdl : int list -> int

The gcdl function should work like this:

gcdl [15; 75; 20] = 5

If the list is empty the result shall be 0.

Basic Mergesort Algorithm[edit]

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

val split : 'a list -> 'a list * 'a list

The split function will work like this.

split [2; 8; 5; 3] = ( [5; 2], [8; 3] )

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:

val merge : 'a list * 'a list -> 'a list

Example:

merge ( [2; 5], [3; 8] )  =  [2; 3; 5; 8]

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.

val msort : 'a list -> 'a 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

Previous: Tuples and Records Index Next: Sequences



Sequences

Previous: Lists Index Next: Sets and Maps
F# : 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[edit]

Sequences are defined using the syntax:

seq { expr }

Similar to lists, sequences can be constructed using ranges and comprehensions:

> seq { 1 .. 10 };; (* seq ranges *)
val it : seq<int> = seq [1; 2; 3; 4; ...]

> seq { 1 .. 2 .. 10 };; (* seq ranges *)
val it : seq<int> = seq [1; 3; 5; 7; ...]

> seq {10 .. -1 .. 0};; (* descending *)
val it : seq<int> = seq [10; 9; 8; 7; ...]

> seq { for a in 1 .. 10 do yield a, a*a, a*a*a };; (* seq comprehensions *)
val it : seq<int * int * int>
= seq [(1, 1, 1); (2, 4, 8); (3, 9, 27); (4, 16, 64); ...]

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:

> let intList =
    [ for a in 1 .. 10 do
        printfn "intList: %i" a
        yield a ]
        
let intSeq =
    seq { for a in 1 .. 10 do
            printfn "intSeq: %i" a
            yield a };;

val intList : int list
val intSeq : seq<int>

intList: 1
intList: 2
intList: 3
intList: 4
intList: 5
intList: 6
intList: 7
intList: 8
intList: 9
intList: 10

> Seq.item 3 intSeq;;
intSeq: 1
intSeq: 2
intSeq: 3
intSeq: 4
val it : int = 4

> Seq.item 7 intSeq;;
intSeq: 1
intSeq: 2
intSeq: 3
intSeq: 4
intSeq: 5
intSeq: 6
intSeq: 7
intSeq: 8
val it : int = 8

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:

> seq { 1I .. 1000000000000I };;
val it : seq<bigint> = seq [1I; 2I; 3I; 4I; ...]

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:

> let allEvens = 
    let rec loop x = seq { yield x; yield! loop (x + 2) }
    loop 0;;

> for a in (Seq.take 5 allEvens) do
    printfn "%i" a;;
0
2
4
6
8
val it : unit = ()

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[edit]

The .NET Base Class Library (BCL) contains two interfaces in the System.Collections.Generic namespace:

type IEnumerable<'a> =
  interface
   (* Returns an enumerator that iterates through a collection *)
    member GetEnumerator<'a> : unit -> IEnumerator<'a>
  end

type IEnumerator<'a> =
  interface
   (* Advances to the next element in the sequences. Returns true if 
      the enumerator was successfully advanced to the next element; false
      if the enumerator has passed the end of the collection. *)
    member MoveNext : unit -> bool

    (* Gets the current element in the collection. *)
    member Current : 'a

    (* Sets the enumerator to its initial position, which is 
       before the first element in the collection. *)
    member Reset : unit -> unit
  end

The seq type is defined as follows:

type seq<'a> = System.Collections.Generic.IEnumerable<'a>

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:

open System
open System.Collections

let evens = seq { 0 .. 2 .. 10 } (* returns IEnumerable<int> *)

let main() =
    let evensEnumerator = evens.GetEnumerator() (* returns IEnumerator<int> *)
    while evensEnumerator.MoveNext() do
        printfn "evensEnumerator.Current: %i" evensEnumerator.Current
    
    Console.ReadKey(true) |> ignore
            
main()

This program outputs:

evensEnumerator.Current: 0
evensEnumerator.Current: 2
evensEnumerator.Current: 4
evensEnumerator.Current: 6
evensEnumerator.Current: 8
evensEnumerator.Current: 10

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[edit]

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.
> let test = Seq.append (seq{1..3}) (seq{4..7});;
val it : seq<int> = seq [1; 2; 3; 4; ...]

val choose : ('T -> 'U option) -> seq<'T> -> seq<'U>

Filters and maps a sequence to another sequence.
> let thisworks = seq { for nm in [ Some("James"); None; Some("John") ] |> Seq.choose id -> nm.Length }
val it : seq<int> = seq [5; 4]

val distinct : seq<'T> -> seq<'T>

Returns a sequence that filters out duplicate entries.
> let dist = Seq.distinct (seq[1;2;2;6;3;2])
val it : seq<int> = seq [1; 2; 6; 3]

val exists : ('T -> bool) -> seq<'T> -> bool

Determines if an element exists in a sequence.
> let equalsTwo x = x=2
> let exist = Seq.exists equalsTwo (seq{3..9})
val equalsTwo : int -> bool
val it : bool = false

val filter : ('T -> bool) -> seq<'T> -> seq<'T>

Builds a new sequence consisting of elements filtered from the input sequence.
> Seq.filter (fun x-> x%2 = 0) (seq{0..9})
val it : seq<int> = seq [0; 2; 4; 6; ...]

val fold : ('State -> 'T -> 'State) -> 'State -> seq<'T> -> 'State

Repeatedly applies a function to each element in the sequence from left to right.
> let sumSeq sequence1 = Seq.fold (fun acc elem -> acc + elem) 0 sequence1
Seq.init 10 (fun index -> index * index)
|> sumSeq
|> printfn "The sum of the elements is %d."
> 
The sum of the elements is 285.

val sumSeq : seq<int> -> int
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.
> Seq.initInfinite (fun x -> x*x)
val it : seq<int> = seq [0; 1; 4; 9; ...]

val map : ('T -> 'U) -> seq<'T> -> seq<'U>

Maps a sequence of type 'a to type 'b.
> Seq.map (fun x->x*x+2) (seq[3;5;4;3])
val it : seq<int> = seq [11; 27; 18; 11]

val item : int -> seq<'T> -> 'T

Returns the nth value of a sequence.
> Seq.item 3 (seq {for n in 2..9 do yield n})
val it : int = 5

val take : int -> seq<'T> -> seq<'T>

Returns a new sequence consisting of the first n elements of the input sequence.
> Seq.take 3 (seq{1..6})
val it : seq<int> = seq [1; 2; 3]

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.
> let sequenciaMenorqDez = Seq.takeWhile (fun elem -> elem < 10) (seq {for i in 0..20 do yield i+1})
val sequenciaMenorqDez : seq<int>
> sequenciaMenorqDez;;
val it : seq<int> = seq [1; 2; 3; 4; ...]

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.
> let fibs = (0I, 1I) |> Seq.unfold (fun (a, b) -> Some(a, (b, a + b) ) );;

val fibs : seq<bigint>

> Seq.iter (fun x -> printf "%O " x) (Seq.take 20 fibs);;
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

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:

> let test = 1 |> Seq.unfold (fun x ->
    if x <= 5 then Some(sprintf "x: %i" x, x + 1)
    else None );;

val test : seq<string>

> Seq.iter (fun x -> printfn "%s" x) test;;
x: 1
x: 2
x: 3
x: 4
x: 5

Often, it's preferable to generate sequences using seq comprehensions rather than the unfold.

Previous: Lists Index Next: Sets and Maps



Sets and Maps

Previous: Sequences Index Next: Discriminated Unions
F# : 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[edit]

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:

> Set.empty.Add(1).Add(2).Add(7);;
val it : Set<int> = set [1; 2; 7]

Converting lists and sequences into sets Additionally, the we can use Set.ofList and Set.ofSeq to convert an entire collection into a set:

> Set.ofList ["Mercury"; "Venus"; "Earth"; "Mars"; "Jupiter"; "Saturn"; "Uranus"; "Neptune"];;
val it : Set<string> = set ["Earth"; "Jupiter"; "Mars"; "Mercury"; ...]

The example above demonstrates the unordered nature of sets.

The Set Module[edit]

The Microsoft.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.
> let a = Set.ofSeq [ 1 .. 10 ]
let b = Set.ofSeq [ 5 .. 15 ];;

val a : Set<int>
val b : Set<int>

> Set.difference a b;;
val it : Set<int> = set [1; 2; 3; 4]

> a - b;; (* The '-' operator is equivalent to Set.difference *)
val it : Set<int> = set [1; 2; 3; 4]

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.
> let a = Set.ofSeq [ 1 .. 10 ]
let b = Set.ofSeq [ 5 .. 15 ];;

val a : Set<int>
val b : Set<int>

> Set.iter (fun x -> printf "%O " x) (Set.intersect a b);;
5 6 7 8 9 10

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.
> let a = Set.ofSeq [ 1 .. 10 ]
let b = Set.ofSeq [ 5 .. 15 ]
let c = Set.ofSeq [ 2; 4; 5; 9 ];;

val a : Set<int>
val b : Set<int>
val c : Set<int>

> Set.isSubset c a;; (* All elements of 'c' exist in 'a' *)
val it : bool = true

> Set.isSubset c b;; (* Not all of the elements of 'c' exist in 'b' *);;
val it : bool = false

val union : Set<'a> -> Set<'a> -> Set<'a>

Compute the union of the two sets.
> let a = Set.ofSeq [ 1 .. 10 ]
let b = Set.ofSeq [ 5 .. 15 ];;

val a : Set<int>
val b : Set<int>

> Set.iter (fun x -> printf "%O " x) (Set.union a b);;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 val it : unit = ()

> Set.iter (fun x -> printf "%O " x) (a + b);; (* '+' computes union *)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Examples[edit]

open System

let shakespeare = "O Romeo, Romeo! wherefore art thou Romeo?"
let shakespeareArray =
    shakespeare.Split([| ' '; ','; '!'; '?' |], StringSplitOptions.RemoveEmptyEntries)
let shakespeareSet = shakespeareArray |> Set.ofSeq
    
let main() =
    printfn "shakespeare: %A" shakespeare
    
    let printCollection msg coll =
        printfn "%s:" msg
        Seq.iteri (fun index item -> printfn "  %i: %O" index item) coll
        
    printCollection "shakespeareArray" shakespeareArray
    printCollection "shakespeareSet" shakespeareSet
    
    Console.ReadKey(true) |> ignore
            
main()
shakespeare: "O Romeo, Romeo! wherefore art thou Romeo?"
shakespeareArray:
  0: O
  1: Romeo
  2: Romeo
  3: wherefore
  4: art
  5: thou
  6: Romeo
shakespeareSet:
  0: O
  1: Romeo
  2: art
  3: thou
  4: wherefore

Maps[edit]

A map is a special kind of set: it associates keys with values. A map is created in a similar way to sets:

> let holidays =
    Map.empty. (* Start with empty Map *)
        Add("Christmas", "Dec. 25").
        Add("Halloween", "Oct. 31").
        Add("Darwin Day", "Feb. 12").
        Add("World Vegan Day", "Nov. 1");;

val holidays : Map<string,string>

> let monkeys =
    [ "Squirrel Monkey", "Simia sciureus";
        "Marmoset", "Callithrix jacchus";
        "Macaque", "Macaca mulatta";
        "Gibbon", "Hylobates lar";
        "Gorilla", "Gorilla gorilla";
        "Humans", "Homo sapiens";
        "Chimpanzee", "Pan troglodytes" ]
    |> Map.ofList;; (* Convert list to Map *)

val monkeys : Map<string,string>

You can use the .[key] to access elements in the map:

> holidays.["Christmas"];;
val it : string = "Dec. 25"

> monkeys.["Marmoset"];;
val it : string = "Callithrix jacchus"

The Map Module[edit]

The Microsoft.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[edit]

open System

let capitals =
    [("Australia", "Canberra"); ("Canada", "Ottawa"); ("China", "Beijing");
        ("Denmark", "Copenhagen"); ("Egypt", "Cairo"); ("Finland", "Helsinki");
        ("France", "Paris"); ("Germany", "Berlin"); ("India", "New Delhi");
        ("Japan", "Tokyo"); ("Mexico", "Mexico City"); ("Russia", "Moscow");
        ("Slovenia", "Ljubljana"); ("Spain", "Madrid"); ("Sweden", "Stockholm");
        ("Taiwan", "Taipei"); ("USA", "Washington D.C.")]
    |> Map.ofList

let rec main() =
    Console.Write("Find a capital by country (type 'q' to quit): ")
    match Console.ReadLine() with
    | "q" -> Console.WriteLine("Bye bye")
    | country ->
        match capitals.TryFind(country) with
        | Some(capital) -> Console.WriteLine("The capital of {0} is {1}\n", country, capital)
        | None -> Console.WriteLine("Country not found.\n")
        main() (* loop again *)
            
main()
Find a capital by country (type 'q' to quit): Egypt
The capital of Egypt is Cairo

Find a capital by country (type 'q' to quit): Slovenia
The capital of Slovenia is Ljubljana

Find a capital by country (type 'q' to quit): Latveria
Country not found.

Find a capital by country (type 'q' to quit): USA
The capital of USA is Washington D.C.

Find a capital by country (type 'q' to quit): q
Bye bye

Set and Map Performance[edit]

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.

Previous: Sequences Index Next: Discriminated Unions



Discriminated Unions

Previous: Sets and Maps Index Next: Mutable Data
F# : 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[edit]

Discriminated unions are defined using the following syntax:

type unionName =
    | Case1
    | Case2 of datatype
    | ...

By convention, union names start with a lowercase character, and union cases are written in PascalCase.

Union basics: an On/Off switch[edit]

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:

type switchstate =
    | On
    | Off

We've defined a union called switchstate which has two cases, On and Off. You can create and use instances of switchstate as follows:

type switchstate =
    | On
    | Off
    
let x = On    (* creates an instance of switchstate *)
let y = Off   (* creates another instance of switchstate *)
    
let main() =
    printfn "x: %A" x
    printfn "y: %A" y
    
main()

This program has the following types:

type switchstate = On | Off
val x : switchstate
val y : switchstate

It outputs the following:

x: On
y: Off

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:

type switchstate =
    | On
    | Off
    
let toggle = function  (* pattern matching input *)
    | On -> Off
    | Off -> On
    
let main() =
    let x = On
    let y = Off
    let z = toggle y
    
    printfn "x: %A" x
    printfn "y: %A" y
    printfn "z: %A" z
    printfn "toggle z: %A" (toggle z)
    
main()

The function toggle has the type val toggle : switchstate -> switchstate.

This program has the following output:

x: On
y: Off
z: On
toggle z: Off

Holding Data In Unions: a dimmer switch[edit]

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:

type switchstate =
    | On
    | Off
    | Adjustable of float

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:

open System

type switchstate =
    | On
    | Off
    | Adjustable of float
    
let toggle = function
    | On -> Off
    | Off -> On
    | Adjustable(brightness) ->
        (* Matches any switchstate of type Adjustable. Binds
        the value passed into the constructor to the variable
        'brightness'. Toggles dimness around the halfway point. *)
        let pivot = 0.5
        if brightness <= pivot then
            Adjustable(brightness + pivot)
        else
            Adjustable(brightness - pivot)

let main() =
    let x = On
    let y = Off
    let z = Adjustable(0.25) (* takes a float in constructor *)
    
    printfn "x: %A" x
    printfn "y: %A" y
    printfn "z: %A" z
    printfn "toggle z: %A" (toggle z)
    
    Console.ReadKey(true) |> ignore
    
main()

This program outputs:

x: On
y: Off
z: Adjustable 0.25
toggle z: Adjustable 0.75

Creating Trees[edit]

Discriminated unions can easily model a wide variety of trees and hierarchical data structures.

For example, let's consider the following binary tree:

Binary tree with 5 leaf nodes

Each node of our tree contains exactly two branches, and each branch can either be a integer or another tree. We can represent this tree as follows:

type tree =
    | Leaf of int
    | Node of tree * tree

We can create an instance of the tree above using the following code:

open System

type tree =
    | Leaf of int
    | Node of tree * tree
    
let simpleTree =
    Node(
        Leaf 1,
        Node(
            Leaf 2,
            Node(
                Node(
                    Leaf 4,
                    Leaf 5
                ),
                Leaf 3
            )
        )
    )
    
let main() =
    printfn "%A" simpleTree
    Console.ReadKey(true) |> ignore
    
main()

This program outputs the following:

Node (Leaf 1,Node (Leaf 2,Node (Node (Leaf 4,Leaf 5),Leaf 3)))

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:

open System

type tree =
    | Leaf of int
    | Node of tree * tree

let simpleTree =
    Node (Leaf 1, Node (Leaf 2, Node (Node (Leaf 4, Leaf 5), Leaf 3)))
    
let countLeaves tree =
    let rec loop sum = function
        | Leaf(_) -> sum + 1
        | Node(tree1, tree2) ->
            sum + (loop 0 tree1) + (loop 0 tree2)
    loop 0 tree
    
let main() =
    printfn "countLeaves simpleTree: %i" (countLeaves simpleTree)
    Console.ReadKey(true) |> ignore
    
main()

This program outputs:

countLeaves simpleTree: 5

Generalizing Unions For All Datatypes[edit]

Note that our binary tree above only operates on integers. Its possible to construct unions which are generalized to operate on all possible data types. We can modify the definition of our union to the following:

type 'a tree =
    | Leaf of 'a
    | Node of 'a tree * 'a tree

(* The syntax above is "OCaml" style. It's common to see 
   unions defined using the ".NET" style as follows which
   surrounds the type parameter with <'s and >'s after the 
   type name:

type tree<'a> =
    | Leaf of 'a
    | Node of tree<'a> * tree<'a>
*)

We can use the union define above to define a binary tree of any data type:

open System

type 'a tree =
    | Leaf of 'a
    | Node of 'a tree * 'a tree  
    
let firstTree =
    Node(
        Leaf 1,
        Node(
            Leaf 2,
            Node(
                Node(
                    Leaf 4,
                    Leaf 5
                ),
                Leaf 3
            )
        )
    )
    
let secondTree = 
    Node(
        Node(
            Node(
                Leaf "Red",
                Leaf "Orange"
            ),
            Node(
                Leaf "Yellow",
                Leaf "Green"
            )
        ),
        Node(
            Leaf "Blue",
            Leaf "Violet"
        )
    )
    
let prettyPrint tree =
    let rec loop depth tree =
        let spacer = new String(' ', depth)
        match tree with
        | Leaf(value) ->        
            printfn "%s |- %A" spacer value
        | Node(tree1, tree2) ->
            printfn "%s |" spacer
            loop (depth + 1) tree1
            loop (depth + 1) tree2
    loop 0 tree
    
let main() =
    printfn "firstTree:"
    prettyPrint firstTree
    
    printfn "secondTree:"
    prettyPrint secondTree
    Console.ReadKey(true) |> ignore
    
main()

The functions above have the following types:

type 'a tree =
    | Leaf of 'a
    | Node of 'a tree * 'a tree

val firstTree : int tree
val secondTree : string tree
val prettyPrint : 'a tree -> unit

This program outputs:

firstTree:
 |
  |- 1
  |
   |- 2
   |
    |
     |- 4
     |- 5
    |- 3
secondTree:
 |
  |
   |
    |- "Red"
    |- "Orange"
   |
    |- "Yellow"
    |- "Green"
  |
   |- "Blue"
   |- "Violet"

Examples[edit]

Built-in Union Types[edit]

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

type 'a list = 
    | Cons of 'a * 'a list
    | Nil

type 'a option =
    | Some of 'a
    | None

Propositional Logic[edit]

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, lets limit our propositions to four possible cases:

type proposition =
    | True
    | Not of proposition
    | And of proposition * proposition
    | Or of proposition * proposition

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:

let rec eval = function
    | True -> true
    | Not(prop) -> not (eval(prop))
    | And(prop1, prop2) -> eval(prop1) && eval(prop2)
    | Or(prop1, prop2) -> eval(prop1) || eval(prop2)

The eval function has the type val eval : proposition -> bool.

Here is a full program using the eval function:

open System
 
type proposition =
    | True
    | Not of proposition
    | And of proposition * proposition
    | Or of proposition * proposition
 
let prop1 =
    (* ~t || ~~t *)
    Or(
        Not True,
        Not (Not True)
    )
 
let prop2 =
    (* ~(t && ~t) || ( (t || t) || ~t) *)
    Or(
        Not(
            And(
                True,
                Not True
            )
        ),
        Or(
            Or(
                True,
                True
            ),
            Not True
        )
    )
 
let prop3 = 
    (* ~~~~~~~t *)
    Not(Not(Not(Not(Not(Not(Not True))))))
 
let rec eval = function
    | True -> true
    | Not(prop) -> not (eval(prop))
    | And(prop1, prop2) -> eval(prop1) && eval(prop2)
    | Or(prop1, prop2) -> eval(prop1) || eval(prop2)
 
let main() =
    let testProp name prop = printfn "%s: %b" name (eval prop)
    
    testProp "prop1" prop1
    testProp "prop2" prop2
    testProp "prop3" prop3
 
    Console.ReadKey(true) |> ignore
 
main()

This program outputs the following:

prop1: true
prop2: true
prop3: false

Additional Reading[edit]

Theorem Proving Examples (OCaml)

Previous: Sets and Maps Index Next: Mutable Data



Mutable Data

Previous: Discriminated Unions Index Next: Control Flow
F# : 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[edit]

The simplest mutable variables in F# are declared using the mutable keyword. Here is a sample using fsi:

> let mutable x = 5;;

val mutable x : int

> x;;
val it : int = 5

> x <- 10;;
val it : unit = ()

> x;;
val it : int = 10

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:

open System
    
type transactionItem =
    { ID : int;
        mutable IsProcessed : bool;
        mutable ProcessedText : string; }
        
let getItem id =
    { ID = id;
        IsProcessed = false;
        ProcessedText = null; }
        
let processItems (items : transactionItem list) =
    items |> List.iter(fun item ->
        item.IsProcessed <- true
        item.ProcessedText <- sprintf "Processed %s" (DateTime.Now.ToString("hh:mm:ss"))
        
        Threading.Thread.Sleep(1000) (* Putting thread to sleep for 1 second to simulate
                                        processing overhead. *)
        )

let printItems (items : transactionItem list) =
        items |> List.iter (fun x -> printfn "%A" x)

let main() =
    let items = List.init 5 getItem
    
    printfn "Before process:"
    printItems items
    
    printfn "After process:"
    processItems items
    printItems items
    
    Console.ReadKey(true) |> ignore
 
main()
Before process:
{ID = 0;
 IsProcessed = false;
 ProcessedText = null;}
{ID = 1;
 IsProcessed = false;
 ProcessedText = null;}
{ID = 2;
 IsProcessed = false;
 ProcessedText = null;}
{ID = 3;
 IsProcessed = false;
 ProcessedText = null;}
{ID = 4;
 IsProcessed = false;
 ProcessedText = null;}
After process:
{ID = 0;
 IsProcessed = true;
 ProcessedText = "Processed 10:00:31";}
{ID = 1;
 IsProcessed = true;
 ProcessedText = "Processed 10:00:32";}
{ID = 2;
 IsProcessed = true;
 ProcessedText = "Processed 10:00:33";}
{ID = 3;
 IsProcessed = true;
 ProcessedText = "Processed 10:00:34";}
{ID = 4;
 IsProcessed = true;
 ProcessedText = "Processed 10:00:35";}

Limitations of Mutable Variables[edit]

Mutable variables are somewhat limited: with early version of F#, mutables are 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:

> let testMutable() =
    let mutable msg = "hello"
    printfn "%s" msg
    
    let setMsg() =
        msg <- "world"
    
    setMsg()
    printfn "%s" msg;;

          msg <- "world"
  --------^^^^^^^^^^^^^^^

stdin(18,9): error FS0191: The mutable variable 'msg' is used in an invalid way. Mutable
variables may not be captured by closures. Consider eliminating this use of mutation or
using a heap-allocated mutable reference cell via 'ref' and '!'.

Ref cells[edit]

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:

type 'a ref = { mutable contents : 'a }

The F# library contains several built-in functions and operators for working with ref cells:

let ref v = { contents = v }      (* val ref  : 'a -> 'a ref *)
let (!) r = r.contents            (* val (!)  : 'a ref -> 'a *)
let (:=) r v = r.contents <- v    (* val (:=) : 'a ref -> 'a -> unit *)

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:

> let x = ref "hello";;

val x : string ref

> x;; (* returns ref instance *)
val it : string ref = {contents = "hello";}

> !x;; (* returns x.contents *)
val it : string = "hello"

> x := "world";; (* updates x.contents with a new value *)
val it : unit = ()

> !x;; (* returns x.contents *)
val it : string = "world"

Since ref cells are allocated on the heap, they can be shared across multiple functions:

open System

let withSideEffects x =
    x := "assigned from withSideEffects function"
   
let refTest() =
    let msg = ref "hello"
    printfn "%s" !msg
    
    let setMsg() =
        msg := "world"
    
    setMsg()
    printfn "%s" !msg
    
    withSideEffects msg
    printfn "%s" !msg

let main() =
    refTest()
    Console.ReadKey(true) |> ignore
 
main()

The withSideEffects function has the type val withSideEffects : string ref -> unit.

This program outputs the following:

hello
world
assigned from withSideEffects function

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[edit]

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:

Three references to an integer with value 7

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:

Three references to an integer with value 10

By assigning cell1.contents a new value, the variables cell2 and cell3 were changed as well. This can be demonstrated using fsi as follows:

> let cell1 = ref 7;;
val cell1 : int ref

> let cell2 = cell1;;
val cell2 : int ref

> let cell3 = cell2;;
val cell3 : int ref

> !cell1;;
val it : int = 7

> !cell2;;
val it : int = 7

> !cell3;;
val it : int = 7

> cell1 := 10;;
val it : unit = ()

> !cell1;;
val it : int = 10

> !cell2;;
val it : int = 10

> !cell3;;
val it : int = 10

Encapsulating Mutable State[edit]

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:

> let incr =
    let counter = ref 0
    fun () ->
        counter := !counter + 1
        !counter;;

val incr : (unit -> int)

> incr();;
val it : int = 1

> incr();;
val it : int = 2

> incr();;
val it : int = 3
Previous: Discriminated Unions Index Next: Control Flow



Control Flow

Previous: Mutable Data Index Next: Arrays
F# : 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[edit]

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[edit]

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:

(* simple if *)
if expr then
    expr

(* binary if *)
if expr then
    expr
else
    expr

(* multiple else branches *)
if expr then
    expr
elif expr then
    expr
elif expr then
    expr
...
else
    expr

Like all F# blocks, the scope of an if statement extends to any code indented under it. For example:

open System

let printMessage condition =
    if condition then
        printfn "condition = true: inside the 'if'"
    printfn "outside the 'if' block"

let main() =
    printMessage true
    printfn "--------"
    printMessage false
    Console.ReadKey(true) |> ignore
 
main()

This program prints:

condition = true: inside the 'if'
outside the 'if' block
--------
outside the 'if' block

Working With Conditions[edit]

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#:

open System

let alwaysTrue() =
    printfn "Always true"
    true
    
let alwaysFalse() =
    printfn "Always false"
    false

let main() =
    let testCases = 
        ["alwaysTrue && alwaysFalse", fun() -> alwaysTrue() && alwaysFalse();
         "alwaysFalse && alwaysTrue", fun() -> alwaysFalse() && alwaysTrue();
         "alwaysTrue || alwaysFalse", fun() -> alwaysTrue() || alwaysFalse();
         "alwaysFalse || alwaysTrue", fun() -> alwaysFalse() || alwaysTrue();]
    
    testCases |> List.iter (fun (msg, res) ->
        printfn "%s: %b" msg (res())
        printfn "-------")
    
    Console.ReadKey(true) |> ignore
 
main()

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:

Always true
Always false
alwaysTrue && alwaysFalse: false
-------
Always false
alwaysFalse && alwaysTrue: false
-------
Always true
alwaysTrue || alwaysFalse: true
-------
Always false
Always true
alwaysFalse || alwaysTrue: true
-------

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[edit]

for loops are traditionally used to iterate over a well-defined integer range. The syntax of a for loop is defined as:

for var = start-expr to end-expr do
    ... // loop body

Here's a trivial program which prints out the numbers 1 - 10:

let main() =
    for i = 1 to 10 do
        printfn "i: %i" i
main()

This program outputs:

i: 1
i: 2
i: 3
i: 4
i: 5
i: 6
i: 7
i: 8
i: 9
i: 10

This code takes input from the user to compute an average:

open System

let main() =
    Console.WriteLine("This program averages numbers input by the user.")
    Console.Write("How many numbers do you want to add? ")
    
    let mutable sum = 0
    let numbersToAdd = Console.ReadLine() |> int
    
    for i = 1 to numbersToAdd do
        Console.Write("Input #{0}: ", i)
        let input = Console.ReadLine() |> int
        sum <- sum + input
    
    let average = sum / numbersToAdd
    Console.WriteLine("Average: {0}", average)
        
main()

This program outputs:

This program averages numbers input by the user.
How many numbers do you want to add? 3
Input #1: 100
Input #2: 90
Input #3: 50
Average: 80

for Loops Over Collections and Sequences[edit]

Its often convenient to iterate over collections of items using the syntax:

for pattern in expr do
    ... // loop body

For example, we can print out a shopping list in fsi:

> let shoppingList =
    ["Tofu", 2, 1.99;
    "Seitan", 2, 3.99;
    "Tempeh", 3, 2.69;
    "Rice milk", 1, 2.95;];;

val shoppingList : (string * int * float) list

> for (food, quantity, price) in shoppingList do
    printfn "food: %s, quantity: %i, price: %g" food quantity price;;
food: Tofu, quantity: 2, price: 1.99
food: Seitan, quantity: 2, price: 3.99
food: Tempeh, quantity: 3, price: 2.69
food: Rice milk, quantity: 1, price: 2.95

while Loops[edit]

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:

while expr do
    ... // loop body

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:

open System

let main() =
    let password = "monkey"
    let mutable guess = String.Empty
    let mutable attempts = 0
    
    while password <> guess && attempts < 3 do
        Console.Write("What's the password? ")
        attempts <- attempts + 1
        guess <- Console.ReadLine()
        
    if password = guess then
        Console.WriteLine("You got the password right!")
    else
        Console.WriteLine("You didn't guess the password")
        
    Console.ReadKey(true) |> ignore
    
        
main()

This program outputs the following:

What's the password? kitty
What's the password? monkey
You got the password right!
Previous: Mutable Data Index Next: Arrays



Arrays

Previous: Control Flow Index Next: Mutable Collections
F# : 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[edit]

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

Array literals[edit]

> [| 1; 2; 3; 4; 5 |];;
val it : int array = [|1; 2; 3; 4; 5|]

Array comprehensions[edit]

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

> [| 1 .. 10 |];;
val it : int array = [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10|]

> [| 1 .. 3 .. 10 |];;
val it : int array = [|1; 4; 7; 10|]

> [| for a in 1 .. 5 do
    yield (a, a*a, a*a*a) |];;
val it : (int * int * int) array
= [|(1, 1, 1); (2, 4, 8); (3, 9, 27); (4, 16, 64); (5, 25, 125)|]

System.Array Methods[edit]

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).
> let (x : int array) = Array.zeroCreate 5;;
val x : int array

> x;;
val it : int array = [|0; 0; 0; 0; 0|]

val create : int -> 'T value -> 'T []

Creates an array with arraySize elements. Initializes each element in the array with value.
> Array.create 5 "Juliet";;
val it : string [] = [|"Juliet"; "Juliet"; "Juliet"; "Juliet"; "Juliet"|]

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.
> Array.init 5 (fun index -> sprintf "index: %i" index);;
val it : string []
= [|"index: 0"; "index: 1"; "index: 2"; "index: 3"; "index: 4"|]

Working With Arrays[edit]

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:

let names = [| "Juliet"; "Monique"; "Rachelle"; "Tara"; "Sophia" |]
(* Indexes:        0         1           2         3        4 *)

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:

> let names = [| "Juliet"; "Monique"; "Rachelle"; "Tara"; "Sophia" |];;

val names : string array

> names.[2];;
val it : string = "Rachelle"

> names.[0];;
val it : string = "Juliet"

Instances of arrays have a Length property which returns the number of elements in the array:

> names.Length;;
val it : int = 5

> for i = 0 to names.Length - 1 do
    printfn "%s" (names.[i]);;
Juliet
Monique
Rachelle
Tara
Sophia

Arrays are mutable data structures, meaning we can assign elements in an array new values at any point in our program:

> names;;
val it : string array = [|"Juliet"; "Monique"; "Rachelle"; "Tara"; "Sophia"|]

> names.[4] <- "Kristen";;
val it : unit = ()

> names;;
val it : string array = [|"Juliet"; "Monique"; "Rachelle"; "Tara"; "Kristen"|]

If you try to access an element outside the range of an array, you'll get an exception:

> names.[-1];;
System.IndexOutOfRangeException: Index was outside the bounds of the array.
   at <StartupCode$FSI_0029>.$FSI_0029._main()
stopped due to error

> names.[5];;
System.IndexOutOfRangeException: Index was outside the bounds of the array.
   at <StartupCode$FSI_0030>.$FSI_0030._main()
stopped due to error

Array Slicing[edit]

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.

> let names = [|"0: Juliet"; "1: Monique"; "2: Rachelle"; "3: Tara"; "4: Sophia"|];;

val names : string array

> names.[1..3];; (* Grabs items between index 1 and 3 *)
val it : string [] = [|"1: Monique"; "2: Rachelle"; "3: Tara"|]

> names.[2..];; (* Grabs items between index 2 and last element *)
val it : string [] = [|"2: Rachelle"; "3: Tara"; "4: Sophia"|]

> names.[..3];; (* Grabs items between first element and index 3 *)
val it : string [] = [|"0: Juliet"; "1: Monique"; "2: Rachelle"; "3: Tara"|]

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[edit]

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[edit]

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:

> Array2D.zeroCreate<int> 2 3;;
val it : int [,] = [|[|0; 0; 0|]; [|0; 0; 0|]|]

This array has 2 rows, and each row has 3 columns. To access elements in this array, you use the .[row,col] operator:

> let grid = Array2D.init<string> 3 3 (fun row col -> sprintf "row: %i, col: %i" row col);;

val grid : string [,]

> grid;;
val it : string [,]
= [|[|"row: 0, col: 0"; "row: 0, col: 1"; "row: 0, col: 2"|];
    [|"row: 1, col: 0"; "row: 1, col: 1"; "row: 1, col: 2"|];
    [|"row: 2, col: 0"; "row: 2, col: 1"; "row: 2, col: 2"|]|]

> grid.[0, 1];;
val it : string = "row: 0, col: 1"

> grid.[1, 2];;
val it : string = "row: 1, col: 2"

Here's a simple program to demonstrate how to use and iterate through multidimensional arrays:

open System

let printGrid grid =
    let maxY = (Array2D.length1 grid) - 1
    let maxX = (Array2D.length2 grid) - 1
    
    for row in 0 .. maxY do
        for col in 0 .. maxX do
            if grid.[row, col] = true then Console.Write("* ")
            else Console.Write("_ ")
        Console.WriteLine()

let toggleGrid (grid : bool[,]) =
    Console.WriteLine()
    Console.WriteLine("Toggle grid:")
    
    let row =
        Console.Write("Row: ")
        Console.ReadLine() |> int
        
    let col =
        Console.Write("Col: ")
        Console.ReadLine() |> int
    
    grid.[row, col] <- (not grid.[row, col])

let main() =
    Console.WriteLine("Create a grid:")
    let rows =
        Console.Write("Rows: ")
        Console.ReadLine() |> int
        
    let cols =
        Console.Write("Cols: ")
        Console.ReadLine() |> int
        
    let grid = Array2D.zeroCreate<bool> rows cols
    printGrid grid
    
    let mutable go = true
    while go do
        toggleGrid grid
        printGrid grid
        Console.Write("Keep playing (y/n)? ")
        go <- Console.ReadLine() = "y"
    
    Console.WriteLine("Thanks for playing")
            
main()

This program outputs the following:

Create a grid:
Rows: 2
Cols: 3
_ _ _
_ _ _

Toggle grid:
Row: 0
Col: 1
_ * _
_ _ _
Keep playing (y/n)? y

Toggle grid:
Row: 1
Col: 1
_ * _
_ * _
Keep playing (y/n)? y

Toggle grid:
Row: 1
Col: 2
_ * _
_ * *
Keep playing (y/n)? n

Thanks for playing

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 can quickly consume all of the available memory on a machine. For comparison, an int is 4 bytes, and a 1000x1000x1000 int array would consume about 3.7 GB of memory, more than the memory available on 99% of desktop PCs.

Jagged arrays[edit]

A jagged array is an array of arrays, except each row in the array does not necessary need to have the same number of elements:

> [| for a in 1 .. 5 do yield [| 1 .. a |] |];;
val it : int array array
= [|[|1|];
    [|1; 2|];
    [|1; 2; 3|];
    [|1; 2; 3; 4|];
    [|1; 2; 3; 4; 5|]|]

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]:

> let jagged = [| for a in 1 .. 5 do yield [| 1 .. a |] |]
for arr in jagged do
    for col in arr do
        printf "%i " col
    printfn "";;

val jagged : int array array

1 
1 2 
1 2 3 
1 2 3 4 
1 2 3 4 5

> jagged.[2].[2];;
val it : int = 3

> jagged.[4].[0];;
val it : int = 1
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[edit]

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[edit]

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

Representation in Memory[edit]

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:

Memory Location: |  100 |  104 |  108 |  112 |  116
          Value: |   15 |    5 |   21 |    0 |    9
          Index: |    0 |    1 |    2 |    3 |    4

Each int occupies 4 bytes of memory. Since our array contains 5 elements, the operating systems allocates 20 bytes of memory to hold this array (4 bytes * 5 elements = 20 bytes). The first 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 it's 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 laymens terms, this means we can access the nth element of any 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:

  1. Creating arrays requires programmers to specify the size of the array upfront, otherwise the operating system won't know how many adjacent memory locations to allocate.
  2. 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.
Previous: Control Flow Index Next: Mutable Collections



Mutable Collections

Previous: Arrays Index Next: Input and Output
F# : 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[edit]

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:

> open System.Collections.Generic;;
> let myList = new List<string>();;

val myList : List<string>

> myList.Add("hello");;
val it : unit = ()
> myList.Add("world");;
val it : unit = ()
> myList.[0];;
val it : string = "hello"
> myList |> Seq.iteri (fun index item -> printfn "%i: %s" index myList.[index]);;
0: hello
1: world

It's easy to tell that .NET lists are mutable because their Add methods return unit rather than returning another list.

Underlying Implementation[edit]

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:

open System
open System.Collections.Generic

let items = new List<string>()

let printList (l : List<_>) =
    printfn "l.Count: %i, l.Capacity: %i" l.Count l.Capacity
    printfn "Items:"
    l |> Seq.iteri (fun index item ->
        printfn "    l.[%i]: %s" index l.[index])
    printfn "-----------"

let main() =
    printList items
    
    items.Add("monkey")
    printList items
    
    items.Add("kitty")
    items.Add("bunny")
    printList items
    
    items.Add("doggy")
    items.Add("octopussy")
    items.Add("ducky")
    printList items
    
    printfn "Removing entry for \"doggy\"\n--------\n"
    items.Remove("doggy") |> ignore
    printList items
    
    printfn "Removing item at index 3\n--------\n"
    items.RemoveAt(3)
    printList items
    
    Console.ReadKey(true) |> ignore
            
main()
l.Count: 0, l.Capacity: 0
Items:
-----------
l.Count: 1, l.Capacity: 4
Items:
    l.[0]: monkey
-----------
l.Count: 3, l.Capacity: 4
Items:
    l.[0]: monkey
    l.[1]: kitty
    l.[2]: bunny
-----------
l.Count: 6, l.Capacity: 8
Items:
    l.[0]: monkey
    l.[1]: kitty
    l.[2]: bunny
    l.[3]: doggy
    l.[4]: octopussy
    l.[5]: ducky
-----------
Removing entry for "doggy"
--------

l.Count: 5, l.Capacity: 8
Items:
    l.[0]: monkey
    l.[1]: kitty
    l.[2]: bunny
    l.[3]: octopussy
    l.[4]: ducky
-----------
Removing item at index 3
--------

l.Count: 4, l.Capacity: 8
Items:
    l.[0]: monkey
    l.[1]: kitty
    l.[2]: bunny
    l.[3]: ducky
-----------

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:

> let myList = new List<int>(1000);;

val myList : List<int>

> myList.Count, myList.Capacity;;
val it : int * int = (0, 1000)
> seq { 1 .. 1000 } |> Seq.iter (fun x -> myList.Add(x));;
val it : unit = ()
> myList.Count, myList.Capacity;;
val it : int * int = (1000, 1000)

LinkedList<'T> Class[edit]

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:

(* Prepends an item to the LinkedList *)
val AddFirst : 'T -> LinkedListNode<'T>

(* Appends an items to the LinkedList *)
val AddLast : 'T -> LinkedListNode<'T>

(* Adds an item before a LinkedListNode *)
val AddBefore : LinkedListNode<'T> -> 'T -> LinkedListNode<'T>

(* Adds an item after a LinkedListNode *)
val AddAfter : LinkedListNode<'T> -> 'T -> LinkedListNode<'T>

Note that these methods return a LinkedListNode<'T>, not a new LinkedList<'T>. Adding nodes actually mutates the LinkedList object:

> open System.Collections.Generic;;
> let items = new LinkedList<string>();;

val items : LinkedList<string>

> items.AddLast("AddLast1");;
val it : LinkedListNode<string>
= System.Collections.Generic.LinkedListNode`1[System.String]
    {List = seq ["AddLast1"];
     Next = null;
     Previous = null;
     Value = "AddLast1";}
> items.AddLast("AddLast2");;
val it : LinkedListNode<string>
= System.Collections.Generic.LinkedListNode`1[System.String]
    {List = seq ["AddLast1"; "AddLast2"];
     Next = null;
     Previous = System.Collections.Generic.LinkedListNode`1[System.String];
     Value = "AddLast2";}
> let firstItem = items.AddFirst("AddFirst1");;

val firstItem : LinkedListNode<string>

> let addAfter = items.AddAfter(firstItem, "addAfter");;

val addAfter : LinkedListNode<string>

> let addBefore = items.AddBefore(addAfter, "addBefore");;

val addBefore : LinkedListNode<string>

> items |> Seq.iter (fun x -> printfn "%s" x);;
AddFirst1
addBefore
addAfter
AddLast1
AddLast2

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[edit]

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.

> stack.Push("First");; (* Adds item to front of the list *)
val it : unit = ()
> stack.Push("Second");;
val it : unit = ()
> stack.Push("Third");;
val it : unit = ()
> stack.Pop();; (* Returns and removes item from front of the list *)
val it : string = "Third"
> stack.Pop();;
val it : string = "Second"
> stack.Pop();;
val it : string = "First"

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.

A simple representation of a stack

Queue<'T> Class[edit]

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.

> let queue = new Queue<string>();;

val queue : Queue<string>

> queue.Enqueue("First");; (* Adds item to the rear of the list *)
val it : unit = ()
> queue.Enqueue("Second");;
val it : unit = ()
> queue.Enqueue("Third");;
val it : unit = ()
> queue.Dequeue();; (* Returns and removes item from front of the queue *)
val it : string = "First"
> queue.Dequeue();;
val it : string = "Second"
> queue.Dequeue();;
val it : string = "Third"

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.

Queue algorithmn.jpg

HashSet<'T>, and Dictionary<'TKey, 'TValue> Classes[edit]

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>

open System
open System.Collections.Generic

let nums_1to10 = new HashSet<int>()
let nums_5to15 = new HashSet<int>()

let main() =
    let printCollection msg targetSet =
        printf "%s: " msg
        targetSet |> Seq.sort |> Seq.iter(fun x -> printf "%O " x)
        printfn ""
        
    let addNums min max (targetSet : ICollection<_>) =
        seq { min .. max } |> Seq.iter(fun x -> targetSet.Add(x))
        
    addNums 1 10 nums_1to10
    addNums 5 15 nums_5to15
    
    printCollection "nums_1to10 (before)" nums_1to10
    printCollection "nums_5to15 (before)" nums_5to15
    
    nums_1to10.IntersectWith(nums_5to15) (* mutates nums_1to10 *)
    printCollection "nums_1to10 (after)" nums_1to10
    printCollection "nums_5to15 (after)" nums_5to15
    
    Console.ReadKey(true) |> ignore
            
main()
nums_1to10 (before): 1 2 3 4 5 6 7 8 9 10
nums_5to15 (before): 5 6 7 8 9 10 11 12 13 14 15
nums_1to10 (after): 5 6 7 8 9 10
nums_5to15 (after): 5 6 7 8 9 10 11 12 13 14 15

Using the Dictionary<'TKey, 'TValue>

> open System.Collections.Generic;;
> let dict = new Dictionary<string, string>();;

val dict : Dictionary<string,string>

> dict.Add("Garfield", "Jim Davis");;
val it : unit = ()
> dict.Add("Farside", "Gary Larson");;
val it : unit = ()
> dict.Add("Calvin and Hobbes", "Bill Watterson");;
val it : unit = ()
> dict.Add("Peanuts", "Charles Schultz");;
val it : unit = ()
> dict.["Farside"];; (* Use the '.[key]' operator to retrieve items *)
val it : string = "Gary Larson"

Differences Between .NET BCL and F# Collections[edit]

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
LinkedList O(1) O(1) O(n) 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
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.
Previous: Arrays Index Next: Input and Output



Input and Output

Previous: Mutable Collections Index Next: Exception Handling
F# : Basic I/O


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[edit]

With F#[edit]

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:

> sprintf "Hi, I'm %s and I'm a %s" "Juliet" "Scorpio";;
val it : string = "Hi, I'm Juliet and I'm a Scorpio"

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:

> sprintf "I'm %i years old" "kitty";;

  sprintf "I'm %i years old" "kitty";;
  ---------------------------^^^^^^^^

stdin(17,28): error FS0001: The type 'string' is not compatible with any of the types
byte,int16,int32,int64,sbyte,uint16,uint32,uint64,nativeint,unativeint, arising from 
the use of a printf-style format string.

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.

> sprintf "%.2f" 12345.67890;;
val it : string = "12345.68"

> sprintf "%.7f" 12345.67890;;
val it : string = "12345.6789000"

[type] (required)

The following placeholder types are interpreted as follows:

     %b:         bool, formatted as "true" or "false"
     %s:         string, formatted as its unescaped contents
     %d, %i:     any basic integer type formatted as a decimal integer, signed if the basic integer type is signed.
     %u:         any basic integer type formatted as an unsigned decimal integer
     %x, %X, %o: any basic integer type formatted as an unsigned hexadecimal 
                 (a-f)/Hexadecimal (A-F)/Octal integer
 
     %e, %E, %f, %F, %g, %G: 
                 any basic floating point type (float,float32) formatted
                 using a C-style floating point format specifications, i.e
 
     %e, %E: Signed value having the form [-]d.dddde[sign]ddd where 
                 d is a single decimal digit, dddd is one or more decimal
                 digits, ddd is exactly three decimal digits, and sign 
                 is + or -
 
     %f:     Signed value having the form [-]dddd.dddd, where dddd is one
                 or more decimal digits. The number of digits before the 
                 decimal point depends on the magnitude of the number, and 
                 the number of digits after the decimal point depends on 
                 the requested precision.
 
     %g, %G: Signed value printed in f or e format, whichever is 
                 more compact for the given value and precision.
 
 
    %M:      System.Decimal value
 
    %O:      Any value, printed by boxing the object and using it's ToString method(s)
 
    %A:      Any value, printed by using Microsoft.FSharp.Text.StructuredFormat.Display.any_to_string with the default layout settings 
 
    %a:      A general format specifier, requires two arguments:
                 (1) a function which accepts two arguments:
                     (a) a context parameter of the appropriate type for the
                         given formatting function (e.g. an #System.IO.TextWriter)
                     (b) a value to print
                         and which either outputs or returns appropriate text.
 
                 (2) the particular value to print
 
 
    %t:      A general format specifier, requires one argument:
                 (1) a function which accepts a context parameter of the
                     appropriate type for the given formatting function (e.g. 
                     an #System.IO.TextWriter)and which either outputs or returns 
                     appropriate text.

  Basic integer types are:
     byte,sbyte,int16,uint16,int32,uint32,int64,uint64,nativeint,unativeint
  Basic floating point types are:
     float, float32

Programmers can print to the console using the printf method, however F# recommends reading console input using the System.Console.ReadLine() method.

With .NET[edit]

.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:

> System.String.Format("Hi, my name is {0} and I'm a {1}", "Juliet", "Scorpio");;
val it : string = "Hi, my name is Juliet and I'm a Scorpio"

> System.String.Format("|{0,-50}|", "Left justified");;
val it : string = "|Left justified                                    |"

> System.String.Format("|{0,50}|", "Right justified");;
val it : string = "|                                   Right justified|"

> System.String.Format("|{0:yyyy-MMM-dd}|", System.DateTime.Now);;
val it : string = "|2009-Apr-06|"

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:

open System

let main() =
    Console.Write("What's your name? ")
    let name = Console.ReadLine()
    Console.Write("Hello, {0}", name)
    
main()

System.IO Namespace[edit]

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

Files and Directories[edit]

The following classes are useful for interrogating the host filesystem:

Streams[edit]

A stream is a sequence of bytes. .NET provides some classes which allow programmers to work with steams including:

Previous: Mutable Collections Index Next: Exception Handling



Exception Handling

Previous: Input and Output Index Next: Operator Overloading
F# : 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[edit]

Let's look at the following code:

let getNumber msg = printf msg; int32(System.Console.ReadLine())

let x = getNumber("x = ")
let y = getNumber("y = ")
printfn "%i + %i = %i" x y (x + y)

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:

x = 7
y = monkeys!
------------
FormatException was unhandled. Input string was not in a correct format.

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:

let getNumber msg =
    printf msg;
    try
        int32(System.Console.ReadLine())
    with
        | :? System.FormatException -> System.Int32.MinValue

let x = getNumber("x = ")
let y = getNumber("y = ")
printfn "%i + %i = %i" x y (x + y)

This program outputs the following:

x = 7
y = monkeys!
7 + -2147483648 = -2147483641

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:

let getNumber msg =
    printf msg;
    try
        int32(System.Console.ReadLine())
    with
        | :? System.FormatException -> -1
        | :? System.OverflowException -> System.Int32.MinValue
        | :? System.ArgumentNullException -> 0

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[edit]

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:

(* General failure *)
val failwith : string -> 'a

(* General failure with formatted message *)
val failwithf : StringFormat<'a, 'b> -> 'a

(* Raise a specific exception *)
val raise : #exn -> 'a

(* Bad input *)
val invalidArg : string -> 'a

For example:

type 'a tree =
    | Node of 'a * 'a tree * 'a tree
    | Empty
    
let rec add x = function
    | Empty -> Node(x, Empty, Empty)
    | Node(y, left, right) ->
        if x > y then Node(y, left, add x right)
        else if x < y then Node(y, add x left, right)
        else failwithf "Item '%A' has already been added to tree" x

Try/Finally[edit]

Normally, an exception will cause a function to exit immediately. However, a finally block will always execute, even if the code throws an exception:

let tryWithFinallyExample f =
    try
        printfn "tryWithFinallyExample: outer try block"
        try
            printfn "tryWithFinallyExample: inner try block"
            f()
        with
            | exn ->
                printfn "tryWithFinallyExample: inner with block"
                reraise() (* raises the same exception we just caught *)
    finally
        printfn "tryWithFinally: outer finally block"
        
let catchAllExceptions f =
    try
        printfn "-------------"
        printfn "catchAllExceptions: try block"
        tryWithFinallyExample f
    with
        | exn ->
            printfn "catchAllExceptions: with block"
            printfn "Exception message: %s" exn.Message
    
let main() =                
    catchAllExceptions (fun () -> printfn "Function executed successfully")
    catchAllExceptions (fun () -> failwith "Function executed with an error")
    
main()

This program will output the following:

-------------
catchAllExceptions: try block
tryWithFinallyExample: outer try block
tryWithFinallyExample: inner try block
Function executed successfully
tryWithFinally: outer finally block
-------------
catchAllExceptions: try block
tryWithFinallyExample: outer try block
tryWithFinallyExample: inner try block
tryWithFinallyExample: inner with block
tryWithFinally: outer finally block
catchAllExceptions: with block
Exception message: Function executed with an error

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):

open System.Data.SqlClient
let executeScalar connectionString sql =
    let conn = new SqlConnection(connectionString)
    try
        conn.Open() (* this line can throw an exception *)
        let comm = new SqlCommand(sql, conn)
        comm.ExecuteScalar() (* this line can throw an exception *)
    finally
        (* finally block guarantees our SqlConnection is closed, even if our sql statement fails *)
        conn.Close()

use Statement[edit]

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:

let writeToFile fileName =
    let sw = new System.IO.StreamWriter(fileName : string)
    try
        sw.Write("Hello ")
        sw.Write("World!")
    finally
        sw.Dispose()

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:

let writeToFile fileName =
    use sw = new System.IO.StreamWriter(fileName : string)
    sw.Write("Hello ")
    sw.Write("World!")

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[edit]

F# allows us to easily define new types of exceptions using the exception declaration. Here's an example using fsi:

> exception ReindeerNotFoundException of string

let reindeer =
    ["Dasher"; "Dancer"; "Prancer"; "Vixen"; "Comet"; "Cupid"; "Donner"; "Blitzen"]
    
let getReindeerPosition name =
    match List.tryFindIndex (fun x -> x = name) reindeer with
    | Some(index) -> index
    | None -> raise (ReindeerNotFoundException(name));;

exception ReindeerNotFoundException of string
val reindeer : string list
val getReindeerPosition : string -> int

> getReindeerPosition "Comet";;
val it : int = 4

> getReindeerPosition "Donner";;
val it : int = 6

> getReindeerPosition "Rudolf";;
FSI_0033+ReindeerNotFoundExceptionException: Rudolf
   at FSI_0033.getReindeerPosition(String name)
   at <StartupCode$FSI_0036>.$FSI_0036._main()
stopped due to error

We can pattern match on our new existing exception type just as easily as any other exception:

> let tryGetReindeerPosition name =
    try
        getReindeerPosition name
    with
        | ReindeerNotFoundException(s) ->
            printfn "Got ReindeerNotFoundException: %s" s
            -1;;

val tryGetReindeerPosition : string -> int

> tryGetReindeerPosition "Comet";;
val it : int = 4

> tryGetReindeerPosition "Rudolf";;
Got ReindeerNotFoundException: Rudolf
val it : int = -1

Exception Handling Constructs[edit]

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
Previous: Input and Output Index Next: Operator Overloading



Operator Overloading

Previous: Exception Handling Index Next: Classes
F# : 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[edit]

You've already used operators:

let sum = x + y

Here + is example of using a mathematical addition operator.

Operator Overloading[edit]

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:

type Complex =
    {   Re: double
        Im: double }
    static member ( + ) (left: Complex, right: Complex) =
        { Re = left.Re + right.Re; Im = left.Im + right.Im }

In FSI, we can add two complex numbers as follows:

> let first = { Re = 1.0; Im = 7.0 };;
val first : Complex

> let second = { Re = 2.0; Im = -10.5 };;
val second : Complex

> first + second;;
val it : Complex = {Re = 3.0;
                    Im = -3.5;}

Defining New Operators[edit]

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[edit]

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:

let (op) arg1 arg2 = ...

In addition to mathematical operators, F# has a variety of infix operators defined as part of its library, for example:

let inline (|>) x f = f x
let inline (::) hd tl = Cons(hd, tl)
let inline (:=) (x : 'a ref) value = x.contents <- value

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:

open System.Text.RegularExpressions

let (=~) input pattern =
    Regex.IsMatch(input, pattern)

let main() =
    printfn "cat =~ dog: %b" ("cat" =~ "dog")
    printfn "cat =~ cat|dog: %b" ("cat" =~ "cat|dog")
    printfn "monkey =~ monk*: %b" ("monkey" =~ "monk*")
 
main()

This program outputs the following:

cat =~ dog: false
cat =~ cat|dog: true
monkey =~ monk*: true

Prefix Operators[edit]

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:

type 'a ref = { mutable contents : 'a }
let (!) (x : 'a ref) = x.contents

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:

> let ( !+ ) l = List.reduce ( + ) l
let ( !- ) l = List.reduce ( - ) l
let ( !* ) l = List.reduce ( * ) l
let ( !/ ) l = List.reduce ( / ) l;;

val ( !+ ) : int list -> int
val ( !- ) : int list -> int
val ( !* ) : int list -> int
val ( !/ ) : int list -> int

> !* [2; 3; 5];;
val it : int = 30

> !+ [2; 3; 5];;
val it : int = 10

> !- [2; 3; 7];;
val it : int = -8

> !/ [100; 10; 2];;
val it : int = 5
Previous: Exception Handling Index Next: Classes



Classes

Previous: Operator Overloading Index Next: Inheritance
F# : Classes and Objects


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[edit]

Before you create an object, you have to identify the properties of your object and describe what it does. 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[edit]

Implicit class syntax is defined as follows:

type TypeName optional-type-arguments arguments [ as ident ] =
    [ inherit type { as base } ]
    [ let-binding | let-rec bindings ] *
    [ do-statement ] *
    [ abstract-binding | member-binding | interface-implementation ] *
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:

type Account(number : int, holder : string) = class
    let mutable amount = 0m

    member x.Number = number
    member x.Holder = holder
    member x.Amount = amount
    
    member x.Deposit(value) = amount <- amount + value
    member x.Withdraw(value) = amount <- amount - value
end

The code above defines a class called Account, which has three properties and two methods. Let's take a closer look at the following:

type Account(number : int, holder : string) = class

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:

let bob = new Account(123456, "Bob’s Saving")

Additionally, let's look at the way a member is defined:

member x.Deposit(value) = amount <- amount + value

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:

> let printAccount (x : Account) =
    printfn "x.Number: %i, x.Holder: %s, x.Amount: %M" x.Number x.Holder x.Amount;;

val printAccount : Account -> unit

> let bob = new Account(123456, "Bob’s Savings");;

val bob : Account

> printAccount bob;;
x.Number: 123456, x.Holder: Bobs Savings, x.Amount: 0
val it : unit = ()

> bob.Deposit(100M);;
val it : unit = ()

> printAccount bob;;
x.Number: 123456, x.Holder: Bobs Savings, x.Amount: 100
val it : unit = ()

> bob.Withdraw(29.95M);;
val it : unit = ()

> printAccount bob;;
x.Number: 123456, x.Holder: Bobs Savings, x.Amount: 70.05

Example[edit]

Let's use this class in a real program:

open System

type Account(number : int, holder : string) = class
    let mutable amount = 0m

    member x.Number = number
    member x.Holder = holder
    member x.Amount = amount
    
    member x.Deposit(value) = amount <- amount + value
    member x.Withdraw(value) = amount <- amount - value
end

let homer = new Account(12345, "Homer")
let marge = new Account(67890, "Marge")

let transfer amount (source : Account) (target : Account) =
    source.Withdraw amount
    target.Deposit amount
    
let printAccount (x : Account) =
    printfn "x.Number: %i, x.Holder: %s, x.Amount: %M" x.Number x.Holder x.Amount
    
let main() =
    let printAccounts() =
        [homer; marge] |> Seq.iter printAccount
    
    printfn "\nInializing account"
    homer.Deposit 50M
    marge.Deposit 100M
    printAccounts()
    
    printfn "\nTransferring $30 from Marge to Homer"
    transfer 30M marge homer
    printAccounts()
    
    printfn "\nTransferring $75 from Homer to Marge"
    transfer 75M homer marge
    printAccounts()
        
main()

The program has the following types:

type Account =
  class
    new : number:int * holder:string -> Account
    member Deposit : value:decimal -> unit
    member Withdraw : value:decimal -> unit
    member Amount : decimal
    member Holder : string
    member Number : int
  end
val homer : Account
val marge : Account
val transfer : decimal -> Account -> Account -> unit
val printAccount : Account -> unit

The program outputs the following:

Initializing account
x.Number: 12345, x.Holder: Homer, x.Amount: 50
x.Number: 67890, x.Holder: Marge, x.Amount: 100

Transferring $30 from Marge to Homer
x.Number: 12345, x.Holder: Homer, x.Amount: 80
x.Number: 67890, x.Holder: Marge, x.Amount: 70

Transferring $75 from Homer to Marge
x.Number: 12345, x.Holder: Homer, x.Amount: 5
x.Number: 67890, x.Holder: Marge, x.Amount: 145

Example using the do keyword[edit]

The do keyword is used for post-constructor initialization. For example, let's say we wanted to create an object which represents a stock. We only need to pass in the stock symbol, and initialize the rest of the properties in our constructor:

open System
open System.Net

type Stock(symbol : string) = class
    let url =
        "http://download.finance.yahoo.com/d/quotes.csv?s=" + symbol + "&f=sl1d1t1c1ohgv&e=.csv"

    let mutable _symbol = String.Empty
    let mutable _current = 0.0
    let mutable _open = 0.0
    let mutable _high = 0.0
    let mutable _low = 0.0
    let mutable _volume = 0

    do
	(* We initialize our object in the do block *)

        let webClient = new WebClient()

       	(* Data comes back as a comma-seperated list, so we split it
           on each comma *)
        let data = webClient.DownloadString(url).Split([|','|])

        _symbol <- data.[0]
        _current <- float data.[1]
        _open <- float data.[5]
        _high <- float data.[6]
        _low <- float data.[7]
        _volume <- int data.[8]
    
    member x.Symbol = _symbol
    member x.Current = _current
    member x.Open = _open
    member x.High = _high
    member x.Low = _low
    member x.Volume = _volume
end

let main() =
    let stocks = 
        ["msft"; "noc"; "yhoo"; "gm"]
        |> Seq.map (fun x -> new Stock(x))
        
    stocks |> Seq.iter (fun x -> printfn "Symbol: %s (%F)" x.Symbol x.Current)
    
main()

This program has the following types:

type Stock =
  class
    new : symbol:string -> Stock
    member Current : float
    member High : float
    member Low : float
    member Open : float
    member Symbol : string
    member Volume : int
  end

This program outputs the following (your outputs will vary):

Symbol: "MSFT" (19.130000)
Symbol: "NOC" (43.240000)
Symbol: "YHOO" (12.340000)
Symbol: "GM" (3.660000)
Note: It's possible to have any number of do statements in a class definition, although there's no particular reason why you'd need more than one.

Explicit Class Definition[edit]

Classes written in explicit style follow this format:

type TypeName =
    [ inherit type ]
    [ val-definitions ]
    [ new ( optional-type-arguments arguments ) [ as ident ] =
      { field-initialization }
      [ then constructor-statements ]
    ] *
    [ abstract-binding | member-binding | interface-implementation ] *

Here's a class defined using the explicit syntax:

type Line = class
    val X1 : float
    val Y1 : float
    val X2 : float
    val Y2 : float
    
    new (x1, y1, x2, y2) =
        { X1 = x1; Y1 = y1;
            X2 = x2; Y2 = y2}
            
    member x.Length =
        let sqr x = x * x
        sqrt(sqr(x.X1 - x.X2) + sqr(x.Y1 - x.Y2) )
end

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:

type Line = class
    val X1 : float
    val Y1 : float
    val X2 : float
    val Y2 : float
    
    new (x1, y1, x2, y2) as this =
        { X1 = x1; Y1 = y1;
            X2 = x2; Y2 = y2;}
        then
            printfn "Line constructor: {(%F, %F), (%F, %F)}, Line.Length: %F"
                this.X1 this.Y1 this.X2 this.Y2 this.Length
            
    member x.Length =
        let sqr x = x * x
        sqrt(sqr(x.X1 - x.X2) + sqr(x.Y1 - x.Y2) )
end

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:

> let line = new Line(1.0, 1.0, 4.0, 2.5);;

val line : Line

Line constructor: {(1.000000, 1.000000), (4.000000, 2.500000)}, Line.Length: 3.354102

Example Using Two Constructors[edit]

Since the constructor is defined explicitly, we have the option to provide more than one constructor.

open System
open System.Net

type Car = class
    val used : bool
    val owner : string
    val mutable mileage : int
    
    (* first constructor *)
    new (owner) =
        { used = false;
            owner = owner;
            mileage = 0 }
    
    (* another constructor *)
    new (owner, mileage) =
        { used = true;
            owner = owner;
            mileage = mileage }
end

let main() =
    let printCar (c : Car) =
        printfn "c.used: %b, c.owner: %s, c.mileage: %i" c.used c.owner c.mileage
    
    let stevesNewCar = new Car("Steve")
    let bobsUsedCar = new Car("Bob", 83000)
    let printCars() =
        [stevesNewCar; bobsUsedCar] |> Seq.iter printCar
    
    printfn "\nCars created"
    printCars()
    
    printfn "\nSteve drives all over the state"   
    stevesNewCar.mileage <- stevesNewCar.mileage + 780
    printCars()
    
    printfn "\nBob commits odometer fraud"
    bobsUsedCar.mileage <- 0
    printCars()
    
main()

This program has the following types:

type Car =
  class
    val used: bool
    val owner: string
    val mutable mileage: int
    new : owner:string * mileage:int -> Car
    new : owner:string -> Car
  end

Notice that our val fields are included in the public interface of our class definition.

This program outputs the following:

Cars created
c.used: false, c.owner: Steve, c.mileage: 0
c.used: true, c.owner: Bob, c.mileage: 83000

Steve drives all over the state
c.used: false, c.owner: Steve, c.mileage: 780
c.used: true, c.owner: Bob, c.mileage: 83000

Bob commits odometer fraud
c.used: false, c.owner: Steve, c.mileage: 780
c.used: true, c.owner: Bob, c.mileage: 0

Differences Between Implicit and Explicit Syntaxes[edit]

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 you can use val fields in the implicit syntax, they must have the attribute [<DefaultValue>] and be mutable. It is more convenient to use let bindings in this case. You can add public member accessors 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, you do not need 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[edit]

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[edit]

Instance and Static Members[edit]

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:

type SomeClass(prop : int) = class
    member x.Prop = prop
    static member SomeStaticMethod = "This is a static method"
end

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:

> SomeClass.SomeStaticMethod;; (* invoking static method *)
val it : string = "This is a static method"

> SomeClass.Prop;; (* doesn't make sense, we haven't created an object instance yet *)

  SomeClass.Prop;; (* doesn't make sense, we haven't created an object instance yet *)
  ^^^^^^^^^^^^^^^

stdin(78,1): error FS0191: property 'Prop' is not static.

> let instance = new SomeClass(5);;

val instance : SomeClass

> instance.Prop;; (* now we have an instance, we can call our instance method *)
val it : int = 5

> instance.SomeStaticMethod;; (* can't invoke static method from instance *)

  instance.SomeStaticMethod;; (* can't invoke static method from instance *)
  ^^^^^^^^^^^^^^^^^^^^^^^^^^

stdin(81,1): error FS0191: property 'SomeStaticMethod' is static.

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:

type SomeClass(prop : int) = class
    member x.Prop = prop
    static member SomeStaticMethod = "This is a static method"
    static member Copy (source : SomeClass) = new SomeClass(source.Prop)
end

We can experiment with this method in fsi:

> let instance = new SomeClass(10);;

val instance : SomeClass

> let shallowCopy = instance;; (* copies pointer to another symbol *)

val shallowCopy : SomeClass

> let deepCopy = SomeClass.Copy instance;; (* copies values into a new object *)

val deepCopy : SomeClass

> open System;;

> Object.ReferenceEquals(instance, shallowCopy);;
val it : bool = true

> Object.ReferenceEquals(instance, deepCopy);;
val it : bool = false

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[edit]

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:

    member alias.PropertyName
        with get() = some-value
        and set(value) = some-assignment

Here's a simple example using fsi:

> type IntWrapper() = class
    let mutable num = 0
    
    member x.Num
        with get() = num
        and set(value) = num <- value
end;;

type IntWrapper =
  class
    new : unit -> IntWrapper
    member Num : int
    member Num : int with set
  end

> let wrapper = new IntWrapper();;

val wrapper : IntWrapper

> wrapper.Num;;
val it : int = 0

> wrapper.Num <- 20;;
val it : unit = ()

> wrapper.Num;;
val it : int = 20

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:

type IntWrapper() = class
    let mutable num = 0
    
    member x.Num
        with get() = num
        and set(value) =
            if value > 10 || value < 0 then
                raise (new Exception("Values must be between 0 and 10"))
            else
                num <- value
end

We can use this class in fsi:

> let wrapper = new IntWrapper();;

val wrapper : IntWrapper

> wrapper.Num <- 5;;
val it : unit = ()

> wrapper.Num;;
val it : int = 5

> wrapper.Num <- 20;;
System.Exception: Values must be between 0 and 10
   at FSI_0072.IntWrapper.set_Num(Int32 value)
   at <StartupCode$FSI_0076>.$FSI_0076._main()
stopped due to error

Adding Members to Records and Unions[edit]

Its just as easy to add members to records and union types as well.

Record example:

> type Line =
    { X1 : float; Y1 : float;
        X2 : float; Y2 : float }
    with    
        member x.Length =
            let sqr x = x * x
            sqrt(sqr(x.X1 - x.X2) + sqr(x.Y1 - x.Y2))
        
        member x.ShiftH amount =
            { x with X1 = x.X1 + amount; X2 = x.X2 + amount }
            
        member x.ShiftV amount =
            { x with Y1 = x.Y1 + amount; Y2 = x.Y2 + amount };;

type Line =
  {X1: float;
   Y1: float;
   X2: float;
   Y2: float;}
  with
    member ShiftH : amount:float -> Line
    member ShiftV : amount:float -> Line
    member Length : float
  end

> let line = { X1 = 1.0; Y1 = 2.0; X2 = 5.0; Y2 = 4.5 };;

val line : Line

> line.Length;;
val it : float = 4.716990566

> line.ShiftH 10.0;;
val it : Line = {X1 = 11.0;
                 Y1 = 2.0;
                 X2 = 15.0;
                 Y2 = 4.5;}

> line.ShiftV -5.0;;
val it : Line = {X1 = 1.0;
                 Y1 = -3.0;
                 X2 = 5.0;
                 Y2 = -0.5;}

Union example

> type shape =
    | Circle of float
    | Rectangle of float * float
    | Triangle of float * float
    with
        member x.Area =
            match x with
            | Circle(r) -> Math.PI * r * r
            | Rectangle(b, h) -> b * h
            | Triangle(b, h) -> b * h / 2.0
            
        member x.Scale value =
            match x with
            | Circle(r) -> Circle(r + value)
            | Rectangle(b, h) -> Rectangle(b + value, h + value)
            | Triangle(b, h) -> Triangle(b + value, h + value);;

type shape =
  | Circle of float
  | Rectangle of float * float
  | Triangle of float * float
  with
    member Scale : value:float -> shape
    member Area : float
  end

> let mycircle = Circle(5.0);;

val mycircle : shape

> mycircle.Area;;
val it : float = 78.53981634

> mycircle.Scale(7.0);;
val it : shape = Circle 12.0

Generic classes[edit]

We can also create classes which take generic types:

type 'a GenericWrapper(initialVal : 'a) = class
    let mutable internalVal = initialVal
    
    member x.Value
        with get() = internalVal
        and set(value) = internalVal <- value
end

We can use this class in FSI as follows:

> let intWrapper = new GenericWrapper<_>(5);;

val intWrapper : int GenericWrapper

> intWrapper.Value;;
val it : int = 5

> intWrapper.Value <- 20;;
val it : unit = ()

> intWrapper.Value;;
val it : int = 20

> intWrapper.Value <- 2.0;; (* throws an exception *)

  intWrapper.Value <- 2.0;; (* throws an exception *)
  --------------------^^^^

stdin(156,21): error FS0001: This expression has type
	float
but is here used with type
	int.

> let boolWrapper = new GenericWrapper<_>(true);;

val boolWrapper : bool GenericWrapper

> boolWrapper.Value;;
val it : bool = true

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[edit]

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:

match arg with
| :? type1 -> expr
| :? type2 -> expr

Here's an example which uses type testing:

type Cat() = class
    member x.Meow() = printfn "Meow"
end

type Person(name : string) = class
    member x.Name = name
    member x.SayHello() = printfn "Hi, I'm %s" x.Name
end

type Monkey() = class
    member x.SwingFromTrees() = printfn "swinging from trees"
end

let handlesAnything (o : obj) =
    match o with
    | null -> printfn "<null>"
    | :? Cat as cat -> cat.Meow()
    | :? Person as person -> person.SayHello()
    | _ -> printfn "I don't recognize type '%s'" (o.GetType().Name)

let main() =
    let cat = new Cat()
    let bob = new Person("Bob")
    let bill = new Person("Bill")
    let phrase = "Hello world!"
    let monkey = new Monkey()
    
    handlesAnything cat
    handlesAnything bob
    handlesAnything bill
    handlesAnything phrase
    handlesAnything monkey
    handlesAnything null

main()

This program outputs:

Meow
Hi, I'm Bob
Hi, I'm Bill
I don't recognize type 'String'
I don't recognize type 'Monkey'
<null>
Previous: Operator Overloading Index Next: Inheritance



Inheritance

Previous: Classes Index Next: Interfaces
F# : Inheritance


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

Subclasses[edit]

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:

type Person(name) =
    member x.Name = name        
    member x.Greet() = printfn "Hi, I'm %s" x.Name
    
type Student(name, studentID : int) =
    inherit Person(name)
    
    let mutable _GPA = 0.0
    
    member x.StudentID = studentID
    member x.GPA
        with get() = _GPA
        and set value = _GPA <- value
    
type Worker(name, employer : string) = 
    inherit Person(name)
    
    let mutable _salary = 0.0
    
    member x.Salary
        with get() = _salary
        and set value = _salary <- value
    
    member x.Employer = employer

Our simple class hierarchy looks like this:

System.Object (* All classes descend from  *)
 - Person
   - Student
   - Worker

The Student and Worker subclasses both inherit the Name and Greet methods from the Person base class. This can be demonstrated in fsi:

> let somePerson, someStudent, someWorker =
    new Person("Juliet"), new Student("Monique", 123456), new Worker("Carla", "Awesome Hair Salon");;

val someWorker : Worker
val someStudent : Student
val somePerson : Person

> somePerson.Name, someStudent.Name, someWorker.Name;;
val it : string * string * string = ("Juliet", "Monique", "Carla")

> someStudent.StudentID;;
val it : int = 123456

> someWorker.Employer;;
val it : string = "Awesome Hair Salon"

> someWorker.ToString();; (* ToString method inherited from System.Object *)
val it : string = "FSI_0002+Worker"

.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[edit]

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:

type Person(name) =
    member x.Name = name        
    member x.Greet() = printfn "Hi, I'm %s" x.Name
    
    override x.ToString() = x.Name    (* The ToString() method is inherited from System.Object *)

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:

type Person(name) =
    member x.Name = name        
    
    abstract Greet : unit -> unit
    default x.Greet() = printfn "Hi, I'm %s" x.Name
    
type Quebecois(name) =
    inherit Person(name)
    
    override x.Greet() = printfn "Bonjour, je m'appelle %s, eh." x.Name

Our class Person provides a Greet method which may be overridden in derived classes. Here's an example of these two classes in fsi:

> let terrance, phillip = new Person("Terrance"), new Quebecois("Phillip");;

val terrance : Person
val phillip : Quebecois

> terrance.Greet();;
Hi, I'm Terrance
val it : unit = ()

> phillip.Greet();;
Bonjour, je m'appelle Phillip, eh.

Abstract Classes[edit]

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:

[<AbstractClass>]
type Shape(position : Point) =
    member x.Position = position
    override x.ToString() =
        sprintf "position = {%i, %i}, area = %f" position.X position.Y (x.Area())
    
    abstract member Draw : unit -> unit 
    abstract member Area : unit -> float

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:

type Circle(position : Point, radius : float) =
    inherit Shape(position)
    
    member x.Radius = radius
    override x.Draw() = printfn "(Circle)"
    override x.Area() = Math.PI * radius * radius
    
type Rectangle(position : Point, width : float, height : float) =
    inherit Shape(position)
    
    member x.Width = width
    member x.Height = height
    override x.Draw() = printfn "(Rectangle)"
    override x.Area() = width * height
    
type Square(position : Point, width : float) =
    inherit Shape(position)
    
    member x.Width = width
    member x.ToRectangle() = new Rectangle(position, width, width)
    override x.Draw() = printfn "(Square)"
    override x.Area() = width * width
    
type Triangle(position : Point, sideA : float, sideB : float, sideC : float) =
    inherit Shape(position)
    
    member x.SideA = sideA
    member x.SideB = sideB
    member x.SideC = sideC
    
    override x.Draw() = printfn "(Triangle)"
    override x.Area() =
        (* Heron's formula *)
        let a, b, c = sideA, sideB, sideC
        let s = (a + b + c) / 2.0
        Math.Sqrt(s * (s - a) * (s - b) * (s - c) )

Now we have several different implementations of the Shape class. We can experiment with these in fsi:

> let position = { X = 0; Y = 0 };;

val position : Point

> let circle, rectangle, square, triangle =
    new Circle(position, 5.0),
    new Rectangle(position, 2.0, 7.0),
    new Square(position, 10.0),
    new Triangle(position, 3.0, 4.0, 5.0);;

val triangle : Triangle
val square : Square
val rectangle : Rectangle
val circle : Circle

> circle.ToString();;
val it : string = "Circle, position = {0, 0}, area = 78.539816"

> triangle.ToString();;
val it : string = "Triangle, position = {0, 0}, area = 6.000000"

> square.Width;;
val it : float = 10.0

> square.ToRectangle().ToString();;
val it : string = "Rectangle, position = {0, 0}, area = 100.000000"

> rectangle.Height, rectangle.Width;;
val it : float * float = (7.0, 2.0)

Working With Subclasses[edit]

Up-casting and Down-casting[edit]

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 hiearchy, we call this an up-cast. We use the :> operator to perform upcasts:

> let regularString = "Hello world";;

val regularString : string

> let upcastString = "Hello world" :> obj;;

val upcastString : obj

> regularString.ToString();;
val it : string = "Hello world"

> regularString.Length;;
val it : int = 11

> upcastString.ToString();; (* type obj has a .ToString method *)
val it : string = "Hello world"

> upcastString.Length;; (* however, obj does not have Length method *)

  upcastString.Length;; (* however, obj does not have Length method *)
  -------------^^^^^^^

stdin(24,14): error FS0039: The field, constructor or member 'Length' is not defined.

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:

> let intAsObj = 20 :> obj;;

val intAsObj : obj

> intAsObj, intAsObj.ToString();;
val it : obj * string = (20, "20")

> let intDownCast = intAsObj :?> int;;

val intDownCast : int

> intDownCast, intDownCast.ToString();;
val it : int * string = (20, "20")

> let stringDownCast = intAsObj :?> string;; (* boom! *)

val stringDownCast : string

System.InvalidCastException: Unable to cast object of type 'System.Int32' to type 'System.String'.
   at <StartupCode$FSI_0067>.$FSI_0067._main()
stopped due to error

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 its 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[edit]

open System

type Point = { X : int; Y : int }

[<AbstractClass>]
type Shape() =
    override x.ToString() =
        sprintf "%s, area = %f" (x.GetType().Name) (x.Area())
    
    abstract member Draw : unit -> unit 
    abstract member Area : unit -> float
    
type Circle(radius : float) =
    inherit Shape()
    
    member x.Radius = radius
    override x.Draw() = printfn "(Circle)"
    override x.Area() = Math.PI * radius * radius
    
type Rectangle(width : float, height : float) =
    inherit Shape()
    
    member x.Width = width
    member x.Height = height
    override x.Draw() = printfn "(Rectangle)"
    override x.Area() = width * height
    
type Square(width : float) =
    inherit Shape()
    
    member x.Width = width
    member x.ToRectangle() = new Rectangle(width, width)
    override x.Draw() = printfn "(Square)"
    override x.Area() = width * width
    
type Triangle(sideA : float, sideB : float, sideC : float) =
    inherit Shape()
    
    member x.SideA = sideA
    member x.SideB = sideB
    member x.SideC = sideC
    
    override x.Draw() = printfn "(Triangle)"
    override x.Area() =
        (* Heron's formula *)
        let a, b, c = sideA, sideB, sideC
        let s = (a + b + c) / 2.0
        Math.Sqrt(s * (s - a) * (s - b) * (s - c) )

let shapes =
        [(new Circle(5.0) :> Shape);
            (new Circle(12.0) :> Shape);
            (new Square(10.5) :> Shape);
            (new Triangle(3.0, 4.0, 5.0) :> Shape);
            (new Rectangle(5.0, 2.0) :> Shape)]
        (* Notice we have to cast each object as a Shape *)
            
let main() = 
    shapes
    |> Seq.iter (fun x -> printfn "x.ToString: %s" (x.ToString()) )

main()

This program has the following types:

type Point =
  {X: int;
   Y: int;}

type Shape =
  class
    abstract member Area : unit -> float
    abstract member Draw : unit -> unit
    new : unit -> Shape
    override ToString : unit -> string
  end

type Circle =
  class
    inherit Shape
    new : radius:float -> Circle
    override Area : unit -> float
    override Draw : unit -> unit
    member Radius : float
  end

type Rectangle =
  class
    inherit Shape
    new : width:float * height:float -> Rectangle
    override Area : unit -> float
    override Draw : unit -> unit
    member Height : float
    member Width : float
  end

type Square =
  class
    inherit Shape
    new : width:float -> Square
    override Area : unit -> float
    override Draw : unit -> unit
    member ToRectangle : unit -> Rectangle
    member Width : float
  end

type Triangle =
  class
    inherit Shape
    new : sideA:float * sideB:float * sideC:float -> Triangle
    override Area : unit -> float
    override Draw : unit -> unit
    member SideA : float
    member SideB : float
    member SideC : float
  end

val shapes : Shape list

This program outputs:

x.ToString: Circle, area = 78.539816
x.ToString: Circle, area = 452.389342
x.ToString: Square, area = 110.250000
x.ToString: Triangle, area = 6.000000
x.ToString: Rectangle, area = 10.000000

Public, Private, and Protected Members[edit]

Previous: Classes Index Next: Interfaces



Interfaces

Previous: Inheritance Index Next: Events
F# : 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:

type Monkey(name : string, birthday : DateTime) =
    let mutable _birthday = birthday
    let mutable _lastEaten = DateTime.Now
    let mutable _foodsEaten = [] : string list
    
    member this.Speak() = printfn "Ook ook!"
    member this.Name = name
    member this.Birthday
        with get() = _birthday
        and set(value) = _birthday <- value
        
    member internal this.UpdateFoodsEaten(food) = _foodsEaten <- food :: _foodsEaten
    member internal this.ResetLastEaten() = _lastEaten <- DateTime.Now
    member this.IsHungry = (DateTime.Now - _lastEaten).TotalSeconds >= 5.0
    member this.GetFoodsEaten() = _lastEaten
    member this.Feed(food) =
        this.UpdateFoodsEaten(food)
        this.ResetLastEaten()
        this.Speak()

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:

type Monkey =
  class
    new : name:string * birthday:DateTime -> Monkey
    member Feed : food:string -> unit
    member GetFoodsEaten : unit -> DateTime
    member Speak : unit -> unit
    member Birthday : DateTime
    member IsHungry : bool
    member Name : string
    member Birthday : DateTime with set
  end

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[edit]

According to the F# specification, interfaces are defined with the following syntax:

type type-name = 
   interface
       inherits-decl 
       member-defns 
   end
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:

type ILifeForm = (* .NET convention recommends the prefix 'I' on all interfaces *)
    abstract Name : string
    abstract Speak : unit -> unit
    abstract Eat : unit -> unit

Using Interfaces[edit]

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:

> type ILifeForm =
    abstract Name : string
    abstract Speak : unit -> unit
    abstract Eat : unit -> unit
    
type Dog(name : string, age : int) =
    member this.Age = age

    interface ILifeForm with
        member this.Name = name
        member this.Speak() = printfn "Woof!"
        member this.Eat() = printfn "Yum, doggy biscuits!"
        
type Monkey(weight : float) =
    let mutable _weight = weight
    
    member this.Weight
        with get() = _weight
        and set(value) = _weight <- value
        
    interface ILifeForm with
        member this.Name = "Monkey!!!"
        member this.Speak() = printfn "Ook ook"
        member this.Eat() = printfn "Bananas!"
        
type Ninja() = 
    interface ILifeForm with
        member this.Name = "Ninjas have no name"
        member this.Speak() = printfn "Ninjas are silent, deadly killers"
        member this.Eat() =
            printfn "Ninjas don't eat, they wail on guitars because they're totally sweet";;

type ILifeForm =
  interface
    abstract member Eat : unit -> unit
    abstract member Speak : unit -> unit
    abstract member Name : string
  end
type Dog =
  class
    interface ILifeForm
    new : name:string * age:int -> Dog
    member Age : int
  end
type Monkey =
  class
    interface ILifeForm
    new : weight:float -> Monkey
    member Weight : float
    member Weight : float with set
  end
type Ninja =
  class
    interface ILifeForm
    new : unit -> Ninja
  end

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?[edit]

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 interface, even if those classes don't necessarily descend from one another. For example, using the Dog, Monkey, and Ninja classes defined above, we can write a method to operate on all of them, as well as any other classes which implement the ILifeForm interface.

Implementing Interfaces with Object Expressions[edit]

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:

{ new ty0 [ args-expr ] [ as base-ident ] [ with 
      val-or-member-defns end ]
 
  interface ty1 with [ 
      val-or-member-defns1 
   end ]
 
  

  interface tyn with [ 
      val-or-member-defnsn  
  end ] }

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:

> open System
open System.Collections.Generic

type person = { name : string; age : int }

let people =
    [|{ name = "Larry"; age = 20 };
      { name = "Moe"; age = 30 };
      { name = "Curly"; age = 25 } |]
      
let sortAndPrint msg items (comparer : System.Collections.Generic.IComparer<person>) =
    Array.Sort(items, comparer)
    printf "%s: " msg
    Seq.iter (fun x -> printf "(%s, %i) " x.name x.age) items
    printfn ""

(* sorting by age *)    
sortAndPrint "age" people { new IComparer<person> with member this.Compare(x, y) = x.age.CompareTo(y.age) }

(* sorting by name *)
sortAndPrint "name" people { new IComparer<person> with member this.Compare(x, y) = x.name.CompareTo(y.name) }

(* sorting by name descending *)
sortAndPrint "name desc" people { new IComparer<person> with member this.Compare(x, y) = y.name.CompareTo(x.name) };;

type person =
  { name: string;
   age: int; }
val people : person array
val sortAndPrint : string -> person array -> IComparer<person> -> unit

age: (Larry, 20) (Curly, 25) (Moe, 30) 
name: (Curly, 25) (Larry, 20) (Moe, 30) 
name desc: (Moe, 30) (Larry, 20) (Curly, 25)

Implementing Multiple Interfaces[edit]

Unlike inheritance, its possible to implement multiple interfaces:

open System

type Person(name : string, age : int) = 
    member this.Name = name
    member this.Age = age
    
    (* IComparable is used for ordering instances *)
    interface IComparable<Person> with
        member this.CompareTo(other) =
            (* sorts by name, then age *)
            match this.Name.CompareTo(other.Name) with
            | 0 -> this.Age.CompareTo(other.Age)
            | n -> n
    
    (* Used for comparing this type against other types *)
    interface IEquatable<string> with
        member this.Equals(othername) = this.Name.Equals(othername)

Its just as easy to implement multiple interfaces in object expressions as well.

Interface Hierarchies[edit]

Interfaces can extend other interfaces in a kind of interface hierarchy. For example:

type ILifeForm =
    abstract member location : System.Drawing.Point

type 'a IAnimal =   (* interface with generic type parameter *)
    inherit ILifeForm
    inherit System.IComparable<'a>
    abstract member speak : unit -> unit
    
type IFeline =
    inherit IAnimal<IFeline>
    abstract member purr : unit -> unit

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[edit]

Generalizing a function to many classes[edit]

open System
type ILifeForm =
    abstract Name : string
    abstract Speak : unit -> unit
    abstract Eat : unit -> unit
    
type Dog(name : string, age : int) =
    member this.Age = age

    interface ILifeForm with
        member this.Name = name
        member this.Speak() = printfn "Woof!"
        member this.Eat() = printfn "Yum, doggy biscuits!"
        
type Monkey(weight : float) =
    let mutable _weight = weight
    
    member this.Weight
        with get() = _weight
        and set(value) = _weight <- value
        
    interface ILifeForm with
        member this.Name = "Monkey!!!"
        member this.Speak() = printfn "Ook ook"
        member this.Eat() = printfn "Bananas!"
        
type Ninja() = 
    interface ILifeForm with
        member this.Name = "Ninjas have no name"
        member this.Speak() = printfn "Ninjas are silent, deadly killers"
        member this.Eat() =
            printfn "Ninjas don't eat, they wail on guitars because they're totally sweet"

let lifeforms =
    [(new Dog("Fido", 7) :> ILifeForm);
     (new Monkey(500.0) :> ILifeForm);
     (new Ninja() :> ILifeForm)]

let handleLifeForm (x : ILifeForm) =
    printfn "Handling lifeform '%s'" x.Name
    x.Speak()
    x.Eat()
    printfn ""
    
let main() =
    printfn "Processing...\n"
    lifeforms |> Seq.iter handleLifeForm
    printfn "Done."
    
main()

This program has the following types:

type ILifeForm =
  interface
    abstract member Eat : unit -> unit
    abstract member Speak : unit -> unit
    abstract member Name : string
  end

type Dog =
  class
    interface ILifeForm
    new : name:string * age:int -> Dog
    member Age : int
  end

type Monkey =
  class
    interface ILifeForm
    new : weight:float -> Monkey
    member Weight : float
    member Weight : float with set
  end

type Ninja =
  class
    interface ILifeForm
    new : unit -> Ninja
  end

val lifeforms : ILifeForm list
val handleLifeForm : ILifeForm -> unit
val main : unit -> unit

This program outputs the following:

Processing...

Handling lifeform 'Fido'
Woof!
Yum, doggy biscuits!

Handling lifeform 'Monkey!!!'
Ook ook
Bananas!

Handling lifeform 'Ninjas have no name'
Ninjas are silent, deadly killers
Ninjas don't eat, they wail on guitars because they're totally sweet

Done.

Using interfaces in generic type definitions[edit]

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:

> open System

type tree<'a> when 'a :> IComparable<'a> =
    | Nil
    | Node of 'a * 'a tree * 'a tree

let rec insert (x : #IComparable<'a>) = function
    | Nil -> Node(x, Nil, Nil)
    | Node(y, l, r) as node ->
        if x.CompareTo(y) = 0 then node
        elif x.CompareTo(y) = -1 then Node(y, insert x l, r)
        else Node(y, l, insert x r)
        
let rec contains (x : #IComparable<'a>) = function
    | Nil -> false
    | Node(y, l, r) as node ->
        if x.CompareTo(y) = 0 then true
        elif x.CompareTo(y) = -1 then contains x l
        else contains x r;;

type tree<'a> when 'a :> IComparable<'a>> =
  | Nil
  | Node of 'a * tree<'a> * tree<'a>
val insert : 'a -> tree<'a> -> tree<'a> when 'a :> IComparable<'a>
val contains : #IComparable<'a> -> tree<'a> -> bool when 'a :> IComparable<'a>

> let x =
    let rnd = new Random()
    [ for a in 1 .. 10 -> rnd.Next(1, 100) ]
    |> Seq.fold (fun acc x -> insert x acc) Nil;;

val x : tree<int>

> x;;
val it : tree<int>
= Node
    (25,Node (20,Node (6,Nil,Nil),Nil),
     Node
       (90,
        Node
          (86,Node (65,Node (50,Node (39,Node (32,Nil,Nil),Nil),Nil),Nil),Nil),
        Nil))

> contains 39 x;;
val it : bool = true

> contains 55 x;;
val it : bool = false

Simple dependency injection[edit]

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:

type Processor() =
    (* ... *)
    member this.Process items =
        try
            (* do stuff with items *)
        with
            | err -> (new Emailer()).SendMsg("admin@company.com", "Error! " + err.Message)

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:

type IFailureNotifier =
    abstract Notify : string -> unit

type Processor(notifier : IFailureNotifier) =
    (* ... *)
    member this.Process items =
        try
            // do stuff with items
        with
            | err -> notifier.Notify(err.Message)

(* concrete implementations of IFailureNotifier *)

type EmailNotifier() =
    interface IFailureNotifier with
        member Notify(msg) = (new Emailer()).SendMsg("admin@company.com", "Error! " + msg)
        
type DummyNotifier() =
    interface IFailureNotifier with
        member Notify(msg) = () // swallow message
        
type LogfileNotifier(filename : string) =
    interface IFailureNotifer with  
        member Notify(msg) = System.IO.File.AppendAllText(filename, msg)

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:

> #time;;

--> Timing now on

> type IAddStrategy =
    abstract add : int -> int -> int
    
type DefaultAdder() =
    interface IAddStrategy with
        member this.add x y = x + y
        
type SlowAdder() = 
    interface IAddStrategy with
        member this.add x y =
            let rec loop acc = function
                | 0 -> acc
                | n -> loop (acc + 1) (n - 1)
            loop x y
            
type OffByOneAdder() =
    interface IAddStrategy with
        member this.add x y = x + y - 1
                
type SwappableAdder(adder : IAddStrategy) =
    let mutable _adder = adder
    member this.Adder
        with get() = _adder
        and set(value) = _adder <- value
        
    member this.Add x y = this.Adder.add x y;;

type IAddStrategy =
  interface
    abstract member add : int -> (int -> int)
  end
type DefaultAdder =
  class
    interface IAddStrategy
    new : unit -> DefaultAdder
  end
type SlowAdder =
  class
    interface IAddStrategy
    new : unit -> SlowAdder
  end
type OffByOneAdder =
  class
    interface IAddStrategy
    new : unit -> OffByOneAdder
  end
type SwappableAdder =
  class
    new : adder:IAddStrategy -> SwappableAdder
    member Add : x:int -> (int -> int)
    member Adder : IAddStrategy
    member Adder : IAddStrategy with set
  end

Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0

> let myAdder = new SwappableAdder(new DefaultAdder());;

val myAdder : SwappableAdder

Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0

> myAdder.Add 10 1000000000;;
Real: 00:00:00.001, CPU: 00:00:00.015, GC gen0: 0, gen1: 0, gen2: 0
val it : int = 1000000010

> myAdder.Adder <- new SlowAdder();;
Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : unit = ()

> myAdder.Add 10 1000000000;;
Real: 00:00:01.085, CPU: 00:00:01.078, GC gen0: 0, gen1: 0, gen2: 0
val it : int = 1000000010

> myAdder.Adder <- new OffByOneAdder();;
Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : unit = ()

> myAdder.Add 10 1000000000;;
Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : int = 1000000009
Previous: Inheritance Index Next: Events



Events

Previous: Interfaces Index Next: Modules and Namespaces
F# : 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[edit]

Events are created and used though F#'s Event class. To create an event, use the Event constructor as follows:

type Person(name : string) =
    let mutable _name = name;
    let nameChanged = new Event<string>()
    
    member this.Name
        with get() = _name
        and set(value) = _name <- value

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:

type Person(name : string) =
    let mutable _name = name;
    let nameChanged = new Event<unit>() (* creates event *)
    
    member this.NameChanged = nameChanged.Publish (* exposed event handler *)
    
    member this.Name
        with get() = _name
        and set(value) =
            _name <- value
            nameChanged.Trigger() (* invokes event handler *)

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[edit]

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:

type Person(name : string) =
    let mutable _name = name;
    let nameChanged = new Event<unit>() (* creates event *)
    
    member this.NameChanged = nameChanged.Publish (* exposed event handler *)
    
    member this.Name
        with get() = _name
        and set(value) =
            _name <- value
            nameChanged.Trigger() (* invokes event handler *)
            
let p = new Person("Bob")
p.NameChanged.Add(fun () -> printfn "-- Name changed! New name: %s" p.Name)

printfn "Event handling is easy"
p.Name <- "Joe"

printfn "It handily decouples objects from one another"
p.Name <- "Moe"

p.NameChanged.Add(fun () -> printfn "-- Another handler attached to NameChanged!")

printfn "It's also causes programs behave non-deterministically."
p.Name <- "Bo"

printfn "The function NameChanged is invoked effortlessly."

This program outputs the following:

Event handling is easy
-- Name changed! New name: Joe
It handily decouples objects from one another
-- Name changed! New name: Moe
It's also causes programs behave non-deterministically.
-- Name changed! New name: Bo
-- Another handler attached to NameChanged!
The function NameChanged is invoked effortlessly.
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[edit]

Adding and Removing Event Handlers[edit]

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:

type Person(name : string) =
    let mutable _name = name;
    let nameChanged = new Event<unit>() (* creates event *)
    
    member this.NameChanged = nameChanged.Publish (* exposed event handler *)
    
    member this.Name
        with get() = _name
        and set(value) =
            _name <- value
            nameChanged.Trigger() (* invokes event handler *)

            
let p = new Person("Bob")

let person_NameChanged =
    new Handler<unit>(fun sender eventargs -> printfn "-- Name changed! New name: %s" p.Name)

p.NameChanged.AddHandler(person_NameChanged)

printfn "Event handling is easy"
p.Name <- "Joe"

printfn "It handily decouples objects from one another"
p.Name <- "Moe"

p.NameChanged.RemoveHandler(person_NameChanged)
p.NameChanged.Add(fun () -> printfn "-- Another handler attached to NameChanged!")

printfn "It's also causes programs behave non-deterministically."
p.Name <- "Bo"

printfn "The function NameChanged is invoked effortlessly."

This program outputs the following:

Event handling is easy
-- Name changed! New name: Joe
It handily decouples objects from one another
-- Name changed! New name: Moe
It's also causes programs behave non-deterministically.
-- Another handler attached to NameChanged!
The function NameChanged is invoked effortlessly.

Defining New Delegate Types[edit]

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:

type NameChangingEventArgs(oldName : string, newName : string) =
    inherit System.EventArgs()

    member this.OldName = oldName
    member this.NewName = newName
        
type NameChangingDelegate = delegate of obj * NameChangingEventArgs -> unit

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[edit]

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.

open System.Windows
open System.Windows.Controls
open System.Windows.Input 
open System
[<EntryPoint>] [<STAThread>]              // STAThread is Single-Threading-Apartment which is required by WPF
let main argv = 
    let b = new Button(Content="Button")  // b is a Button with "Button" as content
    let f(sender:obj)(e:RoutedEventArgs) = // (#3) f is a fun going to handle the Button.ClickEvent
                                           //   f signature must be curried, not tuple as govened by Delegate-RoutedEventHandler.
                                           //   that means f(sender:obj,e:RoutedEventArgs) will not work.
        let b = sender:?>Button            // sender will have Button-type.  Convert it to Button into b.
        MessageBox.Show(b.Content:?>string) // Retrieve the content of b which is obj.  
                                            //    Convert it to string and display by <code>Messagebox.Show</code>
            |> ignore                       // ignore the return because f-signature requires: obj->RoutedEventArgs->unit
                                                      
                                                      
    let d = new RoutedEventHandler(f)       // (#2) d will have type-RoutedEventHandler, 
                                            //      RoutedEventHandler is a kind of delegate to handle Button.ClickEvent.  
                                            //      The f must have signature governed by RoutedEventHandler.
    b.AddHandler(Button.ClickEvent,d)       // (#1) attach a RountedEventHandler-d for Button.ClickEvent
    let w = new Window(Visibility=Visibility.Visible,Content=b)  // create a window-w have a Button-b 
                                                                 // which will show the content of b when clicked
    (new Application()).Run(w)      // create new Application() running the Window-w.
  • (#1) To attach a handler to a control for an event: b.AddHandler(Button.ClickEvent,d)
  • (#2) Create a delegate/handler using a function: let d = new RoutedEventHandler(f)
  • (#3) Create a function with specific signature defined by the delegate: let f(sender:obj)(e:RoutedEventArgs) = ....
  • b is the control.
  • AddHandler is attach.
  • Button.ClickEvent is the event.
  • d is delegate/handler. It is a layer to make sure the signature is correct
  • f is the real function/program provided to the delegate.
  • Rule#1: b must have this event Button.ClickEvent: b is type-Button-object. ClickEvent is a static property of type-ButtonBase which is inherited by type-Button. So Button-type will also have this static property ClickEvent.
  • Rule#2: d must be the handler of ClickEvent: ClickEvent is type-RoutedEvent. RoutedEvent's handler is RoutedEventHandler, just adding Handler at end. RoutedEventHandler is a defined delegate in .NET library. To create d, just let d = new RoutedEventHandler(f), where f is function.
  • Rule#3: f must have signature obeying delegate-d's definition: Check .NET library, RoutedEventHandler is a delegate of C#-signature: void RoutedEventHandler(object sender, RoutedEventArgs e). So f must have same signature. Present the signature in F# is (obj * RountedEventHandler) -> unit
  • Passing State To Callbacks[edit]

    Events can pass state to callbacks with minimal effort. Here is a simple program which reads a file in blocks of characters:

    open System
    
    type SuperFileReader() =
        let progressChanged = new Event<int>()
        
        member this.ProgressChanged = progressChanged.Publish
        
        member this.OpenFile (filename : string, charsPerBlock) =
            use sr = new System.IO.StreamReader(filename)
            let streamLength = int64 sr.BaseStream.Length
            let sb = new System.Text.StringBuilder(int streamLength)
            let charBuffer = Array.zeroCreate<char> charsPerBlock
            
            let mutable oldProgress = 0
            let mutable totalCharsRead = 0
            progressChanged.Trigger(0)
            while not sr.EndOfStream do
                (* sr.ReadBlock returns number of characters read from stream *)
                let charsRead = sr.ReadBlock(charBuffer, 0, charBuffer.Length)
                totalCharsRead <- totalCharsRead + charsRead
                
                (* appending chars read from buffer *)
                sb.Append(charBuffer, 0, charsRead) |> ignore
                
                let newProgress = int(decimal totalCharsRead / decimal streamLength * 100m)
                if newProgress > oldProgress then
                    progressChanged.Trigger(newProgress) // passes newProgress as state to callbacks
                    oldProgress <- newProgress
                
            sb.ToString()
            
    let fileReader = new SuperFileReader()
    fileReader.ProgressChanged.Add(fun percent ->
        printfn "%i percent done..." percent)
        
    let x = fileReader.OpenFile(@"C:\Test.txt", 50)
    printfn "%s[...]" x.[0 .. if x.Length <= 100 then x.Length - 1 else 100]
    

    This program has the following types:

    type SuperFileReader =
      class
        new : unit -> SuperFileReader
        member OpenFile : filename:string * charsToRead:int -> string
        member ProgressChanged : IEvent<int>
      end
    val fileReader : SuperFileReader
    val x : string
    

    Since our event has the type IEvent<int>, we can pass int data as state to listening callbacks. This program outputs the following:

    0 percent done...
    4 percent done...
    9 percent done...
    14 percent done...
    19 percent done...
    24 percent done...
    29 percent done...
    34 percent done...
    39 percent done...
    44 percent done...
    49 percent done...
    53 percent done...
    58 percent done...
    63 percent done...
    68 percent done...
    73 percent done...
    78 percent done...
    83 percent done...
    88 percent done...
    93 percent done...
    98 percent done...
    100 percent done...
    In computer programming, event-driven programming or event-based programming is a programming paradig[...]
    

    Retrieving State from Callers[edit]

    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:

    type Person(name : string) =
        let mutable _name = name;
        let nameChanging = new Event<string * bool ref>()
        let nameChanged = new Event<unit>()
        
        member this.NameChanging = nameChanging.Publish
        member this.NameChanged = nameChanged.Publish
        
        member this.Name
            with get() = _name
            and set(value) =
                let cancelChange = ref false
                nameChanging.Trigger(value, cancelChange)
                
                if not !cancelChange then
                    _name <- value
                    nameChanged.Trigger()
                    
    let p = new Person("Bob")
    
    p.NameChanging.Add(fun (name, cancel) ->
        let exboyfriends = ["Steve"; "Mike"; "Jon"; "Seth"]
        if List.exists (fun forbiddenName -> forbiddenName = name) exboyfriends then
            printfn "-- No %s's allowed!" name
            cancel := true
        else
            printfn "-- Name allowed")
        
    p.NameChanged.Add(fun () ->
        printfn "-- Name changed to %s" p.Name)
        
    let tryChangeName newName =
        printfn "Attempting to change name to '%s'" newName
        p.Name <- newName
    
    tryChangeName "Joe"
    tryChangeName "Moe"
    tryChangeName "Jon"
    tryChangeName "Thor"
    

    This program has the following types:

    type Person =
      class
        new : name:string -> Person
        member Name : string
        member NameChanged : IEvent<unit>
        member NameChanging : IEvent<string * bool ref>
        member Name : string with set
      end
    val p : Person
    val tryChangeName : string -> unit
    

    This program outputs the following:

    Attempting to change name to 'Joe'
    -- Name allowed
    -- Name changed to Joe
    Attempting to change name to 'Moe'
    -- Name allowed
    -- Name changed to Moe
    Attempting to change name to 'Jon'
    -- No Jon's allowed!
    Attempting to change name to 'Thor'
    -- Name allowed
    -- Name changed to Thor
    

    If we need to pass a significant amount of state to listeners, then its recommended to wrap the state in an object as follows:

    type NameChangingEventArgs(newName : string) =
        inherit System.EventArgs()
        
        let mutable cancel = false
        member this.NewName = newName
        member this.Cancel
            with get() = cancel
            and set(value) = cancel <- value
    
    type Person(name : string) =
        let mutable _name = name;
        let nameChanging = new Event<NameChangingEventArgs>()
        let nameChanged = new Event<unit>()
        
        member this.NameChanging = nameChanging.Publish
        member this.NameChanged = nameChanged.Publish
        
        member this.Name
            with get() = _name
            and set(value) =
                let eventArgs = new NameChangingEventArgs(value)
                nameChanging.Trigger(eventArgs)
                
                if not eventArgs.Cancel then
                    _name <- value
                    nameChanged.Trigger()
                    
    let p = new Person("Bob")
    
    p.NameChanging.Add(fun e ->
        let exboyfriends = ["Steve"; "Mike"; "Jon"; "Seth"]
        if List.exists (fun forbiddenName -> forbiddenName = e.NewName) exboyfriends then
            printfn "-- No %s's allowed!" e.NewName
            e.Cancel <- true
        else
            printfn "-- Name allowed")
    
    (* ... rest of program ... *)
    

    By convention, custom event parameters should inherit from System.EventArgs, and should have the suffix EventArgs.

    Using the Event Module[edit]

    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 obejct 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:

    p.NameChanging.Add(fun (e : NameChangingEventArgs) ->
        let exboyfriends = ["Steve"; "Mike"; "Jon"; "Seth"]
        if List.exists (fun forbiddenName -> forbiddenName = e.NewName) exboyfriends then
            printfn "-- No %s's allowed!" e.NewName
            e.Cancel <- true)
    

    We can rewrite this in a more functional style as follows:

    p.NameChanging
        |> Event.filter (fun (e : NameChangingEventArgs) ->  
            let exboyfriends = ["Steve"; "Mike"; "Jon"; "Seth"]
            List.exists (fun forbiddenName -> forbiddenName = e.NewName) exboyfriends )
        |> Event.listen (fun e ->
            printfn "-- No %s's allowed!" e.NewName
            e.Cancel <- true)
    
    Previous: Interfaces Index Next: Modules and Namespaces



    Modules and Namespaces

    Previous: Events Index Next: Units of Measure
    F# : Modules and Namespaces


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

    Defining Modules[edit]

    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

    type 'a Stack =
        | EmptyStack
        | StackNode of 'a * 'a Stack
    
    let rec getRange startNum endNum =
        if startNum > endNum then EmptyStack
        else StackNode(startNum, getRange (startNum+1) endNum)
    

    Program.fs

    let x =
        DataStructures.StackNode(1,
            DataStructures.StackNode(2,
                DataStructures.StackNode(3, DataStructures.EmptyStack)))
                
    let y = DataStructures.getRange 5 10
                
    printfn "%A" x
    printfn "%A" y
    

    This program outputs:

    StackNode (1,StackNode (2,StackNode (3,EmptyStack)))
    StackNode
      (5,
       StackNode
         (6,StackNode (7,StackNode (8,StackNode (9,StackNode (10,EmptyStack))))))
    
    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:

    open DataStructures
    
    let x = StackNode(1, StackNode(2, StackNode(3, EmptyStack)))
    let y = getRange 5 10
                
    printfn "%A" x
    printfn "%A" y
    

    Submodules[edit]

    Its very easy to create submodules using the module keyword:

    (* DataStructures.fs *)
    
    type 'a Stack =
        | EmptyStack
        | StackNode of 'a * 'a Stack
    
    module StackOps =
        let rec getRange startNum endNum =
            if startNum > endNum then EmptyStack
            else StackNode(startNum, getRange (startNum+1) endNum)
    

    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:

    (