CATEGORII DOCUMENTE 
loading...

Introducing Functional Programming
F# programming is effective and productive primarily because it is built on the tried and tested foundational constructs of functional programming, in particular the programming paradigm of the ML and Caml family of languages. In this chapter we look at some of the core building blocks of F# programming, particularly with regard to simple data types and function values. Imperative programming, type definitions, generics and objectoriented programming are covered in Chapters 4 to 7.


We first take a look at the most common base types of data manipulated in F# code. We begin with the basics of F# arithmetic.
The table below shows the most common basic types used in F# code and their corresponding literal forms. Many additional types are defined in the .NET libraries.
Arithmetic types and literals
Type Description Sample Literals .NET name
bool true/false values true, false System.Boolean
byte 8bit unsigned integers 0uy, 19uy, 0xFFuy System.Byte
sbyte 8bit signed integers 0y, 19y, 0xFFy System.SByte
int16 16bit signed integers 0s, 19s, 0x0800s System.Int16
uint16 16bit unsigned integers 0us, 19us, 0x0800us System.UInt16
int, int32 32bit signed integers , 19l[DS1] , 0x0800, 0b0001 System.Int32
uint32 32bit unsigned integers 0ul, 19ul, 0x0800ul[DS2] System.UInt32
int64 64bit signed integers 0L, 19L, 0x0800L System.Int64
uint64 64bit unsigned integers 0UL, 19UL, 0x0800UL System.UInt64
single, float32 32bit IEEE floatingpoint 0.0f, 19.7f, 1.3e4f System.Single
double, float 64bit IEEE floatingpoint , , 1.3e4 System.Double
decimal Highprecision decimal values 0M, 19M, 19.03M[DS3] System.Decimal
bigint Arbitrarily large integers 0I, 19I Math.BigInt
bignum Arbitrary precision rationals 0N, 19N Math.BigNum
A number of operators are by default overloaded to work over multiple types, including userdefined types. Operators may also be redefined to only work over specific types, by replacing the definition that gives the operator the status of an overloaded operator. See Chapter 6 – Type Definitions, Classes and Objects for a description of how to define new instances of overloads for new type definitions. The most commonly used default arithmetic operators are shown below.
Arithmetic operators and examples
Operator Description Sample Use on int Sample Use on float
Unchecked Addition
Unchecked Subtraction
Unchecked Multiplication
Division 5.0 / 2.0
Modulus 5.4 % 2.0
Unary Negation (5.4+2.4)
In F# addition, subtraction and multiplication over integers are unchecked, that is if overflow or underflow occurs beyond the representable range then wraparound occurs. For example, is the largest representable 32bit integer of the int type:
> 2147483647+1;;
val it : int = 2147483648
Checked versions of these that raise System.Overflow
exceptions can be accessed by opening the Microsoft.FSharp.Operators.Checked [DS4] module,
and if detecting overflow is a priority then the use of the decimal, bigint or bignum types is
recommended. Division by zero raises a System.DivideByZeroException,
except in the case of floating point numbers where it returns a
Operator overloading interacts with type inference — if any particular use of an overloaded operator is not otherwise constrained to work on any particular type then F# will assume it works on 32bit integers. To constrain a particular use of an operator to a particular numeric type you must give a type annotation that has the effect of telling the compiler the lefthand type of the two arguments to the binary operator. For example, in the absence of additional type information the following function is assumed to work over integers:
> let doubleAndAdd a b = a * a + b;;
val doubleAndAdd: int > int > int
A single type annotation on a is sufficient to indicate that a*a is an operation on float values, and thus returns a float value, and thus that a*a+b is also an operation on float values.
> let doubleAndAdd (a:float) b = a * a + b;;
val doubleAndAdd: float > float > float
However asymmetric type constraints of this form are not always considered good style, and in some situations involving overloaded operators it will be simplest to give the full type annotations for the arguments and return type of a value:
> let doubleAndAdd (a:float) (b:float) : float = a * a + b;;
val doubleAndAdd: float > float > float
The integer types support bitwise manipulations on their underlying representations. The most commonly used default bitwise manipulation operators are shown in the table below.
Bitwise arithmetic operators and examples
Operator Description Sample Use Result
&&& Bitwise And 0x65 &&& 0x0F 0x05
Bitwise Or 0x65  0x18 0x7D
Bitwise Exclusive Or 0x65 ˆˆˆ 0x0F 0x6A
Bitwise Negation ~~~0x65 0xFFFFFF9a
<<< Left shift 0x01 <<< 3 0x08
>>> Right shift (arithmetic if signed) 0x65 >>> 3 0x0C
The following sample shows the use of these operators to encode 32bit integers into 1, 2 or 5 bytes, represented by returning a list of integers. Input integers in the range 0 to 127 return a list of length one.
let encode (n: uint32) =
if (n >= 0 && n <= 0x7F) then [ n ]
elif (n >= 0x80 && n <= 0x3FFF) then [ (0x80  (n >>> 8)) &&& 0xFF;
(n &&& 0xFF) ]
else [ 0xC0; ((n >>> 24) &&& 0xFF);
((n >>> 16) &&& 0xFF);
((n >>> 8) &&& 0xFF);
(n &&& 0xFF) ]
Here is an example of the function in action:
> encode 32;;
val it : int32 list = [32]
> encode 320;;
val it : int32 list = [129; 64]
> encode 32000;;
val it : int32 list = [192; 0; 0; 125; 0]
Numeric types are not implicitly converted — all conversions between different numeric types must be made explicitly. Some conversion operators are shown in the table below. Often there are multiple equivalent ways of achieving the same conversion.
Basic arithmetic conversions and examples
Operator Type Sample Use Sample Synonyms
Float.of_int int > float Float.of_int 0x65 Int32.to_float, float
Int32.of_float float > int Int32.of_float 128.4 Float.to_int, truncate
Byte.of_int int > byte Byte.of_int 0x65 Int32.to_byte
Int32.of_byte byte > int Int32.of_byte 0x65y Byte.to_int
These conversions are all unchecked, in the sense that they will not raise exceptions. An alternative is to use the .NET static methods contained in the type System.Convert, e.g. System.Convert.ToDouble( ). As with many .NET constructs, uses of System.Convert methods may require type annotations to resolve overloading, discussed in detail in Chapter 5. In addition, these operators are checked and will raise an exception if the source number can’t be represented within the numeric range of the target type.
When used with numeric data the binary comparison operators , <>, <, <=, >, >=, min and max perform comparisons according to the natural ordering for each particular numeric type. These operators can also be used on structured data types, e.g. to compare lists of integers, and their behaviour can be customized for new types that you define. This topic is discussed in Chapter 8.
When used on floating point values these operators implement
the IEEE semantics for
The F# type string is an abbreviation for the.NET Framework type System.String and represents a sequence of Unicode UTF16 characters. More details on Unicode can be found in the many excellent guides on the Web. In this section we briefly introduce strings and the most useful sets of functions for formatting them.
String literals are written using the forms shown in the table below.
String and character literals
Example Kind Type
'Humpty Dumpty' string string
'c:Program Files' string string
@'c:Program Files' verbatim string string
'xyZy3d2'B literal byte string byte[]
'c' character char
As shown in the table a literal form is also available for interpreting sequences of characters as arrays of bytes.
The escape codes that may be used in strings and characters are shown in the table below.
Escape characters in nonverbatim strings
Escape Character ASCII/Unicode Value Examples
n New Line 10 'n'
r Carriage Return 13 'r'
t TAB 9 't'
b Backspace 8
NNN Trigraph NNN (space)
uNNNN Unicode character NNNN 'u00a9' (©)
UNNNNNNNN Long unicode character NNNN NNNN 'U00002260' (≠)
Verbatim strings are particularly useful for file and path names that contain the escape character “ ”. Multiline string literals may also be used, e.g.
let s = 'All the kings horses
and all the kings men”;;
val s : string = 'All the kings horsesnand all the kings men';;
Strings are immutable, i.e. the contents of a string value may not be modified once created. The operator is used to access the elements of a string, and the property .Length retrieves its length:
> let s = 'Couldn't put Humpty';;
val s : string = 'Couldn't put Humpty'
> s.Length;;
val it : int = 19
> s.[13];;
val it : char = 'H'
The simplest way to build strings is via concatenation, using the + operator:
> let s = 'Couldn't put Humpty' + ' ' + 'together again”;;
val s : string = 'Couldn't put Humpty together again'
Strings can also be built using objects of the .NET type System.Text.StringBuilder. These objects are mutable buffers that can be used to accumulate and modify text. An example is shown below.
> let buf = new System.Text.StringBuilder();;
val buf : System.Text.StringBuilder
> buf.Append('Humpty Dumpty');;
> buf.Append(' sat on the wall');;
> let s = buf.ToString();;
val s : string = 'Humpty Dumpty sat on the wall'
One of the most important tools in F# programming is “pattern matching”, a very general construct that combines decomposition and control. In the previous sections we had a taste for how pattern matching can be used with tuple values. However, pattern matching can also be used in many other situations. We’ll see many other examples of pattern matching in this book, but we’ll begin with some simple pattern matching over strings and integers. Pattern matches on explicit values are introduced using the match with construct:
let urlFilter url agent =
match (url,agent) with
 'https://www.control.org', 99 > true
 'https://www.kaos.org' , _ > false
 _, 86 > true
 _ > false
The inferred type of the function is:
val urlFilter: string > int > bool
The expression after match is evaluated to a tuple value, and the “rules” of the match are used to choose a result expression. Each rule of the match is introduced with a , though the first is optional. The first rule of the match will succeed if url and agent are 'https://www.control.org' and respectively. The last three rules all make use of “wildcard” patterns represented by the underscore character – these match all inputs.
The overall conditions under which urlFilter returns true can be read off simply by reading through the pattern match, e.g. agent 99 may access 'https://www.control.org', no one may access 'https://www.kaos.org', and, excluding the latter agent 86 may access anything.
Pattern matching can also decompose values. Here is an example where we match nested tuple values:
let highLow a b =
match (a,b) with
 ('lo', lo), ('hi', hi) > (lo,hi)
 ('hi', hi), ('lo', lo) > (lo,hi)
 _ > failwith 'expected a both a high and low value';;
The match examines two pairs and looks at the strings in the first element of each, returning the associated values.
> highLow ('hi',300) ('lo',100);;
val it : (int * int) = (100,300)
The first rule decomposes the list according to the case where the first parts of the pairs are the strings 'lo' and 'hi' respectively. It then returns a pair made from the respective second parts of the tuples. The second rule is the mirror of this in case the values appeared in reverse order.
The final cases of both of the above examples use wildcard patterns to cover remaining cases. This makes the patterns “exhaustive”. Frequently no wildcard is needed to ensure this, as for many input types F# is able to determine if the given set of rules is sufficient to cover all possibilities for the given shape of data. However, if a match is not exhaustive a warning is given, e.g.
> let urlFilter3 url agent =
match url,agent with
 'https://www.control.org', 86 > true
 'https://www.kaos.org', _ > false;;
match url,agent with
warning: Incomplete pattern match. For example, the value 'a',1 will never match any rule.[DS5]
In these cases it may be necessary to add an extra exceptionthrowing clause to indicate to the F# compiler that the given inputs are not expected, e.g.
match url,agent with
 'https://www.control.org', 86 > true
 'https://www.kaos.org', _ > false;;
 _ > failwith 'unexpected input'
Nonexhaustive matches are automatically augmented by a default case is added where a MatchFailureException is thrown (exceptions are discussed in Section EXN).
F# is also frequently able to determine if pattern matching rules are redundant, i.e.if a rule may never be selected because previous rules subsume all such cases. In this case a warning is given. For example:
> let urlFilter2 url agent =
match url,agent with
 'https://www.control.org', _ > true
 'https://www.control.org', 86 > true
 _ > false;;
 'https://www.control.org', 86 > true
warning: This rule will never be matched.
Individual pattern clauses can be guarded by a condition that is executed if the pattern itself succeeds. Here is a very simple use of this mechanism to records the three clauses for computing the sign of an integer:
let sign x =
match x with
 _ when x < 0 > 1
 _ when x > 0 > 1
 _ > 0
Two patterns may be combined to represent two possible paths for matching:
let getValue a =
match a with
 (('lo'  'low') ,v) > v
 ('hi',v)  ('high',v) > v
 _ > failwith 'expected a both a high and low value';;
Here the pattern ('lo'  'low') matches either string. The pattern ('hi',v)  ('high',v) plays essentially the same role by matching pairs values where the left of the pair is 'hi' or 'high' and binding the value v on either side of the pattern.
Note: Individual patterns may not bind the same variables twice. For example, a pattern “(x,x)” is not permitted. Each side of an “or” pattern must bind the same set of variables.
Some of the foundational data structures of F# coding are tuples, lists and options. In this section we discuss these and some related topics by example.
F# lists are a common data structures used in foundational F# programming. We have seen some examples of concrete lists when using the String.split function in Code Sample CODEWORDCOUNT. The following table shows the primitive constructs for building lists:
List related language constructs
Operator Description Examples
The empty list
A list value
’Cons’ an element with an existing list
Concatenate two lists
Some basic list values are shown below:
let oddPrimes = [3;5;7;11]
let morePrimes = [13;17]
let primes = 2 :: (oddPrimes @ morePrimes)
F# Interactive shows the value of primes as follows:
val primes : int list = [2;3;5;7;11;13;17]
It is important to note that lists are immutable: the “cons” and “append” operations do not modify the original lists, instead they create new lists. This can be seen in the following interactive session:
> let people = [ 'Adam'; 'Dominic'; 'James' ];;
val people : string list = [ 'Adam'; 'Dominic'; 'James' ];;
> 'Chris' :: people;;
val it : string list = [ 'Chris'; 'Adam'; 'Dominic'; 'James' ];;
> people;;
val people : string list = [ 'Adam'; 'Dominic'; 'James' ];;
Note that people has not been changed by the second line – lists and tuples are unchangeable, immutable values. Immutable values bring many advantages. At first it might seem strange to define values that you can’t change. However, knowing that these don’t change means that you rarely need to think about the “object identity” of these values – you can pass them to routines and know they won’t be mutated, and you can pass them between multiple threads without worrying about unsafe concurrent access to the values.
As with tuples, you can decompose lists from the head downwards using pattern matching. Here is an example:
let printFirst primes =
match primes with
 h :: t > printf 'The first prime in the list is %dn' h
 [] > printf 'No primes found in the listn'
> printFirst oddPrimes;;
The first prime in the list is 3
This code examines the head of the primes list, considering the case where primes is an empty list. Note that the and symbols can be used both to build up lists in expressions and to decompose them in pattern matching. This applies to many data structures in F# programming.
The F# library also includes a module List that contains some useful values related to programming with lists. We’ll be seeing many of these functions in the next section and throughout this book. Some of these are shown in Fig. 3.1.
F# lists are represented in memory as linked lists, and each F# list value is either a ’cons’ cell containing a value plus a pointer to the next chain in the list, or else it is a null pointer. When you create a new list using the tail of the new list will point to the old list, which ensures that the inner memory associated with lists is often reused as a part of multiple list values.
F# lists are not appropriate for all circumstances: e.g. very large data structures should probably be represented using arrays or other data structures, or even managed by an external tool such as a relational database. A number of listlike data structures are discussed in the panel below.
Figure 3.1: Some Sample Functions in the List Module
module List
val hd : 'a list > 'a
val tl : 'a list > 'a list
val map : ('a > 'b ) > 'a list > 'b list
val filter : ('a > bool) > 'a list > 'a list
val iter : ('a > unit) > 'a list > unit
val to_array : 'a list > 'a[]
val of_array : 'a[] > 'a list
SOME common DATA STRUCTURES
F# lists are simple, but are just one of a number of important data structures that are available with F#. Data structures are generally divided between mutable and immutable, a distinction covered in more detail in Chapter 4. Here are some of the immutable data structures commonly used with F#:
* 'a list, Immutable linked lists. Cheap to add and access data from one end. Inefficient for random access lookup. Full name Microsoft.FSharp.Collections.List <'a>.
* Microsoft.FSharp.Collections.Set<'a>, Immutable sets based on balanced trees. Cheap to add, access and union, with log(N) access time. Internal nodes can be shared between different sets.
* Microsoft.FSharp.Collections.Map<'key,'value >, Immutable maps based on balanced trees. Cheap to add and access, with log(N) access time. Internal nodes can be shared between different maps.
Chapter 4 includes several examples showing how to use mutable data structures. Some of the important mutable data structures are:
* 'a[]. Mutable, fixed size 1dimensional arrays, intrinsic to .NET. Also written 'a array. Constanttime access
* 'a[,]. Mutable, fixed size 2dimensional arrays, intrinsic to .NET. Constanttime access
* System.Collections.Generic.Dictionary<'key,'value>. Mutable hash tables. Near constanttime access. See Chapter 4 for more details.
* Microsoft.FSharp.Collections.HashSet<'a>. Mutable hash sets. Near constanttime access.
* ResizeArray<'a>. Mutable, autoresizing arrays. Constanttime access. Full name System.Collections.Generic.List<'a>, but generally referred to by the type abbreviation ResizeArray<_> in F#. See Chapter 4 for examples.
There is one name clash between the commonly used mutable and immutable collections: the types Microsoft.FSharp.Collections.List<'a> and System.Collections.Generic.List<'a> both have short name “List<'a>” but are actually immutable linked lists and expanding arrays respectively. These types are very different and live in different namespaces. In general F# code uses lowercase abbreviation 'a list for the former and ResizeArray<'a> for the latter. Operations for these are in the modules Microsoft.FSharp.Collections.List and Microsoft.FSharp.Collections.ResizeArray respectively, accessed via simple paths such as List.map, List.iter, ResizeArray.map and ResizeArray.iter.
Like lists and tuples, option values are simple constructs frequently used as a workhorse in F# coding. An option is simply either a value, Some(v), or the absence of a value, None. For example, options are extremely useful for returning the value of a search where you might or might not have a result. Here’s a data structure that uses options to represent the (optional) parents of some wellknown characters:
> let people = [ ('Adam', None);
('Eve' , None);
('Cain', Some('Adam','Eve'));
('Abel', Some('Adam','Eve')) ];;
val people : (string * (string *string) option) list
Pattern matching is very frequently used with option values:
> let showParents (nm,parents) =
match parents with
 Some(dad,mum) > printf '%s has father is %s, mother %sn” nm dad mum
 None > printf '%s has no parents!n' nm;;
val showParents : (string * (string * string) option) > unit
> showParents ('Adam',None);;
Adam has no parents
The F# library also includes a module Option that contains some useful values related to programming with options. Some of these are shown in Fig. 3.2. While it is easy to code these by hand using pattern matching it can also be useful to learn and rely on the standard definitions.
Figure 3.2: Some Sample Functions in the Option Module
module Option
val get : 'a option > 'a
val is_some : 'a option > bool
val map : ('a > 'b ) > 'a option > 'b option
val iter : ('a > unit) > 'a option > unit
Option values can be used for both data and control, and are often used to represent the success or failure of a computation. This can be useful when catching an exception, e.g.
let res =
try
Some(http('https://www.nature.com'))
with _ >
None
Exceptions are described in more detail in Chapter 4 – what matters here is that if an unexpected problem occurs during the HTTP request then the exception will be caught and the result of the expression will be the value None. Successful webpage requests will return a Some value. Option values may then be discriminated and decomposed using pattern matching, as shown below:
let fetch url =
try Some(http(url))
with _ > None
Here is an example where we use the function:
match (fetch 'https://www.nature.com') with
 Some(res) > printf 'text = %sn' text
 None > printf '**** no web page foundn';;
text = '<HTML> </HTML>' (note: the HTML of the web page will be shown here)
As it happens fetch is a somewhat dangerous function, as it catches all exceptions. Catching particular exceptions related to web requests has been discussed in Chapter 2.
A basic control construct in F# programming is if/then/elif/else. Here’s an example:
let round x =
if x >= 100 then 100
elif x < 0 then 0
else x
Conditionals are really shorthand for pattern matching, e.g. the above could have been written:
let round x =
match () with
 _ when x >= 100 > 100
 _ when x < 0 > 0
 _ > x
Conditionals are always guarded by a booleanvalued expression. These can be built using the && and (the “and” and “or” operators) as well any library functions that return boolean values.
let round2 (x,y) =
if x >= 100  y >= 100 then 100,100
elif x < 0  y < 0 then 0,0
else x,y
&& and are special values that only evaluate the second argument if needed.
Note: If you don’t use the #light lightweight syntax option, then when you combine conditionals with imperative code you need to use parentheses … or begin/end to delimit the regions covered by each branch of the conditional, e.g. if x > 100 then (… . If you use the #light syntax then these are optional, as long as the branches are correctly indented from the if, elif and else tokens of the construct.
One of the fundamental building blocks of computation in F# is recursion. The following code shows a simple wellknown recursive function:
> let rec factorial n = if n <= 1 then 1 else n * factorial (n1);;
val factorial : int > int
> factorial 5;;
val it : int = 120
This example shows that a recursive function is simply one that can call itself as part of its own definition. Recursive functions are introduced by let rec. Functions are not recursive by default, since it is wise to minimize the size of a recursive collection of functions to aid with maintainability. It may help to visualize the execution of factorial 5 in the following way (though note that in reality F# executes the function using efficient native code):
factorial 5
= 5 * factorial 4
= 5 * (4 * factorial 3)
= 5 * (4 * (3 * factorial 2))
= 5 * (4 * (3 * (2 * factorial 1 )))
= 5 * (4 * (3 * (2 * 1)))
= 5 * (4 * (3 * 2))
= 5 * (4 * 6)
= 5 * 24
= 120
As with all calls, the execution of the currently executing instance of the function is effectively suspended while the recursive call is made.
Many of the operators we have so far encountered can be coded as recursive functions. For example, the following is one possible implementation of List.map:
let rec map f l =
match l with
 [] > []
 h :: t > f h :: map f t
Likewise, many functions such as List.length are implemented using recursive functions.
Recursion is sometimes used as a means of programming particular patterns of control. This is usually used in contexts where functions have deliberate side effects. For example, the following code repeatedly fetches the HTML for a particular web page, printing each time it is fetched:
let rec repeatFetch url n =
if n > 0 then
let html = http url
printf 'fetched <<< %s >>> on iteration %dn' html n
repeatFetch (n1)
Note: explicit recursion is an essential technique that should be learnt, but generally avoided if good alternatives are available. It is often sensible to factor recurring patterns of recursive functions into operators of a similar kind to List.map.
Recursion is powerful, but not always the ideal way to encode either data manipulations or control constructs, at least if other techniques are readily available. For example, the above program could be implemented using a for loop, as explained in the next section, which would be clearer. A typical error with recursion is to forget to decrement a variable at the recursive call. For example, the author incorrectly entered the following nonterminating function when writing this chapter:
let rec badFactorial n = if n <= 0 then 1 else n * badFactorial n
Multiple interrelated recursive functions can be defined simultaneously by separating the definitions with and. For example:
let rec even n = (n = 0) or not(odd(n1))
and odd n = not(even(n1))
Care must sometimes be taken with recursive functions to ensure that they are “tailrecursive”, or else the computation stack of your program may be exhausted. Indeed, the implementation of map above is not tailrecursive. This is discussed further in “Managing Resources”, Chapter 8.
In this section we take a look at the next foundational building block of F# programming: function values. We begin by a simple and well known example: using function values to transform one list into another.
One of the primary uses of F# lists is as a generalpurpose concrete data structure for storing ordered sets of inputs and ordered results. Input sets are often transformed to output sets using “aggregate” operations that transform, select, filter and categorize elements of the list according to a range of criteria. These aggregate operations provide an excellent introduction to the use of function values. Let’s take a closer look at this in the following code sample, which continues on from the definition of http in code sample HTTPCODE.
> let sites = [ 'https://www.live.com';
'https://www.google.com' ];;
val sites : string list = ['https://www.live.com'; 'https://www.google.com' ]
> let fetch url = (url, http url);;
val fetch : string > string * string
> let resultsOfFetch = List.map fetch sites;;
val resultsOfFetch: (string * string) list
= [ ('https://www.live.com', '<html></html>');
('https://www.google.com', '<html></html>'); ]
The first definition is a literal list of URLs. The second line calls the aggregate operation List.map. This accepts the “function value” fetch as the first argument and a list as the second argument, applying fetch to each element of the list and collecting up the results in a new list.
Types are one useful way to help learn what a function does. Here’s the type of List.map:
> List.map;;
val it: ('a > 'b) > 'a list > 'b list
This says that List.map accepts a function value as the first argument and a list as the second argument, and returns a list as the result. The function argument can have any type 'a > 'b, and the list must have a corresponding type 'b. The symbols 'a and 'b are called “type parameters” or “type variables”, and functions that involve type variables are called “generic” or “polymorphic”. Type parameters are discussed in detail in the next section.
Function values are so common in F# programming that it is very convenient to define them without giving them names. Here is a very simple example:
> let primes = [2;3;5;7];;
val primes : int list = [2;3;5;7]
> let primeCubes = List.map (fun n > n * n * n) primes;;
val primeCubes : int list = [8;27;125;343]
The definition of primeCubes uses the “anonymous function” (fun n > n * n * n). These are similar to function definitions but are unnamed and appear as an expression rather than as a let declaration. fun is a keyword meaning “function”, n represents the argument to the function, and n*n*n is the result of the function. The overall type of the anonymous function expression is int > int. We could have this technique to avoid defining the intermediary function fetch in the sample above.
let resultsOfFetch = List.map (fun url > (url, http url)) sites
We will see anonymous functions throughout this book. Here is another example:
> let sizes = List.map (fun (_,p) > String.length p) resultsOfFetch;;
val sizes : int list = [3932; 2827 ]
Here we see two things:
* The argument of the anonymous function is a tuple pattern. The use of a tuple pattern automatically extracts the second element from each tuple and gives it the name p within the body of the anonymous function.
* Part of the tuple pattern is a “wildcard” pattern, indicated by an underscore. This indicates that we don’t care what the first part of the tuple is, given we are only interested in extracting the length from the second part of the pair.
Functions such as List.map are called “aggregate operators”, and they are powerful constructs, especially when combined with the other features of F#. Here is a longer example where we use the aggregate operators List.filter and List.map to count the number of URLlinks in each of three wellknown web pages, and then collect stats on a group of pages:
let delimiters = [ ' '; 'n'; 't'; '<'; '>'; '=' ]
let getWords s = String.split delimiters s
let stats site =
let url = 'https://' + site
let html = http url
let hwords = html > getWords
let hrefs = html > getWords > List.filter (fun s > s = 'href')
(site,html.Length, hwords.Length, hrefs.Length)
> let sites = [ 'www.live.com';'www.google.com';'search.yahoo.com' ];;
> sites > List.map stats;;
val it : (string * int * int * int) list
= [('www.live.com', 7728, 1156, 10);
('www.google.com', 2685, 496, 14);
('search.yahoo.com', 10715, 1771, 38)]
The stats function generates the length of the html for the given website, the number of words in the text of that HTML, and the approximate number of links on that page.
The above code sample makes extensive use of the > operator to “pipeline” operations. The F# library design ensures that a common, consistent set of aggregate operations is defined for each structured type. Figure 3.3 shows how the same design patterns occur for many different abstractions.
Figure 3.3: A Recurring Aggregate Operator Design Pattern from the F# Library
Operator Type
List.map ('a > 'b) > 'a list > 'b list
Array.map ('a > 'b) > 'a[] > 'b[]
Option.map ('a > 'b) > 'a option > 'b option
Seq.map ('a > 'b) > #seq<'a> > seq<'b>
PIPELINING WITH >[DS6] AND >>
The > operator is perhaps the most important operator you use in your F# programming. Its definition is deceptively simple:
let (>) x f = f x
Here is a use of the operator to compute the cubes of three numbers:
[1;2;3] > List.map (fun x > x * x * x)
This produces , just as if we’d written:
List.map (fun x > x * x * x) [1;2;3]
In a sense > is just “function application in reverse”. However, the use of > often has distinct advantages:
* Clarity. When used in conjunction with welldesigned libraries, the > operator allows us to perform the data transformations and iterations in a forwardchaining, pipelined style.
* Type inference. The use of the > operator allows type information to be flowed from input objects through to the functions manipulating those objects. F# uses information collected from type inference to resolve some language constructs such as property accesses and method overloading. This relies on information being propagated lefttoright through the text of a program. In particular, typing information to the right of a position is not taken into account when resolving property access and overloads.
For completeness, here is the type of the operator:
val (>) : ’a > (’a > ’b) > ’b
Above we saw how the operator > can be used to “pipe” values through a number of functions. This was a small example of the process of “computing with functions”, and essential and powerful programming technique in F#. In this section we look at ways to compute new function values from existing ones using compositional techniques. First we look at function composition, which is one of the simplest ways of generating new values from old. For example, consider the following code:
google > getWords > List.filter (fun s > s = 'href') > List.length;;
We can rewrite this code using function composition as follows:
let countLinks = getWords >> List.filter (fun s > s = 'href') >> List.length;;
google > countLinks;;
Let’s take a look at this more closely. We have defined countLinks as the composition of three function values using the operator >>. This operator is defined in the F# library as follows:
let (>>) f g x = g(f(x))
We can see from the definition that f >> g gives a function value that first applies f to the x and then applies g. Here is the type of >>:
val (>>) : ('a > 'b) > ('b > 'c) > 'a > 'c
Note that >> is typically applied to only two arguments — those on either side of the binary operator, here named f and g. The final argument x is typically supplied at a later point. F# is very good at optimizing basic constructions of pipelines and composition sequences from functions — for example, the function countLinks above will become a single function calling the three functions in the pipeline in sequence. This means sequences of compositions can be used with relatively low overhead.
Composing functions is just one way to compute interesting new functions. Another useful way is through the use of “partial application”. Here’s an example:
let shift (dx,dy) (px,py) = (px + dx, py + dy)
let shiftRight = shift (1,0)
let shiftUp = shift (0,1)
let shiftLeft = shift (1,0)
let shiftDown = shift (0,1)
The last four functions have been defined by calling shift with only one argument, in each case leaving a residue function that expects an additional argument. F# Interactive will report the types as:
val shift : (int * int) > (int * int) > (int * int)
val shiftRight : (int * int) > (int * int)
val shiftLeft : (int * int) > (int * int)
val shiftUp : (int * int) > (int * int)
val shiftDown : (int * int) > (int * int)
Here is an example of the use shiftRight, and also the use of an inline application of shift to new arguments :
> shiftRight (10,10);;
val it : (int * int) = (11,10)
> List.map (shift (2,2)) [ (0,0); (1,0); (1,1); (0,1) ];;
val it : (int * int) list = [ (2,2); (3,2); (3,3); (2,3) ]
Partial application is one way in which functions can be “computed”, rather than simply being defined. This technique becomes very powerful when combined with additional local definitions. Here’s a simple and practical example, representing an idiom common in graphics programming:
open System.Drawing;;
let remap (r1: Rectangle) (r2: Rectangle) =
let scalex = float r2.Width / float r1.Width
let scaley = float r2.Height / float r1.Height
let mapx x = r2.Left + truncate (float (x  r1.Left) * scalex)
let mapy y = r2.Top + truncate (float (y  r1.Top) * scaley)
let mapp (p: Point) = new Point(mapx p.X, mapy p.Y)
mapp
The function remap computes a new function value mapp that maps points in one rectangle to points in another. F# Interactive will report the type as:
val remap : Rectangle > Rectangle > (Point > Point)
The type Rectangle is defined in the .NET library System.Drawing.dll and represents rectangles specified by integer coordinates. The computations on the interior of the transformation are performed in floating point to improve precision. We can use this as follows:
> let mapp = remap (new Rectangle(100,100,100,100)) (new Rectangle(50,50,200,200));;
val mapp : Point > Point
> mapp (new Point(100,100));;
val it : Point = X=50,Y=50
> mapp (new Point(150,150));;
val it : Point = X=150,Y=150
> mapp (new Point(200,200));;
val it : Point = X=250,Y=250
The intermediate values scalex and scaley are only computed once. This is despite the fact that we’ve called the resulting function mapp three times. It may be helpful to think of mapp as a function object being generated by the remap function.
In the above sample: mapx, mapy and mapp are “local functions”, i.e. functions defined locally as part of the implementation of remap. Local functions can be contextdependent, i.e. they can be defined in terms of any values and parameters that happen to be in scope. Here mapx is defined in terms of scalex, scaley, r1 and r2. Local functions are, if necessary, implemented by taking the “closure” of the variables they depend upon and storing them away until needed. In optimized F# code the F# compiler often avoids this implementation and intead passes extra arguments.
Many useful “abstract” values can be modeled via function types and values. For example:
* The type unit > unit is frequently used to model “actions”, i.e. operations that run and perform some unspecified side effect. A sample implementation of this simple abstraction is the expression (fun () > printf “Hello Worldn”).
* Types of the form 'a > 'a > int are frequently used to model “comparison functions”over the type 'a. You will also see 'a * 'a > int used for this purpose, where a tuple is accepted as the first argument. In both cases a negative results indicates “less than”, zero “equals” and a positive “greater than”. Many collection types will accept such a value as a configuration parameter. One frequently used implementation of this abstraction is provided by the F# compare function, which performs structural comparison on values (see Chapter 4).
* Types of the form 'a > unit are frequently used to model “callbacks”. Here 'a is a placeholder for the type of arguments passed to the callback, e.g. 'a may be System.Windows.Forms.MouseEventArgs.
* Types of the form unit > 'a are frequently used to model “delayed computations”, i.e. values that will, when required, produce a value of type 'a. For example, a threading library may accept such a function value and execute it on a different thread, eventually producing a value of type 'a. Delayed computations are related to lazy computations and comprehensions, discussed in Chapter 4.
* Types of the form 'a > 'b are frequently used to model “transformers”, e.g. functions that transform each element of a collection. You will see this pattern in the map operator for many common collection types.
* Types of the form 'a > 'b > 'b are frequently used to model “visitor accumulating functions”, e.g. functions that visit each element of a collection (type 'a) and accumulate a result (type 'b). For example, a visitor function that accumulates integers into a set of integers would have type int > Set<int> > Set<int>.
Note: The power of function types to model a multitude of nontrivial abstractions is part of the enduring appeal of functional programming. Indeed, this is one of the refreshing things that F# brings to objectoriented programming: many simple abstractions are modeled in very simple ways and often have very simple implementations through orthogonal, unified constructs such as anonymous function values and object expressions.
It is very common to use data to drive control, and indeed in functional programming the distinction between data and control is often blurred: function values can be used as data, and data can influence control flow. One example is using a function such as List.iter to iterate over a list. Let’s take a simple example:
let sites = [ 'https://www.live.com';
'https://www.google.com';
'https://search.yahoo.com' ]
sites > List.iter (fun site > printf '%s, length = %dn' site (http site).Length)
List.iter simply calls the given function (here an anonymous function) for each element in the input list. Here is its type:
val List.iter: ('a > unit) > 'a list > unit
Many additional aggregate iteration techniques are available, particularly by using values of type seq<_>. We cover this later in this chapter.
For example, let’s abstract the common pattern of timing the execution of an operation (measured in wallclock time). First we’ll explore the use of System.DateTime.Now to get the wall clock time:
> open System;;
> let start = DateTime.Now;;
val start : DateTime = 30/04/20.. 23:00:11
> fetch 'https://www.newscientist.com';;
> let finish = DateTime.Now;;
val finish : DateTime = 30/04/20.. 23:00:13
> let elapsed = finish  start;;
val elapsed : TimeSpan = 00:00:01.9799671
Note the type TimeSpan has been inferred from the use of the overloaded operator in the expression finish  start. Overloaded operators are discussed in depth in §??. We can now wrap up this technique as a function time that acts as a new control operator:
open System
let time f =
let start = DateTime.Now
let res = f()
let finish = DateTime.Now
(res, finish  start)
This function runs the input function f, but takes the time on either side of the call. It then returns both the result of the function and the elapsed time. The inferred type is:
val time : (unit > 'a) > ('a * TimeSpan)
Here 'a is a “type variable” that stands for “any” type, and thus the function can be used to time functions that return any kind of result. Note that F# has automatically inferred a very general type for the function, a technique called “automatic generalization” that lies at the heart of F# programming. Automatic generalization is discussed in detail in the side panel on page PPP. We can now use this function as follows:
> time (fun () > fetch 'https://www.newscientist.com' > String.length);;
val it : int * TimeSpan = (The time and HTML text will be shown here)
Many program tasks require the iteration, aggregation and transformation of data streamed from various sources. One very important and very general way to code tasks is in terms of values of type System.Collections.Generic.IEnumerable<'a>, which is typically abbreviated to seq<'a> in F# code[DS7] . A seq<'a> is simply a value which generates “imperative iterators”, which in turn yield results (of type 'a) on demand. They can wrap collections, computations and data streams, and are frequently used to represent the results of database queries. We will return to how this abstraction is defined in Chapter 6, but its role in applied F# programming is so central that a dedicated language construct is included to specify and transform seq<'a> values. In this section we look at some simple examples of working with seq<'a> values.
Simple seq values can be generated by using a range comprehension. In Chapter 2 we saw one simple example of a range comprehension over characters. For integer ranges these take the form for integer expressions n and m. The braces are not optional, and the spaces are required for constant ranges so the integers are not confused with floating point numbers:
> ;;
val it : seq<int> [DS8]
Range expressions may also be specified using other numeric types such as double and single:
> ;;
val it : seq<double> = [ 100.0; 99.0; 98.0; ]
By default F# Interactive only shows the value of an seq to a limited depth. Indeed, seq values are “lazy”, in the sense that they compute and return the successive elements on demand. This means you can create sequences representing very large ranges, and the elements of the sequence will only be computed if they are required by a subsequent computation. In the next example we don’t actually create a concrete data structure containing 1 trillion elements, but rather an value which has the potential to yield up to this number of elements on demand. The default printing performed by F# Interactive forces this computation up to depth four.
> ;;
val it : seq<bigint> = [ 0I; 1I; 2I; 3I; ]
The default increment for range comprehensions is always 1. A different increment may be used via range comprehensions of the form (n .. skip .. m)
> (1 .. 2 .. 5);;
val it : seq<int> = [ 1; 3; 5 ]
> ;;
val it : seq<int> = [ 1; 1; 3; 5 ]
If the skip causes the final element to be overshot then the final element is not included in the result:
> [DS9] ;;
val it : seq<int> = [ 10; 11; 12; ]
The and operators are overloaded operators in the same sense as and . This means they may be used with any type implementing a Range static method accepting two and/or three arguments of the given type (the F# compiler and library simulates the existence of these static methods for the basic .NET numeric types).
seq<'a> values can be iterated using the for … in … do construct. We discuss related constructs for imperative looping and iteration in Chapter 4, Imperative Programming, but here give a simple example as this is a common way to examine the values of an seq:
> let range = ;;
val range : seq<int> = [ 0; 2; 4; 6 ]
> for i in range do
 printf 'i = %dn”;;
i = 0
i = 2
i = 4
i = 6
This operator forces the iteration of the entire seq, so must be used with care when working with sequences that may yield a large number of elements.
Any value of type seq<_> can be iterated and transformed using functions in the Microsoft.FSharp.Collections.Seq module. For example:
> let range = ;;
val range : seq<int> = [ 0; 1; 2; 3; ]
> range > Seq.map (fun i > (i,i*i));;
val it : seq<int * int> = [ (0, 0); (1, 1); (2, 4); (3, 9) ]
Some important values in this library module are shown in Figure 3.4. The following operators necessarily evaluate all the elements of the input seq immediately:
* Seq.iter. This iterates all elements, immediately applying a function to each one.
* Seq.to_list. This iterates all elements, building a new list. Lists are concrete, finite structure, so all elements are required immediately.
* Seq.to_array. This iterates all elements, building a new array. Arrays are concrete, finite structure, so all elements are required immediately.
All the other operators shown below return an seq<_>, and only force the computation of elements in the underlying seq<_> on demand.
Figure 3.4:Some Important Functions and Aggregate Operators from the Seq module
Operator Type
Seq.append : #seq<'a> > #seq<'a> > seq<'a>
Seq.concat : #seq< #seq<'a> > > seq<'a>
Seq.choose : ('a > 'b option) > #seq<'a> > seq<'b>
Seq.delay : (unit > #seq<'a>) > seq<'a>
Seq.empty : unit > seq<'a>
Seq.iter : ('a > unit) > #seq<'a> > unit
Seq.filter : ('a > bool) > #seq<'a> > seq<'a>
Seq.map : ('a > 'b) > #seq<'a> > seq<'b>
Seq.singleton : 'a > seq<'a>
Seq.truncate : int > #seq<'a> > seq<'a>
Seq.to_list : #seq<'a> > 'a list
Seq.of_list : 'a list > seq<'a>
Seq.to_array : #seq<'a> > 'a[]
Seq.of_array : 'a[] > seq<'a>
The table in the previous section includes types prefixed with , e.g. #seq<'a>. This simply means that the function will accept any type that is compatible with (i.e. a subtype of) seq<'a>. The notions of subtyping and compatibility are explained in more detail in Chapter 5, Generics and Type Variables, but to OO programmers the concept will be very familiar, as it is the same as that used by C#, which itself is close to that used by Java. In practice it’s very important to be aware of which types are compatible with which. This can easily be discovered by either using IntelliSense in tools such as Visual Studio, as when you hover over a type name the compatible types are shown as well. You can also refer to the online documentation for the F# libraries and .NET Framework, easily searched by typing a qualified type name into a major search engine.
Here are some of the types compatible with seq<'a>:
* Array types, e.g. int[] is compatibile with seq<int>
* Most F# and .NET collection types, e.g. System.Collections.Generic.SortedList<string> is compatible with seq<string>
The following types are not directly typecompatible with seq<'a>, but can readily be converted into sequences when needed. In particular, they can be used as sequences in comprehensions and for … in … do … loops, both of which are described below.
* Many .NET types are compatible with a somewhat deprecated nongeneric .NET 1.0 construct called System.Collections.IEnumerable (note the absence of any generic parameter) but are not actually compatible with the newer construct System.Collections.Generic.IEnumerable<'a>, i.e. seq<'a> in F# code.
* Some .NET types such as System.Text.RegularExpressions.MatchCollection only support a GetEnumerator method, and can’t always be used directly as values of type seq<'a>. However these can be converted into sequences by using them in conjunction with either the comprehension or loop syntax mentioned above, e.g. or for x in matchCollection do ….
* Somewhat surprisingly, F# list types such as int list are not directly compatible with seq<int> and so can’t always be used directly where a seq<'a> is expected. This is for efficiency reasons: internally F# lists use the special value null to represent the empty list, and for various technical reasons null values can’t be used as seq values. To convert an 'a list to an seq<'a> you can use List.to_IEnumerable[DS10] , or use the list value as part of a comprehension, as discussed below.
seq<'a> values are frequently used to represent the process of streaming data from an external source, e.g. from a database query or from a computer’s file system. For example, the following recursive function constructs an seq<string> that represents the process of recursively reading the names of all the files under a given path. The return types of Directory.GetFiles and Directory.GetDirectories are string[], and as noted above this type is always compatible with seq<string>.
open System.IO
let rec allFiles dir =
let files = Directory.GetFiles(dir)
let subdirs = Directory.GetDirectories(dir)
Seq.append
files
(subdirs > Seq.map allFiles > Seq.concat)
This gives the type:
val allFiles : string > seq<string>
Here is an example of the function being used on one of the author’s machines:
> allFiles @'c:WINDOWSsystem32';;
val it : seq<string> =
= ['c:WINDOWSsystem32$winnt$.inf';
'c:WINDOWSsystem3212520437.cpx';
'c:WINDOWSsystem3212520850.cpx';
'c:WINDOWSsystem326to4svc.dll'; ]
The allFiles function is interesting partly because it shows many aspects of F# working seamlessly together:
* Functions are values. The function allFiles is recursive and is used as a firstclass function value within its own definition
* Pipelining. The pipelining operator > provides a natural way to present the transformations applied to each subdirectory name
* Type inference. Type inference computes all types in the obvious way, without any type annotations.
* NET interoperability. The System.IO.Directory operations provide intuitive primitives, which can then be incorporated in powerful ways using succinct F# programs.
* Laziness where needed. The function Seq.map applies the argument function lazily (on demand), which means that subdirectories will not be read until really required.
One subtlety with programming with sequences is that side effects such as reading and writing from an external store should not in general happen until the sequence value is actually iterated. In particular, the allFiles function as specified above reads the toplevel directory C: as soon as allFiles is applied to its argument. This may not be appropriate if the contents of C: are changing. You should delay the implementation of the sequence until iteration is performed. That is, when data sources may change and you wish to see the changes in subsequent iterations then a sequence value should be a “specification” of a how to generate a sequence rather than a single read of the data source. You can achieve this by using Seq.delay, shown below, and see the F# library documentation for more details)
open System.IO
let rec allFiles dir =
Seq.delay (fun () >
let files = Directory.GetFiles(dir)
let subdirs = Directory.GetDirectories(dir)
Seq.append
files
(subdirs > Seq.map allFiles > Seq.concat))
This also gives the type:
val allFiles : string > seq<string>
Aggregate operators are a very powerful way of working with Seq values. However, an even more convenient syntax is also provided for specifying the class of Seq values that can be built using operations such as choose, map, filter and concat. This syntax is called the enumeration comprehension syntax. It can also be used to specify the shapes of lists and arrays, as we will see below.
The simplest form of a enumeration comprehension is . Here > should be read as “yield”. This is simply a shorthand way of writing Seq.map. As with range comprehensions the parentheses are not optional when using this syntax to generate seq values. For example, we can again generate an enumeration of numbers and their squares as follows:
> let squares = ;;
val squares : seq<int * int> = [ (0,0); (1,1); (2,4); (3,9); ]
The more complete form of this construct is (for pattern in seq > expression). The pattern allows us to decompose the values yielded by the input enumerable. For example, we can consume the elements of squares using for (i,isquared) in squares:
> ;;
val range : seq<int> = [ (0,0,0); (1,1,1); (2,4,8); (3,9,27); ]
The input seq may be a seq<'a>. Somewhat unusually, it may also be an F# list or indeed a value of any type supporting a GetEnumerator method. This is because some important types from the .NET libraries support this method without directly supporting the seq interface. Below is an example where the input is a list of options. If the pattern fails to match the element of the enumerable it is skipped and no result is yielded for that element:
> ;;
val it : seq<int> = [ 5; 4 ]
An enumerable comprehension always begins with for … in …, but additional clauses can also be given, each of which may be one of:
* A secondary iteration: for pattern in seq
* A filter: when expression
* A letbinding: let pattern = expression
* A final yield: > expression
* A final yield of another sequence: >> expression
* A final match& yield: match expression with pattern >
* A final match& yield of another sequence: match expression with pattern >>
Secondary iterations each yield an enumerable, all of which are collected and concatenated together. Filters allow us to skip elements that do not satisfy a given predicate. To see both of these in action, the following computes a checkerboard set of coordinates of a rectangular grid:
let checkerboardCoordinates n =
> checkerboardCoordinates 3;;
val squares : seq<(int * int)> = [(1, 1); (1, 3); (2, 2); (3, 1); ]
The let and match clauses in comprehensions allow us to compute intermediary results and filter results through failing matches. For example, the following code gets the creation time and last access time for each file in a directory.
let fileInfo dir =
The final yield of a comprehension may be another seq, signified through the use of the >> symbol as the yield. The following sample shows how to redefine the allFiles function from the previous section using comprehension syntax.
let rec allFiles dir =
Seq.delay (fun () >
Seq.append
)
The comprehension syntax for ranges and generated sequences can also be used to build list and array values. The syntax is identical except the surrounding parentheses are replaced by the usual for lists and for arrays. We discuss arrays in more detail in Chapter 3..
> let squaresList = [ for i in (0 .. 3) > i,i*i ];;
val squaresList : (int * int) list = [ (0,0); (1,1); (2,4); (3,9) ]
> let squaresArray = [ for i in (0 .. 3) > i,i*i ];;
val squaresArray : (int * int) list = [ (0,0); (1,1); (2,4); (3,9) ]
Caution: F# lists and arrays are finite data structures built immediately rather than lazily, so care must be taken that the length of the sequence is suitable. For example, [ 1I .. 1000000000I ] will attempt to a list that is 1 billion elements long.
[DS1]Based on user feedback, this constant form (i.e. with a trailing lowercase letter “l”) will be deprecated in releases after (but no t including) F# 1.1.13.8. It is really only useful for crosscompiling OCaml code, where other techniques can be used
The problem is that in C/C++ this means “64bit”, and it is very useful to support the expected C/C++ conventions.
[DS3]NYI as of F# 1.1.13
[DS4]This module is NYI as of F# 1.1.13.8
[DS5]Computing and printing a sample incomplete match is NYI as of F# 1.1.13
[DS6]The font kerning for “>” looks poor – this may need work.
[DS7]In this section we use “sequence”, “Seq” and “seq”. Elsewhere in these draft chapters you’ll see “enumerable” and “IEnumerable”. They are equivalent, though the former are now being preferred.
[DS8] F# 1.1.13.8 prints “IEnumerable<int>”, likewise elsewhere
[DS9]This is NYI as of F# 1.1.13.8
[DS10]In future versions “List.to_seq” will be the standard operator to use here.
loading...

Vizualizari: 1107
Importanta:
Termeni si conditii de utilizare  Contact
© SCRIGROUP 2020 . All rights reserved
Distribuie URL
Adauga cod HTML in site