WikiBooks - FSharp
WikiBooks - FSharp
WikiBooks - FSharp
Preface
1.1
Introduction
Introducing F#
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2
A Brief History of F# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3
Getting Set Up
3.1
Windows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1
Setup Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.2
3.1.3
Misc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1
3.2.2
MonoDevelop add-in . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.3
Basic Concepts
4.1
Major Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1
. . . . . . . . . . . . . . . . . . . . . . . . .
4.1.2
Type Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.3
Pattern Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1
4.2.2
Recursion or Loops? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.3
. . . . . . . . . . . . . . . . . . . . . . .
4.2.4
10
Structure of F# Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
4.2
4.3
5
2.1
3.2
11
5.1
Declaring Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
5.1.1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
Declaring Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
5.2
ii
CONTENTS
5.2.1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
5.2.2
12
5.2.3
12
5.2.4
Nested Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
5.2.5
Generic Functions
13
15
6.0.7
15
6.0.8
. . . . . . . . . . . . . . . . . . . . . . . . . .
16
6.0.9
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
18
7.1
Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
7.1.1
Factorial in F# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
7.1.2
18
Tail Recursion
7.2.1
7.3
7.4
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
. . . . . . . . . . . . . . . . . . . . . . . . . . .
19
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
19
Additional Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
Exercises
7.3.1
15
Recursion
7.2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
8.0.1
21
8.0.2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
8.0.3
Anonymous Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
8.0.4
23
Option Types
24
9.1
24
9.2
24
9.3
24
26
26
27
11 Lists
29
29
29
29
29
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
CONTENTS
iii
30
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
31
11.3.2 List.choose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
32
32
11.4 Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
33
33
33
33
12 Sequences
35
35
35
36
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
13.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13.1.1 The Set Module
38
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
13.1.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
13.2 Maps
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
39
13.2.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14 Discriminated Unions
40
41
41
41
41
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
42
14.6 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
42
43
43
15 Mutable Data
44
44
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
44
iv
CONTENTS
15.2.1 Aliasing Ref Cells
15.3 Encapsulating Mutable State
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
16 Control Flow
46
46
46
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
47
47
47
17 Arrays
48
48
48
48
48
48
49
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
50
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
51
18 Mutable Collections
18.1 List<'T> Class
52
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
52
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
53
54
54
55
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
56
19.1.1 With F#
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
56
19.2.2 Streams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
20 Exception Handling
20.1 Try/With
57
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
57
CONTENTS
20.3 Try/Finally
v
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
58
58
59
21 Operator Overloading
21.1 Using Operators
60
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
60
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
62
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
62
62
63
64
64
65
65
66
. . . . . . . . . . . . . . . . . . . . . . . . . .
66
66
67
23 Inheritance
68
23.1 Subclasses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23.1.1 Overriding Methods
68
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
69
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
70
24 Interfaces
71
71
71
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
72
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
72
24.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73
. . . . . . . . . . . . . . . . . . . . . . . . . . .
73
73
vi
CONTENTS
24.3.3 Simple dependency injection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25 Events
73
75
75
75
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
76
76
76
76
77
77
78
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
80
80
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
80
81
81
82
82
83
27 Units of Measure
84
84
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
84
84
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
85
85
85
27.5 F# PowerPack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
86
86
28 Caching
87
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87
88
28.2 Memoization
29 Active Patterns
29.1 Dening Active Patterns
89
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89
89
90
90
91
CONTENTS
vii
92
30.1 Stacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
30.2 Queues
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
93
93
93
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
94
94
95
30.3.3 Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
96
97
97
31 Reection
31.1 Inspecting Types
99
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99
99
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
102
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
105
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
109
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
viii
CONTENTS
34.3 Two-way Communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
34.3.1 Encapsulating MailboxProcessors with Objects
34.4 MailboxProcessor Examples
. . . . . . . . . . . . . . . . . . . . . . . 110
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
111
Chapter 1
Preface
1.1 How This Book Came To Be
2
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 rst-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, denitive F# tutorial on Internet.
CHAPTER 1. PREFACE
Chapter 2
Introduction
2.1 Introducing F#
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 ecient machine code. MLs relative success
spawned an entire family of ML-derived languages, including Standard ML, Caml, its most famous dialect
called OCaml which unies functional programming with
object-oriented and imperative styles, and Haskell.
F# was developed in 2005 at Microsoft Research.
many ways, F# is essentially a .Net implementation
OCaml, combining the power and expressive syntax
functional programming with the tens of thousands
classes which make up the .NET class library.
In many ways, its 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 welldeveloped object model which allows programmers to
mix object-oriented and functional programming styles
seamlessly.
In
of
of
of
4
bines many of the best features of functional and objectoriented programming styles into a uniquely productive
language.
CHAPTER 2. INTRODUCTION
Chapter 3
Getting Set Up
3.1 Windows
3.1.1
Setup Procedure
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.
3.2.1
3.2.2
MonoDevelop add-in
The F# Software Foundation also give instructions for installing the Monodevelop support for F#. This comes
with project build system, code completion, and syntax
highlighting support.
3.2.3
The F# Software Foundation also give instructions for using F# with other editors. An emacs mode for F# is also
available on Github.
Chapter 4
Basic Concepts
Lists, Maps, and Sets, which represent immutable
versions of a stack, hashtable, and set data structures, respectively.
Fundamental Data Types and Type plained in later chapters of this book.
System
F# is a statically typed language, meaning that the com-
let a = 1 in (printfn "%i a; (let a = a + 1 in printfn "%i items.Length - 1 do let item = items.[i] in proc item
a); printfn "%i a)
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 enumera121
tion, functional programmers would use a dierent data
Once symbols are bound to values, they cannot be as- structure, a singly linked list. Here is an example of itersigned a new value. The only way to change the meaning ating over this data structure with pattern matching:
of a bound symbol is to shadow it by introducing a new
binding for this symbol (for example, with a let construct, let rec processItems = function | [] -> () // empty list: end
as in let a = a + 1), but this shadowing will only have a recursion | head :: tail -> // split list in rst item (head)
localized eect: it will only aect the newly introduced and rest (tail) proc head; processItems tail // recursively
scope. F# uses so-called 'lexical scoping', which simply enumerate list
means that one can identify the scope of a binding by simply looking at the code. Thus the scope of the let a = a + It is important to note that because the recursive call to
1 binding in (let a = a + 1 in ..) is limited by the paren- processItems appears as the last expression in the functheses. With lexical scoping, there is no way for a piece tion, this is an example of so-called tail recursion. The
of code to change the value of a bound symbol outside of F# compiler recognizes this pattern and compiles proitself, such as in the code that has called it.
cessItems to a loop. The processItems function therefore
Immutability is a great concept. Immutability allows pro- runs in constant space and does not cause stack overows.
prints out
4.2.2
Recursion or Loops?
10
Functional programming aims to build simple, composable abstractions. Since traditional OO can only make an
objects 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 at 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 impleMost F# code les begin with a number of open statementation across modules.
ments used to import namespaces, allowing programmers to reference classes in namespaces without having
to write fully qualied type declarations. This keyword
4.2.4 Functions as First-Order Types
is functionally equivalent to the using directive in C# and
F# is a functional programming language, meaning that Imports directive in VB.Net. For example, the Console
functions are rst-order data types: they can be declared class is found under the System namespace; without imand used in exactly the same way that any other variable porting the namespace, a programmer would need to access the Console class through its fully qualied name,
can be used.
System.Console.
In an imperative language like Visual Basic there is a funThe body of the F# le usually contains functions to imdamental dierence between variables and functions.
plement the business logic in an application.
Dim myVal as Integer Dim myParam as Integer myParam = 2 Public Function MyFunc(Dim param as Finally, many F# application exhibit this pattern:
Integer) MyFunc = (param * 2) + 7 End Function myVal let main() = (* ... This is the main loop. ... *) main()
= MyFunc(myParam)
(* This is a top-level statement because its not nested in
any other functions. This calls into the main method to
Notice the dierence in syntax between dening and run the main loop. *)
evaluating a function and dening and assigning a variable. In the preceding Visual Basic code we could per- In general, there is no explicit entry point in an F# appliform a number of dierent actions with a variable we cation. Rather, when an F# application is compiled, the
can:
last le passed to the compiler is assumed to be the entry
point, and the compiler executes all top-level statements
create a token (the variable name) and associate it in the le from top to bottom. While its possible to have
any number of top-level statements in the entry point of
with a type
a F# program, well-written F# only has a single top-level
assign it a value
statement which calls the main loop of the application.
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
Chapter 5
bind a variable to a value, its 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.
let add x y = x + y
This declares a variable called x and assigns it the value
5. Naturally, we can write the following:
add is the name of the function, and it takes two parameters, x and y. Notice that each distinct argument in the
let x = 5 let y = 10 let z = x + y
functional declaration is separated by a space. Similarly,
when you execute this function, successive arguments are
z now holds the value 15.
separated by a space:
A complete program looks like this:
let z = add 5 10
let x = 5 let y = 10 let z = x + y printfn x: %i x printfn
y: %i y printfn z: %i z
This assigns z the return value of this function, which in
this case happens to be 15.
The statement printfn prints text out to the console winNaturally, we can pass the return value of functions didow. As you might have guessed, the code above prints
rectly into other functions, for example:
out the values of x, y, and z. This program results in the
let add x y = x + y let sub x y = x - y let printThreefollowing:
Numbers num1 num2 num3 = printfn num1: %i num1
x: 5 y: 10 z: 15
printfn num2: %i num2 printfn num3: %i num3
printThreeNumbers 5 (add 10 7) (sub 20 8)
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.
5.1.1
12
5.2.1
let sign num = if num > 0 then positive elif num < 0 int -> string -> oat
then negative else 0
takes an int and a string input, returns a oat
If you run this code in fsi, you get the following error
message:
This description is a good introductory way to understand
> let sign num = if num > 0 then positive elif num < 0 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
then negative else 0;; else 0;; ---------^
stdin(7,10): error FS0001: This expression was expected who feel comfortable with this concept as described, the
actual way in which F# is implementing these calls is via
to have type string but here has type int
currying the function.
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.
5.2.3 Partial Function Application
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
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:
This function takes no parameters and returns (). You oat -> oat -> oat
can think of unit as the equivalent to void in C-style lansince a function of this type is implicitly curried by F#,
guages.
there is a two step process to resolve the function when
called with two arguments
5.2.2
1. a function is called with the rst argument that returns a function that takes a oat and returns a
oat. 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 oat
13
let addTwoNumbers x y = x + y
// curried version pseudo-code f: int -> (int -> (int -> int))
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
5.2.4 Nested Functions
int and returns an int. In other words, add5toNumber
partially applies the addTwoNumbers function.
F# allows programmers to nest functions inside other
> let z = add5ToNumber 6;; val z : int = 11
functions. Nested functions have a number of applications, such as hiding the complexity of inner loops:
This partial application of a function with multiple argument exemplies 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 The outer function sumOfDivisors makes a call to the intype signature of holdOn is a function (int -> int) since ner function loop. Programmers can have an arbitrary
it is the partial application of addTwoNumbers
level of nested functions as need requires.
> let holdOn = addTwoNumbers 7;; val holdOn : (int ->
int) > let okDone = holdOn 8;; val okDone : int = 15
So while the Arrow Notation is a good shorthand for understanding the type signature of a function, it does so
at the price of oversimplication, for a function with the
type signature of
14
Chapter 6
6.0.6
15
16
6.0.8
Binding Variables
Matching
with
Pattern matching is not a fancy syntax for a switch struc- Example With Incomplete Pattern Matches
ture found in other languages, because it does not necessarily match against values, it matches against the shape > let getCityFromZipcode zip = match zip with | 68528
-> Lincoln, Nebraska | 90210 -> Beverly Hills,
of data.
California";; match zip with ----------^^^^ stdin(12,11):
F# can automatically bind values to identiers if they warning FS0025: Incomplete pattern matches on this
match certain patterns. This can be especially useful expression. For example, the value '0' will not be
when using the alternative pattern matching syntax, for matched val getCityFromZipcode : int -> string
example:
let rec factorial = function | 0 | 1 -> 1 | n -> n * factorial While this code is valid, F# informs the programmer of
(n - 1)
the possible error. F# warns us for a reason:
> getCityFromZipcode 68528;; val it : string = LinThe variable n is a pattern. If the factorial function is coln, Nebraska > getCityFromZipcode 32566;; Micalled with a 5, the 0 and 1 patterns will fail, but the last crosoft.FSharp.Core.MatchFailureException: Exception
pattern will match and bind the value to the identier n. of type 'Microsoft.FSharp.Core.MatchFailureException'
was thrown. at FSI_0018.getCityFromZipcode(Int32
Note to beginners: variable binding in patzip) at <StartupCode$FSI_0020>.$FSI_0020._main()
tern matching often looks strange to beginstopped due to error
ners, however it is probably the most powerful
and useful feature of F#. Variable binding is
F# will throw an exception if a pattern isn't matched. The
used to decompose data structures into compoobvious solution to this problem is to write patterns which
nent parts and allow programmers to examine
are complete.
each part; however, data structure decomposiOn occasions when a function genuinely has a limited
tion is too advanced for most F# beginners, and
range of inputs, its best to adopt this style:
the concept is dicult to express using simple
types like ints and strings. This book will dislet apartmentPrices numberOfRooms = match numcuss how to decompose data structures using
berOfRooms with | 1 -> 500.0 | 2 -> 650.0 | 3 -> 700.0
pattern matching in later chapters.
| _ -> failwith Only 1-, 2-, and 3- bedroom apartments
available at this complex
Using Guards within Patterns
This function now matches any possible input, and will
Occasionally, its not enough to match an input against a fail with an explanatory informative error message on inparticular value; we can add lters, or guards, to patterns valid inputs (this makes sense, because who would rent a
using the when keyword:
negative 42 bedroom apartment?).
let sign = function | 0 -> 0 | x when x < 0 -> 1 | x when Example With Unmatched Patterns
x > 0 -> 1
> let greeting name = match name with | Steve ->
Hello!" | Carlos -> Hola!" | _ -> DOES NOT
The function above returns the sign of a number: 1 for COMPUTE!" | Pierre -> Bonjour";; | Pierre
negative numbers, +1 for positive numbers, and '0' for 0: -> Bonjour";; ------^^^^^^^^^ stdin(22,7): warning
> sign 55;; val it : int = 1 > sign 108;; val it : int = 1 FS0026: This rule will never be matched. val greeting :
string -> string
> sign 0;; val it : int = 0
Variable binding is useful because its often required to Since the pattern _ matches anything, and since F# evaluates patterns from top to bottom, its not possible for the
implement guards.
code to ever reach the pattern Pierre.
6.0.9
17
The rst two lines return the correct output, because
we've dened 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 specic 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 programs life cycle, but may not
show its eects 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.
Chapter 7
Recursion
A recursive function is a function which calls itself. Interestingly, in contrast to many other languages, functions
in F# are not recursive by default. A programmer needs
to explicitly mark a function as recursive using the rec
keyword:
let rec someFunction = ...
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:
{
x
if y = 0
gcd(x, y) =
gcd(y, remainder(x, y)) if x >= y and y > 0
7.1 Examples
7.1.1
Factorial in F#
18
7.3. EXERCISES
19
to drop the current stack frame before executing the target > let rec slowMultiply a b = if b > 1 then a + slowMultiply
function. As a result, tail-recursive functions can recurse a (b - 1) else a;; val slowMultiply : int -> int -> int >
indenitely without consuming stack space.
slowMultiply 3 9;; val it : int = 27 > slowMultiply 2
14;; val it : int = 28 > slowMultiply 1 100000;; Process
Heres non-tail recursive function:
is terminated due to StackOverowException. Session
> let rec count n = if n = 1000000 then printfn done termination detected. Press Enter to restart.
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 Its possible to re-write most recursive functions into their
unit) after the recursive call is invoked. *);; val count tail-recursive forms using an accumulating parameter:
: int -> unit > count 0;; n: 0 n: 1000 n: 2000 n: 3000 > let slowMultiply a b = let rec loop acc counter = if
... n: 58000 n: 59000 Session termination detected. counter > 1 then loop (acc + a) (counter - 1) (* tail
Press Enter to restart. Process is terminated due to recursive *) else acc loop a b;; val slowMultiply : int
StackOverowException.
-> int -> int > slowMultiply 3 9;; val it : int = 27 >
slowMultiply 2 14;; val it : int = 28 > slowMultiply 1
Lets see what happens if we make the function properly 100000;; val it : int = 100000
tail-recursive:
> let rec count n = if n = 1000000 then printfn done The accumulator parameter in the inner loop holds the
state of our function throughout each recursive iteration.
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
7.3 Exercises
If there was no check for n = 1000000, the function would Solutions.
run indenitely. Its important to ensure that all recursive
function have a base case to ensure they terminate eventually.
7.2.1
20
CHAPTER 7. RECURSION
Chapter 8
xp
val map : 'a -> ('a -> 'b) -> 'b val square : int -> int val
cubeAndConvertToString : int -> string val answer :
bool -> string val rst : int val second : string val third :
string
22
the signature (int -> int); this means the placeholders 'a The advantage of doing composition using the >> operand 'b in the map function both become ints.
ator is that the functions in the composition are listed in
The second function passes a datatype int and a function the order in which they are called.
(int -> string), and map predictably returns a string.
In algebra, the composition function is dened as compose(f, g, x) = f(g(x)), denoted f o g. In F#, the compo- Lets also say we had a complicated function which
sition function is dened as follows:
squared a number, added ve to it, and converted it to
a string? Normally, we'd write this:
let inline (<<) f g x = f (g x)
let complexFunction x = toString (add 5 (square x))
Which has the somewhat cumbersome signature val << :
('b -> 'c) -> ('a -> 'b) -> 'a -> 'c.
We can improve the readability of this function somewhat
using the pipeline operator:
If I had two functions:
let complexFunction x = x |> square |> add 5 |> toString
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
23
)) printfn b 30: %i (duration ( fun() -> b 30 )) main() the rest of its arguments, with all occurrences of x being
replaced by the argument 5.
The duration function has the type val duration : (unit -> Currying is built on the principle that each argument ac'a) -> 'a. This program prints:
tually returns a separate function, which is why calling a
function with only part of its parameters returns another
Elapsed Time: 1 b 5: 5 Elapsed Time: 5 b 30: 832040
function. The familiar F# syntax that we've seen so far,
let add x y = x + y, is actually a kind of syntatic sugar for
Note: the actual duration to execute these functhe explicit currying style shown above.
tions will vary from machine to machine.
8.0.4
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
Chapter 9
Option Types
An option type can hold two possible values: Some(x) the CLR System.Nullable<T> representation in IL due
or None. Option types are frequently used to represent to dierences in semantics.
optional values in calculations, or to indicate whether a
particular computation has succeeded or failed.
9.2 Pattern
Types
Matching
Option
> 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 ne, but div 10 0 throws a division val get : 'a option -> 'a
by zero exception.
Returns the value of a Some option.
Using option types, we can return Some(value) on a successful calculation, or None if the calculation fails:
val isNone : 'a option -> bool
> let safediv x y = match y with | 0 -> None | _ ->
Some(x/y);; val safediv : int -> int -> int option > safediv
Returns true for a None option, false otherwise.
10 5;; val it : int option = Some 2 > safediv 10 0;; val it :
int option = None
val isSome : 'a option -> bool
Notice an important dierence between our div and safediv functions:
val div : int -> int -> int val safediv : int -> int -> int option
val map : ('a -> 'b) -> 'a option -> 'b option
div returns an int, while safediv returns an int option.
Since our safediv function returns a dierent data type,
it informs clients of our function that the application has
entered an invalid state.
Given None, returns None. Given Some(x), returns Some(f x), where f is the given mapping
function.
25
Chapter 10
Dening Tuples
A tuple is dened 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 Pattern Matching Tuples
hoc data structures which group together related values.
Pattern matching on tuples is easy, because the same synlet average (a, b) = (a + b) / 2.0
tax used to declare tuple types is also used to match tuples.
This function has the type oat * oat -> oat, it takes a
Example 1
oat * oat tuple and returns another oat.
> let average (a, b) = let sum = a + b sum / 2.0;; val Lets say that we have a function greeting that prints out a
average : oat * oat -> oat > average (10.0, 20.0);; val custom greeting based on the specied name and/or language.
it : oat = 15.0
let greeting (name, language) = match (name, lanNotice that a tuple is considered a single argument. As a guage) with | (Steve, _) -> Howdy, Steve | (name,
English) -> Hello, " + name | (name, _) when
result, tuples can be used to return multiple values:
language.StartsWith(Span) -> Hola, " + name | (_,
Example 1 - a function which multiplies a 3-tuple by a French) -> Bonjour!" | _ -> DOES NOT COMscalar value to return another 3-tuple.
PUTE
> let scalarMultiply (s : oat) (a, b, c) = (a * s, b * s, c
* s);; val scalarMultiply : oat -> oat * oat * oat -> This function has type string * string -> string, meaning
oat * oat * oat > scalarMultiply 5.0 (6.0, 10.0, 20.0);;
that it takes a 2-tuple and returns a string. We can test
val it : oat * oat * oat = (30.0, 50.0, 100.0)
this function in fsi:
> greeting (Steve, English);; val it : string =
Example 2 - a function which reverses the input of what- Howdy, Steve > greeting (Pierre, French);; val it
ever is passed into the function.
: string = Bonjour!" > greeting (Maria, Spanish);;
> let swap (a, b) = (b, a);; val swap : 'a * 'b -> 'b * 'a > val it : string = Hola, Maria > greeting (Rocko,
swap (Web, 2.0);; val it : oat * string = (2.0, Web) Esperanto);; val it : string = DOES NOT COMPUTE
> swap (20, 30);; val it : int * int = (30, 20)
Example 2
Example 3 - a function which divides two numbers and We can conveniently match against the shape of a tuple
returns the remainder simultaneously.
using the alternative pattern matching syntax:
> let divrem x y = match y with | 0 -> None | _ -> Some(x > let getLocation = function | (0, 0) -> origin | (0, y)
/ y, x % y);; val divrem : int -> int -> (int * int) option -> on the y-axis at y=" + y.ToString() | (x, 0) -> on
> divrem 100 20;; (* 100 / 20 = 5 remainder 0 *) val it the x-axis at x=" + x.ToString() | (x, y) -> at x=" +
: (int * int) option = Some (5, 0) > divrem 6 4;; (* 6 / x.ToString() + ", y=" + y.ToString() ;; val getLocation :
4 = 1 remainder 2 *) val it : (int * int) option = Some int * int -> string > getLocation (0, 0);; val it : string =
(1, 2) > divrem 7 0;; (* 7 / 0 throws a DivisionByZero origin > getLocation (0, 1);; val it : string = on the
exception *) val it : (int * int) option = None
y-axis at y=1 > getLocation (5, 10);; val it : string
= at x=5, y=10 > getLocation (7, 0);; val it : string =
Every tuple has a property called arity, which is the num- on the x-axis at x=7
26
27
> System.Int32.TryParse(3);; val it : bool * int = (true,
3) > System.Math.DivRem(10, 7);; val it : int * int = (1,
3)
fst and snd
F# has two built-in functions, fst and snd, which return
the rst and second items in a 2-tuple. These functions 10.0.2 Dening Records
are dened as follows:
A record is similar to a tuple, except it contains named
let fst (a, b) = a let snd (a, b) = b
elds. A record is dened using the syntax:
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 Heres a simple record:
(hello, world);; val it : string = world > fst (Web, type website = { Title : string; Url : string }
2.0);; val it : string = Web > snd (50, 100);; val it : int
= 100
Unlike a tuple, a record is explicitly dened as its own
type using the type keyword, and record elds are dened
as a semicolon-separated list. (In many ways, a record can
be thought of as a simple class.)
Assigning Multiple Variables Simultaneously
A website record is created by specifying the records
Tuples can be used to assign multiple values simultane- elds as follows:
ously. The syntax for doing so is:
> let homepage = { Title = Google"; Url =
let val1, val2, ... valN = (expr1, expr2, ... exprN)
"http://www.google.com" };; val homepage : website
In other words, you assign a comma-separated list of N
values to an N-tuple. Heres an example in FSI:
28
The method setX has the type coords -> oat -> coords. (0.000000, 0.000000) is in quadrant Origin (1.000000,
The with keyword creates a clone of item and set its X 1.000000) is in quadrant I (1.000000, 1.000000) is in
property to newX.
quadrant II (1.000000, 1.000000) is in quadrant III
> let start = { X = 1.0; Y = 2.0 };; val start : coords > let (1.000000, 1.000000) is in quadrant IV
nish = setX start 15.5;; val nish : coords > start;; val it
: coords = {X = 1.0; Y = 2.0;} > nish;; 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.
Heres 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;}
Chapter 11
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.
11.1.2
The :: operator prepends items to a list, returning a new Ranges have the constructs [start .. end] and [start .. step
list. It is a right-associative operator with the following .. end]. For example:
type:
> [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' ..
val inline (::) : 'T -> 'T list -> 'T list
's];; val it : char list = ['a'; 'b'; 'c'; 'd'; 'e'; 'f'; 'g'; 'h'; 'i'; 'j';
29
30
'k'; 'l'; 'm'; 'n'; 'o'; 'p'; 'q'; 'r'; 's]
Generators have the construct [for x in collection do ... You use the same syntax to match against lists that you
yield expr], and they are much more exible than ranges. use to create lists. Heres a simple program:
For example:
let rec sum total = function | [] -> total | hd :: tl -> sum
> [ for a in 1 .. 10 do yield (a * a) ];; val it : int list = [1; (hd + total) tl let main() = let numbers = [ 1 .. 5 ] let
4; 9; 16; 25; 36; 49; 64; 81; 100] > [ for a in 1 .. 3 do for sumOfNumbers = sum 0 numbers printfn sumOfNumb in 3 .. 7 do yield (a, b) ];; val it : (int * int) list = [(1, bers: %i sumOfNumbers main()
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 The sum method has the type val sum : int -> int list 1 .. 100 do if a % 3 = 0 && a % 5 = 0 then yield a];; val > int. It recursively enumerates through the list, adding
it : int list = [15; 30; 45; 60; 75; 90]
each item in the list to the value total. Step by step, the
function works as follows:
Its 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']; Frequently, we use recursion and pattern matching to gen['c'; 'c'; 'c']; ['d'; 'd'; 'd']; ['e'; 'e'; 'e']; ['f'; 'f'; 'f']]
erate new lists from existing lists. A simple example is
reversing a list:
Note that the yield keyword pushes a single value into let reverse l = let rec loop acc = function | [] -> acc | hd
a list. Another keyword, yield!, pushes a collection of :: tl -> loop (hd :: acc) tl loop [] l
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]
Its 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"]
The samples above use the yield keyword explicitly, how- This simple function works because items are always
ever F# provides a slightly dierent arrow-based syntax prepended to the accumulating parameter acc, resulting
in series of recursive calls as follows:
for list comprehensions:
> [ for a in 1 .. 5 -> a * a];; val it : int list = [1; 4; 9; 16; List.rev is a built-in function for reversing a list:
25] > [ for a in 1 .. 5 do for b in 1 .. 3 -> a, b];; val it : > List.rev [1 .. 5];; val it : int list = [5; 4; 3; 2; 1]
(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]
11.2.2 Filter A List
-> and ->> are equivalent to the yield and yield! operators respectively. While its 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!.
31
11.2.3
Mapping Lists
let rst = [1; 2; 3;] let second = [4; 5; 6;] let combined1
= rst @ second (* returns [1; 2; 3; 4; 5; 6] *) let
We can write a function which maps a list to another list: combined2 = List.append rst second (* returns [1; 2; 3;
open System let rec map converter = function | [] -> [] 4; 5; 6] *)
| hd :: tl -> converter hd::map converter tl let main()
= let mappedNumbers = [1 .. 10] |> map ( fun x -> Since lists are immutable, appending two lists together
(x * x).ToString() ) printfn mappedNumbers: %A requires copying all of the elements of the lists to create
mappedNumbers main()
a brand new list. However, since lists are immutable, its
only necessary to copy the elements of the rst list; the
map has the type val map : ('a -> 'b) -> 'a list -> 'b list. second list does not need to be copied. Represented in
memory, appending two lists can be diagrammed as folThe program above outputs:
lows:
mappedNumbers: ["1"; 4"; 9"; 16"; 25"; 36"; 49";
We start with the following:
64"; 81"; 100"]
rst = 1 :: 2 :: 3 :: [] second = 4 :: 5 :: 6 :: []
A tail-recursive map function can be written as:
let map converter l = let rec loop acc = function | [] -> Appending the two lists, rst @ second, results in the folacc | hd :: tl -> loop (converter hd :: acc) tl List.rev (loop lowing:
[] l)
rst = 1 :: 2 :: 3 :: [] \______ ______/ \/ combined = 1 ::
2 :: 3 :: second (copied)
Like the example above, we use the accumulating-param- In other words, F# prepends a copy of rst to second to
and-reverse pattern to make the function tail recursive.
create the combined list. This hypothesis can be veried
using the following in fsi:
> let rst = [1; 2; 3;] let second = [4; 5; 6;] let combined
= rst @ second let secondHalf = List.tail (List.tail
(List.tail combined));; val rst : int list val second : int
Although a reverse, lter, and map method were imple- list val combined : int list val secondHalf : int list >
mented above, its much more convenient to use F#'s built- System.Object.ReferenceEquals(second, secondHalf);;
val it : bool = true
in functions:
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
> [1 .. 10] |> List.lter (fun x -> x % 2 = 0);; val it : int complexity of O(list1.Length).
32
11.3.2
List.choose
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))))
choose lters for items that return Some and maps them
to another value in a single step.
11.3.3
In F#, mathematical operators are no dierent from functions. As shown above, we can actually pass the addition
operator to the fold function, because the + operator has
the denition int -> int -> int.
Computing a factorial
let factorial n = [ 1I .. n ] |> List.fold ( * ) 1I let x =
factorial 13I (* returns 6227020800I *)
Computing population standard deviation
The value of output is 3840. This table demonstrates how List.nd and List.trynd have the following types:
output was calculated:
val nd : ('T -> bool) -> 'T list -> 'T val tryFind : ('T ->
List.fold passes an accumulator with an item from the list bool) -> 'T list -> 'T option
into a function. The output of the function is passed as
the accumulator for the next item.
The nd and tryFind methods return the rst item in the
As shown above, the fold function processes the list from
the rst 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
list for which the search function returns true. They only
dier as follows: if no items are found that meet the
search function, nd throws a KeyNotFoundException,
while trynd returns None.
11.4. EXERCISES
33
11.4 Exercises
Solutions.
11.4.1
unpair [(1, 2); (3, 4); (5, 6)] = [1; 2; 3; 4; 5; 6] unpair Note that the algorithm works recursively. It will rst split
[(one, two); (three, four)] = ["one"; two"; the list. The next step is to sort both parts. To do that, they
three"; four"]
will be split again and so on. This will basically continue
until the original list is scrambled up completely. Then
recursion will do its magic and assemble the list from the
bottom. This might seem confusing at rst, but you will
11.4.2 Expand a List
learn a lot about how recursion works, when theres more
than one function involved
Write a function with the following type denition:
The split function
val expand : 'a list -> 'a list list
val split : 'a list -> 'a list * 'a list
The expand function should expand a list as follows:
expand [ 1 .. 5 ] = [ [1; 2; 3; 4; 5]; [2; 3; 4; 5]; [3; 4; The split function will work like this.
34
split [2; 8; 5; 3] = ( [5; 2], [8; 3] )
The splits 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 splits
together into a sorted list assuming that both splits 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 splits are already sorted. It will make its implementation a lot easier. Assuming both splits are sorted,
we can just look at the rst element of both splits 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 its 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 thats 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
Chapter 12
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 innite data structures.
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
12.1 Dening Sequences
one trillion elements. By comparison, it would not be
possible to create a list [ 1I .. 1000000000000I ] since
Sequences are dened using the syntax:
the .NET runtime would attempt to create all one trillion
seq { expr }
elements up front, which would certainly consume all of
the available memory on a system before the operation
Similar to lists, sequences can be constructed using ranges completed.
and comprehensions:
Additionally, sequences can represent an innite number
> seq { 1 .. 10 };; (* seq ranges *) val it : seq<int> = seq of elements:
[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); ...]
> 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 = ()
36
Sys-
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 lters out duplicate entries.
Note: sequences can only be read in a forwardonly manner, so there is no corresponding foldBack function as found in the List and Array
modules.
37
> Seq.initInnite (fun x -> x*x) val it : seq<int> = seq > let test = 1 |> Seq.unfold (fun x -> if x <= 5 then
[0; 1; 4; 9; ...]
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
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 rst
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 bs = (0I, 1I) |> Seq.unfold (fun (a, b) ->
Some(a, (b, a + b) ) );; val bs : seq<bigint> > Seq.iter
(fun x -> printf "%O " x) (Seq.take 20 bs);; 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 rst value of the tuple is inserted as an element into the sequence, the second value
of the tuple is passed as the accumulator. The bs function is clever for its brevity, but its hard to understand
if you've never seen an unfold function. The following
demonstrates unfold in a more straightforward way:
Chapter 13
13.1 Sets
A set in F# is just a container for items. Sets do not pre- val count : Set<'a> -> int
serve the order in which items are inserted, nor do they
allow duplicate entries to be inserted into the collection.
Return the number of elements in the set.
Same as size.
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 val dierence : Set<'a> -> Set<'a> -> Set<'a>
set to start with.
Return a new set with the elements of the secConveniently, all instances of sets have an Add function
ond set removed from the rst.
with the type val Add : 'a -> Set<'a>. In other words, our
Add returns a set containing our new item, which makes
it easy to add items together in this fashion:
> let a = Set.ofSeq [ 1 .. 10 ] let b = Set.ofSeq [ 5 .. 15 ];;
> Set.empty.Add(1).Add(2).Add(7);; val it : Set<int> = val a : Set<int> val b : Set<int> > Set.dierence a b;; val
it : Set<int> = set [1; 2; 3; 4] > a - b;; (* The '-' operator
set [1; 2; 7]
is equivalent to Set.dierence *) val it : Set<int> = set
[1; 2; 3; 4]
Converting lists and sequences into sets Additionally,
the we can use Set.ofList and Set.ofSeq to convert an enval exists : ('a -> bool) -> Set<'a> -> bool
tire collection into a set:
> Set.ofList ["Mercury"; Venus"; Earth"; Mars";
Jupiter"; Saturn"; Uranus"; Neptune"];; val it :
Set<string> = set ["Earth"; Jupiter"; Mars"; Mercury"; ...]
13.1.1
Return a new collection containing only the elements of the collection for which the given
predicate returns true.
13.2. MAPS
39
13.2 Maps
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
val add :
'key -> 'a -> Map<'key,'a> ->
Map<'key,'a>
40
13.2.2
Examples
Chapter 14
Discriminated Unions
Discriminated unions, also called tagged unions, represent a nite, well-dened 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.
14.1 Creating
Unions
Discriminated
x: On y: O
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:
By convention, union names start with a lowercase charThis program has the following output:
acter, and union cases are written in PascalCase.
x: On y: O z: On toggle z: O
an On/O
14.3 Holding Data In Unions: a
dimmer switch
42
type 'a tree = | Leaf of 'a | Node of 'a tree * 'a tree (*
The syntax above is OCaml style. Its common to see
This program outputs:
unions dened using the ".NET style as follows which
x: On y: O z: Adjustable 0.25 toggle z: Adjustable 0.75 surrounds the type parameter with <'s and >'s after
the type name: type tree<'a> = | Leaf of 'a | Node of
tree<'a> * tree<'a> *)
Discriminated unions can easily model a wide variety of open System type 'a tree = | Leaf of 'a | Node of 'a tree
* 'a tree let rstTree = Node( Leaf 1, Node( Leaf 2,
trees and hierarchical data structures.
Node( Node( Leaf 4, Leaf 5 ), Leaf 3 ) ) ) let secondTree
For example, lets consider the following binary tree:
= Node( Node( Node( Leaf Red, Leaf Orange ),
/\ / \ 1 /\ / \ 2 /\ / \ /\ 3 / \ 4 5
Node( Leaf Yellow, Leaf Green ) ), Node( Leaf
Each node of our tree contains exactly two branches, and Blue, Leaf Violet ) ) let prettyPrint tree = let rec
each branch can either be a integer or another tree. We loop depth tree = let spacer = new String(' ', depth)
match tree with | Leaf(value) -> printfn "%s |- %A
can represent this tree as follows:
spacer value | Node(tree1, tree2) -> printfn "%s |"
type tree = | Leaf of int | Node of tree * tree
spacer loop (depth + 1) tree1 loop (depth + 1) tree2
loop 0 tree let main() = printfn rstTree:" prettyPrint
We can create an instance of the tree above using the fol- rstTree printfn secondTree:" prettyPrint secondTree
Console.ReadKey(true) |> ignore main()
lowing 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()
14.6 Examples
14.6.1 Built-in Union Types
F# has several built-in types derived from discriminated
unions, some of which have already been introduced in
this tutorial. These types include:
type 'a list = | Cons of 'a * 'a list | Nil type 'a option = |
Some of 'a | None
14.6.2
Propositional Logic
43
Chapter 15
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 variables are somewhat limited: mutables are inaccessible outside of the scope of the function where they
15.1 mutable Keyword
are dened. Specically, this means its not possible to
reference a mutable in a subfunction of another function.
The simplest mutable variables in F# are declared using Heres a demonstration in fsi:
the mutable keyword. Here is a sample using fsi:
> let testMutable() = let mutable msg = hello printfn
> let mutable x = 5;; val mutable x : int > x;; val it : int = "%s msg let setMsg() = msg <- world setMsg() printfn
"%s msg;; msg <- world --------^^^^^^^^^^^^^^^
5 > x <- 10;; val it : unit = () > x;; val it : int = 10
stdin(18,9): error FS0191: The mutable variable 'msg'
is used in an invalid way. Mutable variables may not be
As shown above, the <- operator is used to assign a muta- captured by closures. Consider eliminating this use of
ble variable a new value. Notice that variable assignment mutation or using a heap-allocated mutable reference
actually returns unit as a value.
cell via 'ref' and '!'.
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
44
45
cell1 := 10, this changes the value in memory to the following:
Memory ____ |____| cell1 |____| / |_10_| - cell2 |____| \
|____| cell3
15.2.1
Chapter 16
Control Flow
In all programming languages, control ow refers to the
decisions made in code that aect the order in which
statements are executed in an application. F#'s imperative control ow elements are similar to those encountered in other languages.
condition = true: inside the 'if' outside the 'if' block ------- outside the 'if' block
46
47
Chapter 17
Arrays
Arrays are a ubiquitous, familiar data structure used to val create : int -> 'T value -> 'T []
represent a group of related, ordered values. Unlike F#
data structures, arrays are mutable, meaning the values in
Creates an array with arraySize elements. Inian array can be changed after the array has been created.
tializes each element in the array with value.
> Array.create 5 Juliet";; val it : string [] = [|"Juliet";
Juliet"; Juliet"; Juliet"; Juliet"|]
17.1.1
Array literals
Creates an array with arraySize elements. Initializes each element in the array with the initializer function.
17.1.2
Array comprehensions
F# supports array comprehensions using ranges and generators in the same style and format as list comprehensions:
17.1.3
System.Array Methods
There are several methods in the System.Array module This list contains 5 items. The rst index is 0, and the last
index is 4.
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).
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
49
17.2.1
Array Slicing
F# supports a few useful operators which allow programmers to return slices or subarrays of an array using the
.[start..nish] operator, where one of the start and nish
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 rst 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 ecient to look at parts of an array using
a few index adjustments.
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
Multi-dimensional Arrays
A multi-dimensional array is literally an array of arrays. Conceptually, its 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.
17.2.2
50
Jagged arrays
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[]
17.2.3
List literals.
Pattern matching.
51
In laymens terms, this means we can access the nth element of any array in constant time, or in O(1) operations.
Arrays
Array literals.
Chapter 18
Mutable Collections
The .NET BCL comes with its own suite of
mutable collections which are found in the
System.Collections.Generic namespace. These builtin collections are very similar to their immutable
counterparts in F#.
sized:
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 -----------
Its easy to tell that .NET lists are mutable because their If you know the maximum size of the list beforehand,
Add methods return unit rather than returning another it is possible to avoid the performance hit by calling the
List<'T>(size : int) constructor instead. The following
list.
sample demonstrates how to add 1000 items to a list without resizing the internal array:
18.1.1
Underlying Implementation
53
mentation prevents ecient random access. Linked lists in the stack is at the bottom of the stack, and the last coin
have a few valuable methods:
in the stack appears at the top. We remove coins from top
(* Prepends an item to the LinkedList *) val AddFirst to bottom, so the last coin added to the stack is the rst
: 'T -> LinkedListNode<'T> (* Appends an items to one removed.
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>
Push
Pop
18.2.1
Stack<'T> Class
54
18.3 HashSet<'T>,
tionary<'TKey,
Classes
and Dic'TValue>
Chapter 19
[width] (optional)
56
hexadecimal (a-f)/Hexadecimal (A-F)/Octal integer %e, See Number Format Strings, Date and Time Format
%E, %f, %F, %g, %G: any basic oating point type Strings, and Enum Format Strings for a comprehensive
(oat,oat32) formatted using a C-style oating point reference on format speciers for .NET.
format specications, i.e %e, %E: Signed value having Programmers can read and write to the console using the
the form [-]d.dddde[sign]ddd where d is a single decimal System.Console class:
digit, dddd is one or more decimal digits, ddd is exactly
three decimal digits, and sign is + or - %f: Signed value open System let main() = Console.Write(Whats
having the form [-]dddd.dddd, where dddd is one or more your name? ") let name = Console.ReadLine() Condecimal digits. The number of digits before the decimal sole.Write(Hello, {0}", name) main()
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 19.2 System.IO Namespace
value and precision. %M: System.Decimal value %O:
Any value, printed by boxing the object and using its The System.IO namespace contains a variety of useful
ToString method(s) %A: Any value, printed by using Mi- classes for performing basic I/O.
crosoft.FSharp.Text.StructuredFormat.Display.any_to_string
with the default layout settings %a: A general format
specier, requires two arguments: (1) a function which 19.2.1 Files and Directories
accepts two arguments: (a) a context parameter of
the appropriate type for the given formatting func- The following classes are useful for interrogating the host
tion (e.g. an #System.IO.TextWriter) (b) a value to lesystem:
print and which either outputs or returns appropriate
text. (2) the particular value to print %t: A gen The System.IO.File class exposes several useful
eral format specier, requires one argument: (1) a
members for creating, appending, and deleting les.
function which accepts a context parameter of the
appropriate type for the given formatting function
System.IO.Directory exposes methods for creating,
(e.g. an #System.IO.TextWriter)and which either outmoving, and deleting directories.
puts or returns appropriate text. Basic integer types are:
System.IO.Path performs operations on strings
byte,sbyte,int16,uint16,int32,uint32,int64,uint64,nativeint,unativeint
which represent le paths.
Basic oating point types are: oat, oat32
Programmers can print to the console using the printf
method, however F# recommends reading console input
using the System.Console.ReadLine() method.
19.2.2 Streams
19.1.2
With .NET
Chapter 20
Exception Handling
When a program encounters a problem or enters an in- FormatException
valid state, it will often respond by throwing an exception.
Left to its own devices, an uncaught exception will crash
Occurs when s does not represent a numeric inan application. Programmers write exception handling
put.
code to rescue an application from an invalid state.
OverowException
20.1 Try/With
let
getNumber
msg
=
printf
msg;
int32(System.Console.ReadLine()) let x = getNumWe can catch all of these exceptions by adding additional
ber(x = ") let y = getNumber(y = ") printfn "%i + %i
match cases:
= %i x y (x + y)
let getNumber msg = printf msg;
try
int32(System.Console.ReadLine())
with
|
:?
This code is syntactically valid, and it has the correct
System.FormatException -> 1 | :?
Systypes. However, it can fail at run time if we give it a
tem.OverowException -> System.Int32.MinValue
bad input:
| :? System.ArgumentNullException -> 0
This program outputs the following:
x = 7 y = monkeys! ------------ FormatException was un- Its not necessary to have an exhaustive list of match cases
handled. Input string was not in a correct format.
on exception types, as the uncaught exception will simply
The string monkeys does not represent a number, so the move to the next method in the stack trace.
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)
ArgumentNullException
Occurs when s is a null reference.
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
57
58
x right) else if x < y then Node(y, add x left, right) else ministic cleanup of unmanaged resources. Its considered
failwithf Item '%A' has already been added to tree x
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/nally block in this fashion:
let writeToFile leName = let sw = new System.IO.StreamWriter(leName
:
string)
try
sw.Write(Hello
")
sw.Write(World!")
nally
Normally, an exception will cause a function to exit im- sw.Dispose()
mediately. However, a nally block will always execute,
even if the code throws an exception:
However, this can be occasionally bulky and cumberlet tryWithFinallyExample f = try printfn tryWithFi- some, especially when dealing with many objects which
nallyExample: outer try block try printfn tryWith- implement the IDisposable interface. F# provides the
FinallyExample: inner try block f() with | exn -> keyword use as syntactic sugar for the pattern above. An
printfn tryWithFinallyExample: inner with block equivalent version of the code above can be written as
reraise() (* raises the same exception we just caught *) follows:
nally printfn tryWithFinally: outer nally block let
catchAllExceptions f = try printfn "-------------" printfn let writeToFile leName = use sw = new SyscatchAllExceptions: try block tryWithFinallyExample tem.IO.StreamWriter(leName : string) sw.Write(Hello
f with | exn -> printfn catchAllExceptions: with block ") sw.Write(World!")
printfn Exception message: %s exn.Message let
main() = catchAllExceptions (fun () -> printfn Function The scope of a use statement is identical to the scope of a
executed successfully) catchAllExceptions (fun () -> let statement. F# will automatically call Dispose() on an
failwith Function executed with an error) main()
object when the identier goes out of scope.
20.3 Try/Finally
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 *) nally (* nally block guarantees
We can pattern match on our new existing exception type
our SqlConnection is closed, even if our sql statement
just as easily as any other exception:
fails *) conn.Close()
> let tryGetReindeerPosition name = try getReindeerPosition name with | ReindeerNotFoundException(s)
-> printfn Got ReindeerNotFoundException: %s
s 1;; val tryGetReindeerPosition : string -> int >
20.3.1 use Statement
tryGetReindeerPosition Comet";; val it : int = 4 >
Many objects in the .NET framework implement the tryGetReindeerPosition Rudolf";; Got ReindeerNotSystem.IDisposable interface, which means the objects FoundException: Rudolf val it : int = 1
have a special method called Dispose to guarantee deter-
20.5 Exception
structs
Handling
59
Con-
Chapter 21
Operator Overloading
Operator overloading allows programmers to provide new F# supports two types of operators: inx operators and
behavior for the default operators in F#. In practice, pro- prex operators.
grammers overload operators to provide a simplied syntax for objects which can be combined mathematically.
An inx operator takes two arguments, with the operator appearing in between both arguments (i.e. arg1 {op}
arg2). We can dene our own inx operators using the
syntax:
let sum = x + y
Here + is example of using a mathematical addition op- In addition to mathematical operators, F# has a variety of
inx operators dened as part of its library, for example:
erator.
let inline (|>) x f = f x let inline (::) hd tl = Cons(hd, tl)
let inline (:=) (x : 'a ref) value = x.contents <- value
In addition to overloading existing operators, its possible type 'a ref = { mutable contents : 'a } let (!) (x : 'a ref) =
to dene new operators. The names of custom operators x.contents
can only be one or more of the following characters:
!%&*+./<=>?@^|~
61
Chapter 22
Classes
In the real world, an object is a real thing. A cat, per- 22.1.1 Implicit Class Construction
son, computer, and a roll of duct tape are all real things
in the tangible sense. When we think about these things, Implicit class syntax is dened as follows:
we can broadly describe them in terms of a number of
type TypeName optional-type-arguments arguments [
attributes:
as ident ] = [ inherit type { as base } ] [ let-binding |
let-rec bindings ] * [ do-statement ] * [ abstract-binding |
Properties: a person has a name, a cat has four legs, member-binding | interface-implementation ] *
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.
Elements in brackets are optional, elements followed by a * may appear zero or more times.
Before you create an object, you have to identify the properties of your object and describe what it does. You dene properties and methods of an object in a class. There
are actually two dierent syntaxes for dening a class: an
implicit syntax and an explicit syntax.
62
63
can access its properties using .propertyName notation. 67890, x.Holder: Marge, x.Amount: 145
Heres 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, Bobs 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
Lets 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:
64
implementation ] *
Heres a class dened using the explicit syntax:
As you've probably guessed, the major dierence 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
Notice that we have to add an alias after our construc- a few other subtle dierences:
tor, new (x1, y1, x2, y2) as this), to access the elds of
The explicit syntax does not allow programmers to
our object being constructed. Each time we create a Line
declare let and do bindings.
object, the constructor will print to the console. We can
demonstrate this using fsi:
Even though you can use val elds in the implicit syntax, they must have the attribute [<Default> let line = new Line(1.0, 1.0, 4.0, 2.5);; val line : Line
Value>] and be mutable. It is more convenient to
Line constructor: {(1.000000, 1.000000), (4.000000,
use let bindings in this case. You can add public
2.500000)}, Line.Length: 3.354102
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.
In general, its up to the programmer to use the implicit
or explicit syntax to dene classes. However, the implicit
syntax is used more often in practice as it tends to result
in shorter, more readable class denitions.
65
For example, there is no dierence between the following type SomeClass(prop : int) = class member x.Prop =
class denitions:
prop static member SomeStaticMethod = This is a static
Both classes compile down to the same bytecode, but the method static member Copy (source : SomeClass) =
code using class inference allows us to omit a few unnec- new SomeClass(source.Prop) end
essary keywords.
Class inference and class explicit styles are considered acceptable. At the very least, when writing F# libraries,
don't dene 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.
Object.ReferenceEquals is a static method on the SysThere are two types of members you can add to an object: tem.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
Instance members, which can only be called from an Prop property.
object instance created using the new keyword.
When should you use static methods rather than in Static members, which are not associated with any stance methods?
object instance.
When the designers of the .NET framework were designing the System.String class, they had to decide where the
The following class has a static method and an instance Length method should go. They had the option of making
method:
the property an instance method (s.Length) or making it
type SomeClass(prop : int) = class member x.Prop = static (String.GetLength(s)). The .NET designers chose
prop static member SomeStaticMethod = This is a static to make Length an instance method because it is an intrinsic property of strings.
method end
On the other hand, the String class also has several static
We invoke a static method using the form class- methods, including String.Concat which takes a list of
Name.methodName. We invoke instance methods by string and concatenates them all together. Concatenatcreating an instance of our class and calling the methods ing strings is instance-agnostic, its does not depend on
using classInstance.methodName. Here is a demonstra- the instance members of any particular strings.
tion in fsi:
The following general principles apply to all OO lan> SomeClass.SomeStaticMethod;; (* invoking static guages:
method *) val it : string = This is a static method
> SomeClass.Prop;; (* doesn't make sense, we haven't
Instance members should be used to access propcreated an object instance yet *) SomeClass.Prop;; (*
erties intrinsic to an object, such as stringIndoesn't make sense, we haven't created an object instance
stance.Length.
yet *) ^^^^^^^^^^^^^^^ stdin(78,1): error FS0191:
property 'Prop' is not static. > let instance = new Some Instance methods should be used when they depend
Class(5);; val instance : SomeClass > instance.Prop;;
on state of a particular object instance, such as strin(* now we have an instance, we can call our instance
gInstance.Contains.
method *) val it : int = 5 > instance.SomeStaticMethod;;
(* can't invoke static method from instance *) in Instance methods should be used when its expected
stance.SomeStaticMethod;; (* can't invoke static
that programmers will want to override the method
method from instance *) ^^^^^^^^^^^^^^^^^^^^^^^^^^
in a derived class.
stdin(81,1): error FS0191: property 'SomeStaticMethod'
is static.
Static methods should not depend on a particular instance of an object, such as Int32.TryParse.
We can, of course, invoke instance methods from objects
passed into static methods, for example, lets say we add
a Copy method to our object dened above:
66
Constants, which are values that don't change for any - x.X2) + sqr(x.Y1 - x.Y2)) member x.ShiftH amount
class instance, should be declared as a static mem- = { x with X1 = x.X1 + amount; X2 = x.X2 + amount
bers, such as System.Boolean.TrueString.
} member x.ShiftV amount = { x with Y1 = x.Y1 +
amount; Y2 = x.Y2 + amount };; type Line = {X1: oat;
Y1: oat; X2: oat; Y2: oat;} with member ShiftH
22.2.2 Getters and Setters
: amount:float -> Line member ShiftV : amount:float
-> Line member Length : oat end > let line = { X1 =
Getters and setters are special functions which allow pro- 1.0; Y1 = 2.0; X2 = 5.0; Y2 = 4.5 };; val line : Line >
grammers to read and write to members using a conve- line.Length;; val it : oat = 4.716990566 > line.ShiftH
nient syntax. Getters and setters are written using this 10.0;; val it : Line = {X1 = 11.0; Y1 = 2.0; X2 = 15.0;
format:
Y2 = 4.5;} > line.ShiftV 5.0;; val it : Line = {X1 =
member alias.PropertyName with get() = some-value 1.0; Y1 = 3.0; X2 = 5.0; Y2 = 0.5;}
and set(value) = some-assignment
Union example
Heres a simple example using fsi:
> type shape = | Circle of oat | Rectangle of oat * oat
> type IntWrapper() = class let mutable num = 0 member | Triangle of oat * oat with member x.Area = match
x.Num with get() = num and set(value) = num <- value x with | Circle(r) -> Math.PI * r * r | Rectangle(b, h)
end;; type IntWrapper = class new : unit -> IntWrapper -> b * h | Triangle(b, h) -> b * h / 2.0 member x.Scale
member Num : int member Num : int with set end > let value = match x with | Circle(r) -> Circle(r + value)
wrapper = new IntWrapper();; val wrapper : IntWrapper | Rectangle(b, h) -> Rectangle(b + value, h + value) |
> wrapper.Num;; val it : int = 0 > wrapper.Num <- 20;; Triangle(b, h) -> Triangle(b + value, h + value);; type
shape = | Circle of oat | Rectangle of oat * oat |
val it : unit = () > wrapper.Num;; val it : int = 20
Triangle of oat * oat with member Scale : value:float
-> shape member Area : oat end > let mycircle =
Getters and setters are used to expose private members Circle(5.0);; val mycircle : shape > mycircle.Area;; val
to outside world. For example, our Num property allows it : oat = 78.53981634 > mycircle.Scale(7.0);; val it :
users to read/write to the internal num variable. Since shape = Circle 12.0
getters and setters are gloried 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:
22.3 Generic classes
type IntWrapper() = class let mutable num = 0 member
x.Num with get() = num and set(value) = if value > 10 We can also create classes which take generic types:
|| value < 0 then raise (new Exception(Values must be type 'a GenericWrapper(initialVal : 'a) = class let
between 0 and 10)) else num <- value end
mutable internalVal = initialVal member x.Value with
get() = internalVal and set(value) = internalVal <- 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
67
Chapter 23
Inheritance
Many object-oriented languages use inheritance exten- other words, its not possible to create a class which desively in the .NET BCL to construct class hierarchies.
rives from Student and Employee simultaneously.
23.1 Subclasses
A subclass is, in the simplest terms, a class derived from
a class which has already been dened. A subclass inher- 23.1.1 Overriding Methods
its its members from a base class in addition to adding
its own members. A subclass is dened using the inherit
keyword as shown below:
Occasionally, you may want a derived class to change the
type Person(name) = member x.Name = name member default behavior of methods inherited from the base class.
x.Greet() = printfn Hi, I'm %s x.Name type Stu- For example, the output of the .ToString() method above
dent(name, studentID : int) = inherit Person(name) let isn't very useful. We can override that behavior with a
mutable _GPA = 0.0 member x.StudentID = studentID dierent implementation using the override:
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
23.1.2
69
Abstract Classes
An abstract class is one which provides an incomplete implementation of an object, and requires a programmer to
create subclasses of the abstract class to ll 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 -> oat
The rst 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 : oat) = inherit
Shape(position) member x.Radius = radius override x.Draw() = printfn "(Circle)" override x.Area() =
Math.PI * radius * radius type Rectangle(position : Point,
width : oat, height : oat) = 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 : oat) = 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 : oat, sideB : oat, sideC :
oat) = inherit Shape(position) member x.SideA = sideA
member x.SideB = sideB member x.SideC = sideC override x.Draw() = printfn "(Triangle)" override x.Area() =
(* Herons 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 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
Now we have several dierent implementations of the object of type 'System.Int32' to type 'System.String'. at
Shape class. We can experiment with these in fsi:
<StartupCode$FSI_0067>.$FSI_0067._main() stopped
> let position = { X = 0; Y = 0 };; val position : due to error
Point > let circle, rectangle, square, triangle = new
Circle(position, 5.0), new Rectangle(position, 2.0, 7.0), Since intAsObj holds an int boxed as an obj, we can
new Square(position, 10.0), new Triangle(position, downcast to an int as needed. However, we cannot down3.0, 4.0, 5.0);; val triangle : Triangle val square : cast to a string because its an incompatible type. DownSquare val rectangle : Rectangle val circle : Circle casting is considered unsafe because the error isn't de> circle.ToString();; val it : string = Circle, position tectable by the type-checker, so an error with a down-cast
= {0, 0}, area = 78.539816 > triangle.ToString();; always results in a runtime exception.
val it : string = Triangle, position = {0, 0}, area
= 6.000000 > square.Width;; val it : oat = 10.0
> square.ToRectangle().ToString();; val it : string = Up-casting example
Rectangle, position = {0, 0}, area = 100.000000 >
rectangle.Height, rectangle.Width;; val it : oat * oat = open System type Point = { X : int; Y : int } [<AbstractClass>] type Shape() = override x.ToString() = sprintf
(7.0, 2.0)
70
23.2.2
Public, Private,
Members
and Protected
Chapter 24
Interfaces
An objects interface refers to all of the public members 24.1 Dening Interfaces
and functions that a function exposes to consumers of the
object. For example, take the following:
According to the F# specication, interfaces are dened
type Monkey(name : string, birthday : DateTime) with the following syntax:
= let mutable _birthday = birthday let mutable type type-name = interface inherits-decl member-defns
_lastEaten = DateTime.Now let mutable _food- end
sEaten = [] : string list member this.Speak() =
printfn Ook ook!" member this.Name = name
member this.Birthday with get() = _birthday and
Note: The interface/end tokens can be omitted
set(value) = _birthday <- value member internal
when using the #light syntax option, in which
this.UpdateFoodsEaten(food) = _foodsEaten <- food
case Type Kind Inference (10.1) is used to
:: _foodsEaten member internal this.ResetLastEaten()
determine the kind of the type. The presence
= _lastEaten <- DateTime.Now member this.IsHungry
of any non-abstract members or constructors
= (DateTime.Now - _lastEaten).TotalSeconds >= 5.0
means a type is not an interface type.
member this.GetFoodsEaten() = _lastEaten member this.Feed(food) = this.UpdateFoodsEaten(food)
For example:
this.ResetLastEaten() this.Speak()
type ILifeForm = (* .NET convention recommends
This class contains several public, private, and internal the prex 'I' on all interfaces *) abstract Name : string
members. However, consumers of this class can only ac- abstract Speak : unit -> unit abstract Eat : unit -> unit
cess 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 : 24.2 Using Interfaces
food:string -> unit member GetFoodsEaten : unit
-> DateTime member Speak : unit -> unit member Since they only dene a set of public method signatures,
Birthday : DateTime member IsHungry : bool member users need to create an object to implement the interface.
Name : string member Birthday : DateTime with set end Here are three classes which implement the ILifeForm
interface in fsi:
Notice the _birthday, _lastEaten, _foodsEaten, UpdateFoodsEaten, and ResetLastEaten members are inaccessible to the outside world, so they are not part of this objects public interface.
All interfaces you've seen so far have been intrinsically
tied to a specic object. However, F# and many other
OO languages allow users to dene interfaces as standalone types, allowing us to eectively separate an objects
interface from its implementation.
71
72
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 : oat member Weight : oat 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 dene instance members signatures on objects. In other words, they cannot
dene static member signatures or constructor signatures.
24.2.1
24.2.2
24.3. EXAMPLES
Note: Interface hierarchies are occasionally
useful, however deep, complicated hierarchies
can be cumbersome to work with.
24.3 Examples
24.3.1
73
classes
74
type Processor() = (* ... *) member this.Process items
= try (* do stu 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.
Lets 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 IFailureNotier = abstract Notify : string -> unit
type Processor(notier : IFailureNotier) = (* ... *)
member this.Process items = try // do stu with items
with | err -> notier.Notify(err.Message) (* concrete implementations of IFailureNotier *) type EmailNotier()
= interface IFailureNotier with member Notify(msg)
= (new Emailer()).SendMsg(admin@company.com,
Error! " + msg) type DummyNotier() = interface
IFailureNotier with member Notify(msg) = () // swallow message type LogleNotier(lename : string) =
interface IFailureNotifer with member Notify(msg) =
System.IO.File.AppendAllText(lename, msg)
Now, we create a processor and pass in the kind of FailureNotier we're interested in. In test environments,
we'd use new Processor(new DummyNotier()); in production, we'd use new Processor(new EmailNotier()) or
new Processor(new LogleNotier(@"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 OByOneAdder() = 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 OByOneAdder = class interface
IAddStrategy new : unit -> OByOneAdder end type
SwappableAdder = class new : adder:IAddStrategy
-> SwappableAdder member Add : x:int -> (int ->
int) member Adder : IAddStrategy member Adder :
Chapter 25
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, lets 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 buttons 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 indenite 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.
76
<- Moe p.NameChanged.Add(fun () -> printfn "-Another handler attached to NameChanged!") printfn
Its also causes programs behave non-deterministically.
p.Name <- Bo printfn The function NameChanged is
invoked eortlessly.
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 Its also
causes programs behave non-deterministically. p.Name
This program outputs the following:
<- Bo printfn The function NameChanged is invoked
Event handling is easy -- Name changed! New name: Joe eortlessly.
It handily decouples objects from one another -- Name
changed! New name: Moe Its also causes programs
behave non-deterministically. -- Name changed! New This program outputs the following:
name: Bo -- Another handler attached to NameChanged! Event handling is easy -- Name changed! New name: Joe
The function NameChanged is invoked eortlessly.
It handily decouples objects from one another -- Name
changed! New name: Moe Its also causes programs behave non-deterministically. -- Another handler attached
Note: When multiple callbacks are connected
to NameChanged! The function NameChanged is into a single event, they are executed in the orvoked eortlessly.
der they are added. However, in practice, you
should not write code with the expectation that
events will trigger in a particular order, as do25.3.2 Dening New Delegate Types
ing so can introduce complex dependencies between functions. Event-driven programming
F#'s event handling model is a little dierent from the
is often non-deterministic and fundamentally
rest of .NET. If we want to expose F# events to dierent
stateful, which can occasionally be at odds with
languages like C# or VB.NET, we can dene a custom
the spirit of functional programming. Its best
delegate type which compiles to a .NET delegate using
to write callback functions which do not modthe delegate keyword, for example:
ify state, and do not depend on the invocation
of any prior events.
type NameChangingEventArgs(oldName : string, new-
Adding and Removing Event Han- sponds to the .NET naming guidelines which recommend
dlers
that all events have the type val eventName : (sender : obj
77
open System type SuperFileReader() = let progressChanged
=
new
Event<int>()
member
this.ProgressChanged = progressChanged.Publish member this.OpenFile (lename : string, charsPerBlock)
= use sr = new System.IO.StreamReader(lename) let
streamLength = int64 sr.BaseStream.Length let sb =
new System.Text.StringBuilder(int streamLength) let
charBuer = 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(charBuer,
0, charBuer.Length) totalCharsRead <- totalCharsRead
+ charsRead (* appending chars read from buer *)
sb.Append(charBuer, 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 leReader = new SuperFileReader() leReader.ProgressChanged.Add(fun
percent -> printfn "%i percent done... percent) let
x = leReader.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 leReader : 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[...]
78
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 %ss 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:
79
p.NameChanging |> Event.lter (fun (e : NameChangingEventArgs) -> let exboyfriends = ["Steve"; Mike";
Jon"; Seth"] List.exists (fun forbiddenName >forbiddenName = e.NewName) exboyfriends ) |>
Event.listen (fun e -> printfn "-- No %ss allowed!"
e.NewName e.Cancel <- true)
Chapter 26
26.1.2
81
Seq = begin val foralli : (int -> 'a -> bool) -> seq<'a>
-> bool end module StringExtensions = begin end >
hello world.IsPalindrome;; val it : bool = false > System.String.Reverse(hello world);; val it : System.String
= dlrow olleh
F# supports extension methods, which allow programmers to add new static and instance methods to classes By default, all members in a module are accessible from
and modules without inheriting from them.
outside the module. However, a module often contain
members which should not be accessible outside itself,
Extending a Module
such as helper functions. One way to expose only a subThe Seq module contains several pairs of methods:
set of a modules members is by creating a signature le
for that module. (Another way is to apply .Net CLR ac iter/iteri
cess modiers of public, internal, or private to individual
declarations).
map/mapi
Seq has a forall member, but does not have a corresponding foralli function, which includes the index of each
sequence element. We add this missing method to the
module simply by creating another module with the same
name. For example, using fsi:
> module Seq = let foralli f s = s |> Seq.mapi (fun i x ->
i, x) (* pair item with its index *) |> Seq.forall (fun (i, x)
-> f i x) (* apply item and index to function *) let isPalindrome (input : string) = input |> Seq.take (input.Length
/ 2) |> Seq.foralli (fun i x -> x = input.[input.Length i - 1]);; module Seq = begin val foralli : (int -> 'a ->
bool) -> seq<'a> -> bool end val isPalindrome : string
-> bool > isPalindrome hello";; val it : bool = false >
isPalindrome racecar";; val it : bool = true
Extending a Type
The System.String has many useful methods, but lets say
we thought it was missing a few important functions, Reverse and IsPalindrome. Since this class is marked as
sealed or NotInheritable, we can't create a derived version of this class. Instead, we create a module with the
new methods we want. Heres an example in fsi which
demonstrates how to add new static and instance methods to the String class:
> module Seq = let foralli f s = s |> Seq.mapi (fun i x ->
i, x) (* pair item with its index *) |> Seq.forall (fun (i, x)
-> f i x) (* apply item and index to function *) module
StringExtensions = type System.String with member
this.IsPalindrome = this |> Seq.take (this.Length / 2) |>
Seq.foralli (fun i x -> this.[this.Length - i - 1] = x) static
member Reverse(s : string) = let chars : char array =
let temp = Array.zeroCreate s.Length let charsToTake
= if temp.Length % 2 <> 0 then (temp.Length + 1)
/ 2 else temp.Length / 2 s |> Seq.take charsToTake
|> Seq.iteri (fun i x -> temp.[i] <- s.[temp.Length
- i - 1] temp.[temp.Length - i - 1] <- x) temp new
System.String(chars) open StringExtensions;; module
Signature les have the same name as their corresponding module, but end with a ".fsi extension (f-sharp interface). Signature les always come before their implementation les, which have a corresponding ".fs extension.
For example:
DataStructures.fsi
type 'a stack = | EmptyStack | StackNode of 'a * 'a stack
module Stack = val getRange : int -> int -> int stack val
hd : 'a stack -> 'a val tl : 'a stack -> 'a stack val fold : ('a
-> 'b -> 'a) -> 'a -> 'b stack -> 'a val reduce : ('a -> 'a ->
'a) -> 'a stack -> 'a
DataStructures.fs
type 'a stack = | EmptyStack | StackNode of 'a * 'a
stack module Stack = (* helper functions *) let internal_head_tail = function | EmptyStack -> failwith
Empty stack | StackNode(hd, tail) -> hd, tail let rec
internal_fold_left f acc = function | EmptyStack -> acc
| StackNode(hd, tail) -> internal_fold_left f (f acc hd)
tail (* public functions *) let rec getRange startNum
endNum = if startNum > endNum then EmptyStack
else StackNode(startNum, getRange (startNum+1)
endNum) let hd s = internal_head_tail s |> fst let tl
s = internal_head_tail s |> snd let fold f seed stack
= internal_fold_left f seed stack let reduce f stack =
internal_fold_left f (hd stack) (tl stack)
Program.fs
open DataStructures let x = Stack.getRange 1 10 printfn
"%A (Stack.hd x) printfn "%A (Stack.tl x) printfn
"%A (Stack.fold ( * ) 1 x) printfn "%A (Stack.reduce
( + ) x) (* printfn "%A (Stack.internal_head_tail x) *)
(* will not compile *)
Since Stack.internal_head_tail is not dened in our interface le, the method is marked private and no longer
accessible outside of the DataStructures module.
82
Module signatures are useful to building a code librarys
skeleton, however they have a few caveats. If you want
to expose a class, record, or union in a module through
a signature, then the signature le must expose all of the
objects members, records elds, and unions cases. Additionally, the signature of the function dened in the module and its corresponding signature in the signature le
must match exactly. Unlike OCaml, F# does not allow a
function in a module with the generic type 'a -> 'a -> 'a to
be restricted to int -> int -> int in the signature le.
Code is grouped under a namespace using the namespace Or equivalently, we dene a module and place it a namespace simultaneously using:
keyword:
module Princess.Collections.DataStructures type 'a
stack = | EmptyStack | StackNode of 'a * 'a stack let
namespace Princess.Collections type 'a stack = | Empsomefunction() = 12 (* ... *)
tyStack | StackNode of 'a * 'a stack module Stack = val
getRange : int -> int -> int stack val hd : 'a stack -> 'a
val tl : 'a stack -> 'a stack val fold : ('a -> 'b -> 'a) -> 'a
-> 'b stack -> 'a val reduce : ('a -> 'a -> 'a) -> 'a stack -> 'a
DataStructures.fsi
DataStructures.fs
namespace Princess.Collections type 'a stack = | EmptyStack | StackNode of 'a * 'a stack module Stack = (*
helper functions *) let internal_head_tail = function |
EmptyStack -> failwith Empty stack | StackNode(hd,
tail) -> hd, tail let rec internal_fold_left f acc = function
| EmptyStack -> acc | StackNode(hd, tail) -> internal_fold_left f (f acc hd) tail (* public functions *) let rec
getRange startNum endNum = if startNum > endNum
then EmptyStack else StackNode(startNum, getRange
(startNum+1) endNum) let hd s = internal_head_tail s
|> fst let tl s = internal_head_tail s |> snd let fold f seed
stack = internal_fold_left f seed stack let reduce f stack
= internal_fold_left f (hd stack) (tl stack)
namespace Princess.Collections type 'a stack = | EmptyStack | StackNode of 'a * 'a stack module Stack = (*
helper functions *) let internal_head_tail = function |
EmptyStack -> failwith Empty stack | StackNode(hd,
tail) -> hd, tail let rec internal_fold_left f acc = function
| EmptyStack -> acc | StackNode(hd, tail) -> internal_fold_left f (f acc hd) tail (* public functions *) let rec
getRange startNum endNum = if startNum > endNum
then EmptyStack else StackNode(startNum, getRange
(startNum+1) endNum) let hd s = internal_head_tail s
|> fst let tl s = internal_head_tail s |> snd let fold f seed
Program.fs
stack = internal_fold_left f seed stack let reduce f stack
open Princess.Collections let x = Stack.getRange 1 = internal_fold_left f (hd stack) (tl stack)
MoreDataStructures.fs
namespace Princess.Collections type 'a tree when 'a :>
System.IComparable<'a> = | EmptyTree | TreeNode of
'a * 'a tree * 'a tree module Tree = let rec insert (x :
#System.IComparable<'a>) = function | EmptyTree ->
TreeNode(x, EmptyTree, EmptyTree) | TreeNode(y, l,
r) as node -> match x.CompareTo(y) with | 0 -> node | 1
-> TreeNode(y, l, insert x r) | 1 -> TreeNode(y, insert
x l, r) | _ -> failwith CompareTo returned illegal value
Since we have a leading namespace declaration in both
les, F# does not create any implicit modules. The 'a
stack, 'a tree, Stack, and Tree types are all accessible
through the Princess.Collections namespace:
Program.fs
open Princess.Collections let x = Stack.getRange 1 10 let
y = let rnd = new System.Random() [ for a in 1 .. 10 ->
rnd.Next(0, 100) ] |> Seq.fold (fun acc x -> Tree.insert
x acc) EmptyTree printfn "%A (Stack.hd x) printfn
"%A (Stack.tl x) printfn "%A (Stack.fold ( * ) 1 x)
printfn "%A (Stack.reduce ( + ) x) printfn "%A y
26.2.2
83
Chapter 27
Units of Measure
Units of measure allow programmers to annotate oats
and integers with statically-typed unit metadata. This can
be handy when writing programs which manipulate oats
and integers representing specic units of measure, such
as kilograms, pounds, meters, newtons, pascals, etc. F#
will verify that units are used in places where the programmer intended. For example, the F# compiler will
throw an error if a oat<m/s> is used where it expects a
oat<kg>.
In short, Microsoft depends on coding conventions to en27.1.2 Decorating Data With Contextual code contextual data about a variable, and they depend on
code reviews to enforce correct usage of a variable from
Information
its context. This works in practice, but its still possible
for incorrect code to work its way it the product without
In an article Making Code Look Wrong, Joel Spolsky
the bug being detected for months.
describes a scenario in which, during the design of Microsoft Word and Excel, programmers at Microsoft were If Microsoft were using a language with units of measure,
required to track the position of objects on a page using they could have dened their own rw, col, xw, xl, and cb
units of measure so that an assignment of the form int<xl>
two non-interchangeable coordinate systems:
= int<cb> not only fails visual inspection, it doesn't even
In WYSIWYG word processing, you have
compile.
84
85
Units can be dened for integral types too:
86
0.718)
Since units are erased from compiled code, they are not
considered a real data type, so they can't be used directly
as a type parameter in generic functions and classes. For
example, the following code will not compile:
> type triple<'a> = { a : oat<'a>; b : oat<'a>; c :
oat<'a>};; type triple<'a> = { a : oat<'a>; b : oat<'a>;
c : oat<'a>};; ------------------------------^^ stdin(40,31):
error FS0191: Expected unit-of-measure parameter, not
type parameter. Explicit unit-of-measure parameters
must be marked with the [<Measure>] attribute
F# does not infer that 'a is a unit of measure above, possibly because the following code appears correct, but it can
be used in non-sensical ways:
type quad<'a> = { a : oat<'a>; b : oat<'a>; c :
oat<'a>; d : 'a}
The type 'a can be a unit of measure or a data type, but
not both at the same time. F#'s type checker assumes 'a is
a type parameter unless otherwise specied. We can use
the [<Measure>] attribute to change the 'a to a unit of
measure:
> type triple<[<Measure>] 'a> = { a : oat<'a>; b :
oat<'a>; c : oat<'a>};; type triple<[<Measure>] 'a> =
{a: oat<'a>; b: oat<'a>; c: oat<'a>;} > { a = 7.0<kg>;
b = 10.5<_>; c = 0.5<_> };; val it : triple<kg> = {a =
7.0; b = 10.5; c = 0.5;}
27.5 F# PowerPack
The F# PowerPack (FSharp.PowerPack.dll) includes a
number of predened units of measure for scientic applications. These are available in the following modules:
Microsoft.FSharp.Math.SI - a variety of predened
measures in the International System of Units (SI).
Microsoft.FSharp.Math.PhysicalConstants - Fundamental physical constants with units of measure.
Chapter 28
Caching
Caching is often useful to re-use data which has already puted on every successive call. Long-running pure funcbeen computed. F# provides a number of built-in tech- tions (i.e. functions which have no side-eects) are good
niques to cache data for future use.
candidates for memoization. Consider the recursive definition for computing Fibonacci numbers:
> #time;; --> Timing now on > let rec b n = if n = 0I
then 0I elif n = 1I then 1I else b (n - 1I) + b(n - 2I);;
Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0,
F# automatically caches the value of any function which gen1: 0, gen2: 0 val b : Math.bigint -> Math.bigint > b
takes no parameters. When F# comes across a function 35I;; Real: 00:00:23.557, CPU: 00:00:23.515, GC gen0:
with no parameters, F# will only evaluate the function 2877, gen1: 3, gen2: 0 val it : Math.bigint = 9227465I
once and reuse its value everytime the function is accessed. Compare the following:
Beyond b 35I, the runtime of the function becomes unlet isNebraskaCity_bad city = let cities = printfn Cre- bearable. Each recursive call to the b function throws
ating cities Set ["Bellevue"; Omaha"; Lincoln"; away all of its intermediate calculations to b(n - 1I)
Papillion"] |> Set.ofList cities.Contains(city) let isNe- and b(n - 2I), giving it a runtime complexity of about
braskaCity_good = let cities = printfn Creating cities O(2^n). What if we kept all of those intermediate calcuSet ["Bellevue"; Omaha"; Lincoln"; Papillion"] |> lations around in a lookup table? Heres the memoized
version of the b function:
Set.ofList fun city -> cities.Contains(city)
> #time;; --> Timing now on > let rec b = let dict =
Both functions accept and return the same values, but they new System.Collections.Generic.Dictionary<_,_>() fun
have very dierent behavior. Heres a comparison of the n -> match dict.TryGetValue(n) with | true, v -> v |
false, _ -> let temp = if n = 0I then 0I elif n = 1I then
output in fsi:
1I else b (n - 1I) + b(n - 2I) dict.Add(n, temp) temp;;
The implementation of isNebraskaCity_bad forces F# to val b : (Math.bigint -> Math.bigint) > b 35I;; Real:
re-create the internal set on each call. On the other hand, 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1:
isNebraskaCity_good is a value initialized to the function 0, gen2: 0 val it : Math.bigint = 9227465I
fun city -> cities.Contains(city), so it creates its internal
set once and reuses it for all successive calls.
Much better! This version of the b function runs almost
instaneously. In fact, since we only calculate the value of
Note: Internally, isNebraskaCity_bad is comany b(n) precisely once, and dictionary lookups are an
piled as a static function which constructs a set
O(1) operation, this b function runs in O(n) time.
on every call. isNebraskaCity_good is comNotice all of the memoization logic is contained in the
piled as a static readonly property, where the
b function. We can write a more general function to
value is initialized in a static constructor.
memoize any function:
This distinction is often subtle, but it can have a huge im- let memoize f = let dict = new System.Collections.Generic.Dictionary<_,_>() fun n ->
pact on an applications performance.
match dict.TryGetValue(n) with | (true, v) -> v | _ ->
let temp = f(n) dict.Add(n, temp) temp let rec b =
memoize(fun n -> if n = 0I then 0I elif n = 1I then 1I
28.2 Memoization
else b (n - 1I) + b (n - 2I) )
Memoization is a fancy word meaning that computed
values are stored in a lookup table rather than recom87
88
Chapter 29
Active Patterns
Active Patterns allow programmers to wrap arbitrary val- tween active patterns and explicitly dened unions:
ues in a union-like data structure for easy pattern matching. For example, its possible wrap objects with an active
Active patterns dene an anonymous union, where
pattern, so that you can use objects in pattern matching
the explicit union has a name (numKind, seqWrapas easily as any other union type.
per, etc.).
Active patterns determine their constructor parameters using a kind of type-inference, whereas we need
to explicitly dene the constructor parameters for
each case of our explicit union.
The syntax for using active patterns looks a little odd, but
once you know whats going on, its very easy to understand. Active patterns are used in pattern matching expressions, for example:
Even and Odd are union constructors, so our active pattern either returns an instance of Even or an instance of Whats going on here? When the pattern matching funcOdd. The code above is roughly equivalent to the follow- tion encounters Even, it calls (|Even|Odd|) with parameter
ing:
in the match clause, its as if you've written:
type numKind = | Even | Odd let get_choice n = if n % 2 type numKind = | Even | Odd let get_choice n = if n
= 0 then Even else Odd
% 2 = 0 then Even else Odd let testNum n = match
get_choice n with | Even -> printfn "%i is even n | Odd
Active patterns can also dene union constructors which -> printfn "%i is odd n
take a set of parameters. For example, consider we can
wrap a seq<'a> with an active pattern as follows:
The parameter in the match clause is always passed as the
let (|SeqNode|SeqEmpty|) s = if Seq.isEmpty s then last argument to the active pattern expression. Using our
seq example from earlier, we can write the following:
SeqEmpty else SeqNode ((Seq.hd s), Seq.skip 1 s)
> let (|SeqNode|SeqEmpty|) s = if Seq.isEmpty s then
SeqEmpty else SeqNode ((Seq.head s), Seq.skip 1 s)
This code is, of course, equivalent to the following:
let perfectSquares = seq { for a in 1 .. 10 -> a * a
type 'a seqWrapper = | SeqEmpty | SeqNode of 'a } let rec printSeq = function | SeqEmpty -> printfn
* seq<'a> let get_choice s = if Seq.isEmpty s then Done. | SeqNode(hd, tl) -> printf "%A " hd printSeq
SeqEmpty else SeqNode ((Seq.hd s), Seq.skip 1 s)
tl;; val ( |SeqNode|SeqEmpty| ) : seq<'a> -> Choice<('a
* seq<'a>),unit> val perfectSquares : seq<int> val
You've probably noticed the immediate dierence be- printSeq : seq<'a> -> unit > printSeq perfectSquares;; 1
89
90
4 9 16 25 36 49 64 81 100 Done.
Traditionally, seqs are resistant to pattern matching, but A partial active pattern is a special class of single-case
now we can operate on them just as easily as lists.
active patterns: it either returns Some or None. For example, a very handy active pattern for working with regex
can be dened as follows:
29.1.2
91
Chapter 30
30.1 Stacks
let stack = StackNode(1, StackNode(2, StackNode(3, We can implement this function with minimal eort using
the following:
StackNode(4, StackNode(5, EmptyStack)))))
let rec append x y = match x with | EmptyStack -> y |
Each StackNode contains a value and a pointer to the next StackNode(hd, tl) -> StackNode(hd, append tl y)
stack in the list. The resulting data structure can be diagrammed as follows:
Stacks are very easy to work with and implement. The
___ ___ ___ ___ ___ |_1_|->|_2_|->|_3_|->|_4_|->|_5_|- principles behind copying nodes to modify stacks is
fundamentally the same for all persistent data structures.
>Empty
We can create a boilerplate stack module as follows:
92
30.2. QUEUES
StackNode(hd, tl) -> StackNode(hd, update (index - 1)
value tl) let rec append x y = match x with | EmptyStack
-> y | StackNode(hd, tl) -> StackNode(hd, append tl y)
let rec map f = function | EmptyStack -> EmptyStack
| StackNode(hd, tl) -> StackNode(f hd, map f tl) let
rec rev s = let rec loop acc = function | EmptyStack
-> acc | StackNode(hd, tl) -> loop (StackNode(hd,
acc)) tl loop EmptyStack s let rec contains x = function
| EmptyStack -> false | StackNode(hd, tl) -> hd =
x || contains x tl let rec fold f seed = function | EmptyStack -> seed | StackNode(hd, tl) -> fold f (f seed hd) tl
30.2 Queues
93
very practical in practice. We can certainly improve on
the implementation of immutable queues.
To enqueue a new item, prepend it to the front of r; to dequeue an item, pop it o f. Both enqueues and dequeues
Queues aren't quite as straightforward as stacks. A naive are O(1) operations. Of course, at some point, f will be
queue can be implemented using a stack, with the caveat empty and there will be no more items to dequeue; in this
case, simply move all items from r to f and reverse the list.
that:
While the queue certainly has O(n) worst-case behavior,
it has acceptable O(1) amortized (average case) bounds.
Items are always appended to the end of the list, and
The code for this implementation is straight forward:
dequeued from the head of the stack.
30.2.1
Naive Queue
-OR- Items are prepended to the front of the stack, type Queue<'a>(f : stack<'a>, r : stack<'a>) = let check
and dequeued by reversing the stack and getting its = function | EmptyStack, r -> Queue(Stack.rev r, EmptyStack) | f, r -> Queue(f, r) member this.hd = match f
head.
with | EmptyStack -> failwith empty | StackNode(hd,
tl) -> hd member this.tl = match f, r with | EmptyStack,
(* AwesomeCollections.fsi *) type 'a stack = | EmptyS- _ -> failwith empty | StackNode(x, f), r -> check(f,
tack | StackNode of 'a * 'a stack module Stack = begin r) member this.enqueue(x) = check(f, StackNode(x,
val hd : 'a stack -> 'a val tl : 'a stack -> 'a stack val cons : r)) static member empty = Queue<'a>(Stack.empty,
'a -> 'a stack -> 'a stack val empty : 'a stack val rev : 'a Stack.empty)
stack -> 'a stack end [<Class>] type 'a Queue = member
hd : 'a member tl : 'a Queue member enqueue : 'a -> 'a
This is a simple, common, and useful implementation of
Queue static member empty : 'a Queue
(* AwesomeCollections.fs *) type 'a stack = | Emp- an immutable queue. The magic is in the check function
tyStack | StackNode of 'a * 'a stack module Stack = which maintains that f always contains items if they are
let hd = function | EmptyStack -> failwith Empty available.
stack | StackNode(hd, tl) -> hd let tl = function
Note: The queues periodic O(n) worst case
| EmptyStack -> failwith Emtpy stack | StackNbehavior can give it unpredictable response
ode(hd, tl) -> tl let cons hd tl = StackNode(hd, tl) let
times, especially in applications which rely
empty = EmptyStack let rec rev s = let rec loop acc
heavily on persistence since its possible to hit
= function | EmptyStack -> acc | StackNode(hd, tl) ->
the pathological case each time the queue is acloop (StackNode(hd, acc)) tl loop EmptyStack s type
cessed. However, this particular implementaQueue<'a>(item : stack<'a>) = member this.hd with
tion of queues is perfectly adequate for the vast
get() = Stack.hd (Stack.rev item) member this.tl with
majority of applications which do not require
get() = Queue(item |> Stack.rev |> Stack.tl |> Stack.rev)
persistence or uniform response times.
member this.enqueue(x) = Queue(StackNode(x, item))
override this.ToString() = sprintf "%A item static
member empty = Queue<'a>(Stack.empty)
As shown above, we often want to wrap our underlying
data structure in class for two reasons:
We use an interface le to hide the Queue classs con1. To simplify the interface to the data structure. For
structor. Although this technically satises the function
example, clients neither know nor care that our
of a queue, every dequeue is an O(n) operation where n
queue uses two stacks; they only know that items in
is the number of items in the queue. There are lots of
the queue obey the principle of rst-in, rst-out.
variations on the same approach, but these are often not
94
(* AwesomeCollections.fsi *) [<Class>] type 'a Bina2. The root node is always black.
ryTree = member hd : 'a member exists : 'a -> bool
3. No red node has a red child.
member insert : 'a -> 'a BinaryTree
(* AwesomeCollections.fs *) type 'a tree = | EmptyTree
4. Every simple path from a given node to any of its de| TreeNode of 'a * 'a tree * 'a tree module Tree =
scendant leaves contains the same number of black
let hd = function | EmptyTree -> failwith empty |
nodes.
TreeNode(hd, l, r) -> hd let rec exists item = function |
EmptyTree -> false | TreeNode(hd, l, r) -> if hd = item
then true elif item < hd then exists item l else exists item
13
r let rec insert item = function | EmptyTree -> TreeNode(item, EmptyTree, EmptyTree) | TreeNode(hd, l,
8
17
r) as node -> if hd = item then node elif item < hd
1
11
15
25
then TreeNode(hd, insert item l, r) else TreeNode(hd,
l, insert item r) type 'a BinaryTree(inner : 'a tree) =
NIL
NIL
NIL
NIL
NIL
6
22
27
member this.hd = Tree.hd inner member this.exists
item = Tree.exists item inner member this.insert item =
NIL
NIL
NIL
NIL
NIL
NIL
BinaryTree(Tree.insert item inner) member this.empty
= BinaryTree<'a>(EmptyTree)
An example of a red-black tree
We're using an interface and a wrapper class to hide the
implementation details of the tree from the user, otherwise the user could construct a tree which invalidates the
specic ordering rules used in the binary tree.
This implementation is simple and it allows us to add and
lookup any item in the tree in O(log n) best case time.
However, it suers from a pathological case: if we add
items in sorted order, or mostly sorted order, then the
tree can become heavily unbalanced. For example, the
following code:
[1 ..
95
B(z) / \ R(x) d / \ a R(y) / \ b c || \/ B(z) R(y) B(x) / \ / \ / type 'a tree = | Node of int * 'a tree * 'a * 'a tree (* height,
\ R(y) d => B(x) B(z) <= a R(y) / \ / \ / \ / \ R(x) c a b c left child, value, right child *) | Nil
d b R(z) / \ / \ a b c d /\ || B(x) / \ a R(z) / \ R(y) d / \ b c
We can modify our binary tree class as follows:
30.3.2
AVL Trees
96
30.3.3 Heaps
Binary search trees can eciently nd arbitrary elements
in a set, however it can be occasionally useful to access the
minimum element in set. Heaps are special data structure
which satisfy the heap property: the value of every node
is greater than the value of any of its child nodes. Additionally, we can keep the tree approximately balanced
using the leftist property, meaning that the height of any
left child heap is at least as large as its right sibling. We
can hold the height of each tree in each heap node.
Finally, since heaps can be implemented as min- or maxheaps, where the root element will either be the largest or
smallest element in the set, we support both types of heaps
by passing in an ordering function into heaps constructor
as such:
type 'a heap = | EmptyHeap | HeapNode of int * 'a * 'a
heap * 'a heap type 'a BinaryHeap(comparer : 'a -> 'a ->
int, inner : 'a heap) = static member make(comparer) =
BinaryHeap<_>(comparer, EmptyHeap)
97
laziness in ways which make purely functional data structures just as ecient as their imperative counterparts.
For example, its easy to create a stack-like data structure
which delays all computation until its really needed:
type 'a lazyStack = | Node of Lazy<'a * 'a lazyStack> |
EmptyStack module LazyStack = let (|Cons|Nil|) = function | Node(item) -> let hd, tl = item.Force() Cons(hd, tl)
| EmptyStack -> Nil let hd = function | Cons(hd, tl) -> hd |
Nil -> failwith empty let tl = function | Cons(hd, tl) -> tl
| Nil -> failwith empty let cons(hd, tl) = Node(lazy(hd,
tl)) let empty = EmptyStack let rec append x y = match
x with | Cons(hd, tl) -> Node(lazy(printfn appending...
got %A hd; hd, append tl y)) | Nil -> y let rec iter f =
function | Cons(hd, tl) -> f(hd); iter f tl | Nil -> ()
In the example above, the append operation returns one
node delays the rest of the computation, so appending
two lists will occur in constant time. A printfn statement
above has been added to demonstrate that we really don't
compute appended values until the rst time they're accessed:
> open LazyStack;; > let x = cons(1, cons(2, cons(3,
cons(4, EmptyStack))));; val x : int lazyStack =
Node <unevaluated> > let y = cons(5, cons(6, cons(7,
EmptyStack)));; val y : int lazyStack = Node <unevaluated> > let z = append x y;; val z : int lazyStack
= Node <unevaluated> > hd z;; appending... got 1
val it : int = 1 > hd (tl (tl z) );; appending... got 2
appending... got 3 val it : int = 3 > iter (fun x -> printfn
"%i x) z;; 1 2 3 appending... got 4 4 5 6 7 val it : unit = ()
Interestingly, the append method clearly runs in O(1) time
because the actual appending operation is delayed until a
user grabs the head of the list. At the same time, grabbing
the head of the list may have the side eect of triggering,
at most, one call to the append method without causing
a monolithic rebuilding the rest of the data structure, so
grabbing the head is itself an O(1) operation. This stack
implementation supports supports constant-time consing
and appending, and linear time lookups.
This heap implements the IEnumerable<'a> interface, al- Similarly, implementations of lazy queues exists which
lowing us to iterate through it like a seq. In addition to support O(1) worst-case behavior for all operations.
the leftist heap shown above, its very easy to implement
immutable versions of splay heaps, binomial heaps, Fibonacci heaps, pairing heaps, and a variety other tree-like
30.5 Additional Resources
data structures in F#.
Its worth noting that some purely functional data structures above are not as ecient as their imperative implementations. For example, appending two immutable
stacks x and y together takes O(n) time, where n is the
number of elements in stack x. However, we can exploit
98
Chapter 31
Reection
Reection allows programmers to inspect types and in- Version=2.0.0.0,
Culture=neutral,
PublicKeyTovoke methods of objects at runtime without knowing their ken=b77a5c561934e089"; Attributes = AutoLayout,
data type at compile time.
AnsiClass, Class, Public, Abstract, Sealed, BeforeFielAt rst glance, reection seems to go against the spirit dInit; BaseType = System.Object; ContainsGenericPaof ML as it is inherently not type-safe, so typing errors rameters = false; DeclaringMethod = ?; DeclaringType
using reection are not discovered until runtime. How- = null; FullName = System.IO.File"; ...
ever, .NETs typing philosophy is best stated as static typing where possible, dynamic typing when needed, where object.GetType and typeof return an instance of
reection serves to bring in the most desirable behaviors System.Type, which has a variety of useful properties
of dynamic typing into the static typing world. In fact, such as:
dynamic typing can be a huge time saver, often promotes
the design of more expressive APIs, and allows code to be
val Name : string
refactored much further than possible with static typing.
This section is intended as a cursory overview of reection, not a comprehensive tutorial.
Its also possible to get type information without an actual The following program will print out the properties of any
object passed into it:
object using the built-in typeof method:
> typeof<System.IO.File>;; val it : System.Type =
System.IO.File {Assembly = mscorlib, Version=2.0.0.0,
Culture=neutral, PublicKeyToken=b77a5c561934e089;
AssemblyQualiedName = System.IO.File, mscorlib,
99
100
31.2 Microsoft.FSharp.Reection
Namespace
While .NETs built-in reection API is useful, the
F# compiler performs a lot of magic which makes
built-in types like unions, tuples, functions, and other
built-in types appear strange using vanilla reection.
The Microsoft.FSharp.Reection namespace provides a
wrapper for exploring F# types.
open
System.Reection
open
Mi----------- Program+Car WheelCount: 4 Year: 2009 crosoft.FSharp.Reection let explore x = let t =
Model: Focus Make: Ford ----------- Program+Cat x.GetType() if FSharpType.IsTuple(t) then let elds =
Name: Mittens Age: 3
FSharpValue.GetTupleFields(x) |> Array.map string |>
fun strings -> System.String.Join(", ", strings) printfn
Tuple: (%s)" elds elif FSharpType.IsUnion(t) then let
31.1.2 Example: Setting Private Fields
union, elds = FSharpValue.GetUnionFields(x, t) printfn
Union: %s(%A)" union.Name elds else printfn Got
In addition to discovering types, we can dynamically in- another type
voke methods and set properties:
let dynamicSet x propName propValue = let prop- Using fsi:
erty = x.GetType().GetProperty(propName) prop> explore (Some(Hello world));; Union: Some([|"Hello
erty.SetValue(x, propValue, null)
world"|]) val it : unit = () > explore (7, Hello world);;
Tuple: (7, Hello world) val it : unit = () > explore
Reection is particularly remarkable in that it can (Some(Hello world));; Union: Some([|"Hello world"|])
read/write private elds, even on objects which appear val it : unit = () > explore [1;2;3;4];; Union: Cons([|1;
to be immutable. In particular, we can explore and ma- [2; 3; 4]|]) val it : unit = () > explore Hello world";; Got
nipulate the underlying properties of an F# list:
another type
> open System.Reection let x = [1;2;3;4;5] let
lastNode = x.Tail.Tail.Tail.Tail;; val x : int list =
[1; 2; 3; 4; 5] val lastNode : int list = [5] > lastNode.GetType().GetFields(BindingFlags.NonPublic
31.3 Working With Attributes
||| BindingFlags.Instance) |> Array.map (fun eld ->
eld.Name);; val it : string array = [|"__Head"; "__Tail"|]
> let tailField = lastNode.GetType().GetField("__Tail, .NET attributes and reection go hand-in-hand. AtBindingFlags.NonPublic ||| BindingFlags.Instance);; tributes allow programmers to decorate classes, methods,
val
tailField
:
FieldInfo
=
Mi- members, and other source code with metadata used at
crosoft.FSharp.Collections.FSharpList`1[System.Int32] runtime. Many .NET classes use attributes to annotate
__Tail > tailField.SetValue(lastNode, x);; (* circular list code in a variety of ways; it is only possible to access
*) val it : unit = () > x |> Seq.take 20 |> Seq.to_list;; val and interpret attributes through reection. This section
it : int list = [1; 2; 3; 4; 5; 1; 2; 3; 4; 5; 1; 2; 3; 4; 5; 1; 2; will provide a brief overview of attributes. Readers interested in a more complete overview are encouraged to read
3; 4; 5]
MSDNs Extending Metadata With Attributes series.
The example above mutates the list in place and to produce a circularly linked list. In .NET, immutable
doesn't really mean immutable and private members are
mostly an illusion.
Note: The power of reection has denite security implications, but a full discussion of reection security is far outside of the scope of
this section. Readers are encouraged to visit
the Security Considerations for Reection ar-
Attributes are dened using [<AttributeName>], a notation already seen in a variety of places in previous chapters of this book. The .NET framework includes a number of built-in attributes, including:
System.ObsoleteAttribute - used to mark source
code intended to be removed in future versions.
System.FlagsAttribute - indicates that an enumeration can be treated as a bit eld.
101
31.3.1
Chapter 32
Computation Expressions
Computation expressions are easily the most dicult, let read_line() = System.Console.ReadLine() let
yet most powerful language constructs to understand in print_string(s) = printf "%s s print_string Whats your
F#.
name? " let name = read_line() print_string (Hello, " +
name)
Of course, its perfectly reasonable to say what masochistic reason would anyone have for writing code like that?
All it does it print out Hello, Steve to the console! After all, C#, Java, C++, or other languages we know and
love execute code in exactly the order specied -- in other
words, monads solve a problem in Haskell which simply
Monads in Haskell
doesn't exist in imperative languages. Consequently, the
Haskell is interesting because its a functional program- monad design pattern is virtually unknown in imperative
ming language where all statements are executed lazily, languages.
meaning Haskell doesnt compute values until they are ac- However, monads are occasionally useful for modeling
tually needed. While this gives Haskell some unique fea- computations which are dicult to capture in an impertures such as the capacity to dene innite data struc- ative style.
tures, it also makes it hard to reason about the execution
The Maybe Monad
of programs since you can't guarantee that lines of code
A well-known monad, the Maybe monad, represents a
will be executed in any particular order (if at all).
short-circuited computation which should bail out if
Consequently, its quite a challenge to do things which
any part of the computation fails. Using a simple examneed to be executed in a sequence, which includes any
ple, lets say we wanted to write a function which asks the
form of I/O, acquiring locks objects in multithreaded
user for 3 integer inputs between 0 and 100 (inclusive)
code, reading/writing to sockets, and any conceivable ac-- if at any point, the user enters an input which is nontion which has a side-eect on any memory elsewhere in
numeric or falls out of our range, the entire computation
our application. Haskell manages sequential operations
should be aborted. Traditionally, we might represent this
using something called a monad, which can be used to
kind of program using the following:
simulate state in an immutable environment.
let addThreeNumbers() = let getNum msg = printf "%s
Visualizing Monads with F#
msg // NOTE: return values from .Net methods that acTo visualize monads, lets take some everyday F# code cept 'out' parameters are exposed to F# as tuples. match
written in imperative style:
102
103
url msg bind( (fun () -> printMsg Creating webclient..."; new System.Net.WebClient()), fun webclient
-> bind( (fun () -> printMsg Downloading url...";
webclient.DownloadString(url)), fun html -> bind( (fun
() -> printMsg Extracting urls..."; Regex.Matches(html,
@"http://\char"005C\relax{}S+") ), fun matches > printMsg (Found " + matches.Count.ToString()
+ " links) ) ) ) ["http://www.google.com/";
"http://microsoft.com/"; "http://www.wordpress.com/";
"http://www.peta.org"] |> Seq.iter downloadAsync;;
val bind : (unit -> 'a) * ('a -> unit) -> unit val downloadAsync : string -> unit > ThreadID = 5, Url =
http://www.google.com/, Creating webclient... ThreadID = 11, Url = http://microsoft.com/, Creating webclient... ThreadID = 5, Url = http://www.peta.org,
Creating webclient...
ThreadID = 11, Url =
http://www.wordpress.com/,
Creating webclient...
ThreadID = 5, Url = http://microsoft.com/, Downloading url... ThreadID = 11, Url = http://www.google.com/,
Downloading url...
ThreadID = 11, Url =
http://www.peta.org, Downloading url... ThreadID = 13,
Url = http://www.wordpress.com/, Downloading url...
ThreadID = 11, Url = http://www.google.com/, Extracting urls... ThreadID = 11, Url = http://www.google.com/,
Found 21 links ThreadID = 11, Url = http:
//www.peta.org, Extracting urls... ThreadID = 11, Url =
http://www.peta.org, Found 111 links ThreadID = 5, Url
= http://microsoft.com/, Extracting urls... ThreadID = 5,
Url = http://microsoft.com/, Found 1 links ThreadID =
13, Url = http://www.wordpress.com/, Extracting urls...
ThreadID = 13, Url = http://www.wordpress.com/,
Found 132 links
Its interesting to notice that Google starts downloading on
thread 5 and nishes on thread 11. Additionally, thread
11 is shared between Microsoft, Peta, and Google at some
point. Each time we call bind, we pull a thread out of
.NETs threadpool, when the function returns the thread
is released back to the threadpool where another thread
might pick it up again -- its wholly possible for async functions to hop between any number of threads throughout
their lifetime.
This technique is so powerful that its baked into F# liopen System.Threading let bind(input, rest) = Thread- brary in the form of the async workow.
Pool.QueueUserWorkItem(new WaitCallback( fun _ ->
rest(input()) )) |> ignore
104
32.2.1
Syntax Sugar
Chapter 33
Async Workows
Async workows allow programmers to convert singlethreaded code into multi-threaded code with minimal
code changes.
member
Parallel
:
computationList:
seq<Async<'T>> -> Async<'T array>
Specify an asynchronous computation that,
when run, executes all the given asynchronous
computations, initially queueing each in the
thread pool. If any raise an exception then
the overall computation will raise an exception,
and attempt to cancel the others. All the subcomputations belong to an AsyncGroup that is
105
106
open System.Text.RegularExpressions open System.Net let download url = let webclient = new
System.Net.WebClient() webclient.DownloadString(url
: string) let extractLinks html = Regex.Matches(html,
@"http://\char"005C\relax{}S+") let downloadAndExtractLinks url = let links = (url |> download |>
extractLinks) url, links.Count let urls = [@"http:
//www.craigslist.com/";
@"http://www.msn.com/";
@"http://en.wikibooks.org/wiki/Main_Page"; @"http:
//www.wordpress.com/"; @"http://news.google.com/";]
let pmap f l = seq { for a in l -> async { return f
a } } |> Async.Parallel |> Async.Run let testSynchronous() = List.map downloadAndExtractLinks
urls let testAsynchronous() = pmap downloadAndExtractLinks urls let time msg f = let stopwatch =
System.Diagnostics.Stopwatch.StartNew() let temp =
f() stopwatch.Stop() printfn "(%f ms) %s: %A stopwatch.Elapsed.TotalMilliseconds msg temp let main() =
printfn Start... time Synchronous testSynchronous
time Asynchronous testAsynchronous printfn Done.
main()
33.3.1
Parallel Map
Consider the function Seq.map. This function is synchronous, however there is no real reason why it needs
to be synchronous, since each element can be mapped in
parallel (provided we're not sharing any mutable state).
Using a module extension, we can write a parallel version
of Seq.map with minimal eort:
module Seq = let pmap f l = seq { for a in l -> async {
return f a } } |> Async.Parallel |> Async.Run
The code using pmap ran about 2.2x faster because web
pages are downloaded in parallel, rather than serially.
33.4.1
For the rst 50 years of software development, programmers could take comfort in the fact that computer hardware roughly doubled in power every 18 months. If a
program was slow today, one could just wait a few months
and the program would run at double the speed with no
change to the source code. This trend continued well into
the early 2000s, where commodity desktop machines in
2003 had more processing power than the fastest supercomputers in 1993. However, after the publication of a
well-known article, The Free Lunch is Over: A Fundamental Turn Toward Concurrency in Software by Herb
Sutter, processors have peaked at around 3.7 GHz in
2005. The theoretical cap in in computing speed is limited by the speed of light and the laws of physics, and
we've very nearly reached that limit. Since CPU designers are unable to design faster CPUs, they have turned
toward designing processors with multiple cores and better support for multithreading. Programmers no longer
have the luxury of their applications running twice as fast
with improving hardware -- the free lunch is over.
Clockrates are not getting any faster, however the amount
of data businesses process each year grows exponentially
(usually at a rate of 10-20% per year). To meet the
growing processing demands of business, the future of all
software development is tending toward the development
of highly parallel, multithreaded applications which take
advantage of multicores processors, distributed systems,
and cloud computing.
33.4.2
107
108
Programming
Chapter 34
MailboxProcessor
F#'s MailboxProcessor class is essentially a dedicated
message queue running on its own logical thread of control. Any thread can send the MailboxProcessor a message asynchronously or synchronously, allowing threads
to communicate between one another through message
passing. The thread of control is actually a lightweight
simulated thread implemented via asynchronous reactions to messages. This style of message-passing concurrency is inspired by the Erlang programming language.
static
member
Start
:
initial:(MailboxProcessor<'msg> -> Async<unit>)
* ?asyncGroup:AsyncGroup -> MailboxProcessor<'msg>
Create and start an instance of a MailboxProcessor. The asynchronous computation executed by the processor is the one returned by
the 'initial' function.
member Post : message:'msg -> unit
109
110
type msg = | Incr of int | Fetch of AsyncReplyChannel<int> let counter = MailboxProcessor.Start(fun inbox
-> let rec loop n = async { let! msg = inbox.Receive()
match msg with | Incr(x) -> return! loop(n + x) |
Fetch(replyChannel) -> replyChannel.Reply(n) return!
loop(n) } loop 0)
The msg union wraps two types of messages: we
can tell the MailboxProcessor to increment, or have
it send its contents to a reply channel. The type
AsyncReplyChannel<'a> exposes a single method, member Reply : 'reply -> unit. We can use this class in fsi as
follows:
> counter.Post(Incr 7);; val it : unit = () >
counter.Post(Incr 50);; val it :
unit = () >
counter.PostAndReply(fun replyChannel -> Fetch
replyChannel);; val it : int = 57
Notice that PostAndReply is a syncronous method.
34.3.1
Encapsulating MailboxProcessors
with Objects
Often, we don't want to expose the implementation details counter represents an innite list of numbers from
of our classes to consumers. For example, we can re-write n..innity.
the example above as a class which exposes a few select
lter is simply a lter for another MailboxProcessor. Its
methods:
analogous to Seq.lter.
type countMsg = | Die | Incr of int | Fetch of AsyncReplyChannel<int> type counter() = let innerCounter = processor is essentially an iterative lter: we seed our
MailboxProcessor.Start(fun inbox -> let rec loop n = prime list with the rst prime, 2 and a innite list of numasync { let! msg = inbox.Receive() match msg with | Die bers from 3..innity. Each time we process a message,
-> return () | Incr x -> return! loop(n + x) | Fetch(reply) we return the prime number, then replace our innite list
-> reply.Reply(n); return! loop n } loop 0) mem- with a new list which lters out all numbers divisible by
ber this.Incr(x) = innerCounter.Post(Incr x) member our prime. The head of each new ltered list is the next
this.Fetch() = innerCounter.PostAndReply((fun reply prime number.
-> Fetch(reply)), timeout = 2000) member this.Die() = So, the rst time we call Next, we get back a 2 and reinnerCounter.Post(Die)
place our innite list with all numbers not divisible by
two. We call next again, we get back the next prime, 3,
and lter our list again for all numbers divisible by 3. We
call next again, we get back the next prime, 5 (we skip 4
34.4 MailboxProcessor Examples since its divisible by 2), and lter all numbers divisible by
5. This process repeats indenitely. The end result is a
prime number sieve with an identical implementation to
34.4.1 Prime Number Sieve
the Sieve of Eratosthenes.
Rob Pike delivered a fascinating presentation at a Google
TechTalk on the NewSqueak programming language.
NewSqueaks approach to concurrency uses channels,
analogous to MailboxProcessors, for inter-thread communication. Toward the end of the presentation, he
demonstrates how to implement a prime number sieve using these channels. The following is an implementation
of prime number sieve based on Pikes NewSqueak code:
type 'a seqMsg = | Die | Next of AsyncReplyChannel<'a>
type primes() = let counter(init) = MailboxProcessor.Start(fun inbox -> let rec loop n = async { let! msg
Chapter 35
This is a pretty simple query, and while it doesn't demonTransforming input into a well-dened abstract syntax strate everything you can do with the language, its a good
start. We can model everything in this query using the
tree requires (at minimum) two transformations:
following denitions in F#:
1. A lexer uses regular expressions to convert each syn- // Sql.fs type value = | Int of int | Float of oat | String
tactical element from the input into a token, essen- of string type dir = Asc | Desc type op = Eq | Gt | Ge |
Lt | Le // =, >, >=, <, <= type order = string * dir type
tially mapping the input to a stream of tokens.
where = | Cond of (value * op * value) | And of where *
2. A parser reads in a stream of tokens and attempts to where | Or of where * where type joinType = Inner | Left
match tokens to a set of rules, where the end result | Right type join = string * joinType * where option //
maps the token stream to an abstract syntax tree.
table name, join, optional on clause type sqlStatement
= { Table : string; Columns : string list; Joins : join list;
It is certainly possible to write a lexer which generates the Where : where option; OrderBy : order list }
abstract syntax tree directly, but this only works for the
most simplistic grammars. If a grammar contains balanced parentheses or other recursive constructs, optional
tokens, repeating groups of tokens, operator precedence,
or anything which can't be captured by regular expressions, then it is easiest to write a parser in addition to a
lexer.
With F#, it is possible to write custom le formats, domain specic languages, and even full-blown compilers A token is any single identiable element in a grammar.
Lets look at the string we're trying to parse:
for your new language.
111
112
SELECT x, y, z FROM t1 LEFT JOIN t2 INNER JOIN 35.2.3 Step 3: Dening the lexer rules
t3 ON t3.ID = t2.ID WHERE x = 50 AND y = 20
ORDER BY x ASC, y DESC, z
Lexers convert text inputs into a stream of tokens. We
can start with the following boiler plate code:
So far, we have several keywords (by convention, all keywords are uppercase): SELECT, FROM, LEFT, INNER, { // header: any valid F# can appear here. open Lexing
RIGHT, JOIN, ON, WHERE, AND, OR, ORDER, BY, } // regex macros let char = ['a'-'z' 'A'-'Z'] let digit =
['0'-'9'] let int = '-'?digit+ let oat = '-'?digit+ '.' digit+ let
ASC, DESC, and COMMA.
whitespace = [' ' '\t'] let newline = "\n\r | '\n' | '\r' // rules
There are also a few comparison operators: EQ, GT, GE, rule tokenize = parse | whitespace { tokenize lexbuf }
LT, LE.
| newline { lexbuf.EndPos <- lexbuf.EndPos.NextLine;
We also have non-keyword identiers composed of tokenize lexbuf; } | eof { () }
strings and numeric literals. which well represent using
the keyword ID, INT, FLOAT.
This is not real F# code, but rather a special language
Finally, there is one more token, EOF, which indicates used by FsLex.
the end of our input stream.
The let bindings at the top of the le are used to dene
Now we can create a basic parser le for FsYacc, name regular expression macros. eof is a special marker used
to identify the end of a string buer input.
the le SqlParser.fsp:
%{ open Sql %} %token <string> ID %token <int>
INT %token <oat> FLOAT %token AND OR %token
COMMA %token EQ LT LE GT GE %token JOIN
INNER LEFT RIGHT ON %token SELECT FROM
WHERE ORDER BY %token ASC DESC %token EOF
// start %start start %type <string> start %% start: | {
Nothing to see here } %%
rule ... = parse ... denes our lexing function, called tokenize above. Our lexing function consists of a series of
rules, which has two pieces: 1) a regular expression, 2)
an expression to evaluate if the regex matches, such as
returning a token. Text is read from the token stream one
character at a time until it matches a regular expression
and returns a token.
Notice the code between the {'s and }'s consists of plain
old F# code. Also notice we are returning the same tokens (INT, FLOAT, COMMA and EOF) that we dened
in SqlParser.fsp. As you can probably infer, the code lexeme lexbuf returns the string our parser matched. The
tokenize function will be converted into function which
has a return type of SqlParser.token.
We can ll in the rest of the lexer rules fairly easily:
{ open System open SqlParser open Lexing let keywords = [ SELECT, SELECT; FROM, FROM;
WHERE, WHERE; ORDER, ORDER; BY, BY;
JOIN, JOIN; INNER, INNER; LEFT, LEFT;
RIGHT, RIGHT; ASC, ASC; DESC, DESC;
AND, AND; OR, OR; ON, ON; ] |> Map.ofList
let ops = [ "=", EQ; "<", LT; "<=", LE; ">", GT; ">=",
GE; ] |> Map.ofList } let char = ['a'-'z' 'A'-'Z'] let
digit = ['0'-'9'] let int = '-'?digit+ let oat = '-'?digit+
113
record.
The F# code contains "$1, "$2, :$3, etc. which vaguely
resembles regex replace syntax. Each "$#" corresponds
to the index (starting at 1) of the token in our matching
rule. The indexes become obvious when theyre annotated as follows:
(* $1 $2 *) start: SELECT columnList (* $3 $4 *)
FROM ID (* $5 *) joinList (* $6 *) whereClause (*
$7 *) orderByClause (* $8 *) EOF { { Table = $4;
Columns = $2; Joins = $5; Where = $6; OrderBy = $7 } }
So, the start rule breaks our tokens into a basic shape,
which we then use to map to our sqlStatement record.
You're probably wondering where the columnList, joinList, whereClause, and orderByClause come from -these are not tokens, but are rather additional parse rules
To compile this lexer, execute the following code on the which we'll have to dene. Lets start with the rst rule:
commandline: fslex SqlLexer.fsl. (Try adding this le to
your projects Build Events as well.) Then, add the le columnList: | ID { [$1]} | ID COMMA columnList { $1
SqlLexer.fs to the project. We can experiment with the :: $3 }
lexer now with some sample input:
open System open Sql let x = " SELECT x, y, z columnList matches text in the style of a, b, c, ... z
FROM t1 LEFT JOIN t2 INNER JOIN t3 ON t3.ID and returns the results as a list. Notice this rule is dened
= t2.ID WHERE x = 50 AND y = 20 ORDER BY x recursively (also notice the order of rules is not signiASC, y DESC, z " let lexbuf = Lexing.from_string x cant). FsYaccs match algorithm is greedy, meaning it
while not lexbuf.IsPastEndOfStream do printfn "%A will try to match as many tokens as possible. When FsY(SqlLexer.tokenize lexbuf) Console.WriteLine("(press acc receives an ID token, it will match the rst rule, but it
also matches part of the second rule as well. FsYacc then
any key)") Console.ReadKey(true) |> ignore
performs a one-token lookahead: it the next token is a
COMMA, then it will attempt to match additional tokens
This program will print out a list of tokens matched by until the full rule can be satised.
the string above.
Notice we've created a few maps, one for keywords and
one for operators. While we certainly can dene these as
rules in our lexer, its generally recommended to have a
very small number of rules to avoid a state explosion.
35.2.4
A parser converts a stream of tokens into an abstract syntax tree. We can modify our boilerplate parser as follows
(will not compile):
114
35.2.5
Step 5:
gether
115
=
=
to
Thanks
If you get the message that some module doesn't exist or
2011-07-08 (Sjuul Janssen) Contact me through my
that some module is declared multiple times. Make sure
github account. I'm working on this and some other stu.
that in the solution explorer the les come in this order:
Sql.fs
SqlParser.fsp
SqlLexer.fsl
SqlParser.fsi
SqlParser.fs
SqlLexer.fs
Program.fs
If
you
get
the
message
Method
not
found:
'System.Object
Microsoft.FSharp.Text.Parsing.Tables`1.Interpret(Microsoft.FSharp.Core.FSharpFunc`2<Microsoft.FSharp.Text.Lexing.LexBuer`1<By
... Go to http://www.microsoft.com/download/en/
details.aspx?id=15834 and reinstall Visual Studio 2010
F# 2.0 Runtime SP1 (choose for repair)
2011-07-06: (mkdu) Could someone please provide a
sample project. I have followed all of your changes but
still can not build. Thanks.
116
Text
117
35.3.2
Images
File:Data_stack.svg Source: https://upload.wikimedia.org/wikipedia/commons/2/29/Data_stack.svg License: Public domain Contributors: made in Inkscape, by myself User:Boivie. Based on Image:Stack-sv.png, originally uploaded to the Swedish Wikipedia in 2004 by
sv:User:Shrimp Original artist: User:Boivie
File:Queue_algorithmn.jpg Source: https://upload.wikimedia.org/wikipedia/commons/4/45/Queue_algorithmn.jpg License: Public domain Contributors: Own work Original artist: Leon22
File:Red-black_tree_example.svg Source: https://upload.wikimedia.org/wikipedia/commons/6/66/Red-black_tree_example.svg License: CC-BY-SA-3.0 Contributors: This vector image was created with Inkscape. Original artist: en:User:Cburnett
File:Symbol_thumbs_down.svg Source: https://upload.wikimedia.org/wikipedia/commons/8/84/Symbol_thumbs_down.svg License:
Public domain Contributors: ? Original artist: ?
File:Symbol_thumbs_up.svg Source: https://upload.wikimedia.org/wikipedia/commons/8/87/Symbol_thumbs_up.svg License: Public
domain Contributors: Own work Original artist: Pratheepps (talk contribs)
35.3.3
Content license