CHAPTER 5

Mastering Types and

Generics
F# constructs such as lists, tuples and function values are all “generic”, which means they
can be instantiated at multiple different types. For example, int list, string list and (int *
int) list are all instantiations of the generic family of F# list types. Likewise, int -> int
and string -> int are both instantiations of the generic family of F# function types
represented by ->. There are also many other generic types and operations in the F#
library and the.NET Framework. In this section we look at how F# determines
instantiations for generic parameters, and how F# automatically infers generic types for
function and member definitions.

Generics
Generic constructs are always represented through the use of “type variables”, which in
F# syntax are written 'a, 'b, 'k, 'key, 'K etc. For example, the definition of the list type in
the F# library begins:
type 'a list = ...
Values can also be generic. A typical generic value is List.map, whose type is as follows:
val map : ('a -> 'b) -> 'a list -> 'b list
Each time you name a generic type or value the F# type system must infer instantiations
for the type variables involved. For example, in the previous section we used hen we
used “List.map fetch” over an input list. The type of the latter was:

val fetch : string -> string * string

In this case, in the signature of List.map the type variable 'a is instantiated to string and
'b to string * string.
Sometimes the binding point of these variables will be made explicit in error
messages, and explicit bindings can also be used in type annotations, e.g. you may see:
val map<'a,'b> : ('a -> 'b) -> 'a list -> 'b list
Type variables may also be constrained, so that they may only be instantiated with
particular kinds of types. The most important kind of constraint is a subtyping constraint,
and is discussed below in the section on subtyping.

Understanding Automatic Generalization

A key feature of F# is the “automatic generalization” of code. The combination of
automatic generalization and type inference makes many programs simple, succinct and
general. It also greatly enhances code reuse. Languages without automatic generalization
force programmers to compute and explicitly write down the most general type of their
Page | 1
functions, and often this is sufficiently tedious that programmers do not take the time to
abstract common patterns of data manipulation and control.
For example, type parameters are automatically introduced when writing simple
functions that are independent of some of their arguments:
let getFirst (a,b,c) = a
Here the inferred type of getFirst is reported as:

val getFirst: 'a * 'b * 'c -> 'a

That is, getFirst has been inferred to be generic in three type variables, where the result
type is related to the first element of the input tuple. Automatic generalization is applied
when a let or member definition doesn’t fully constrain the types of inputs or outputs.
You can tell automatic generalization has been applied by the presence of type variables
in an inferred type, and ultimately by the fact you can reuse a construct at multiple types.
Automatic generalization is particularly useful when taking functions as inputs. For
example, the following takes two functions as input and applies them to each side of a
tuple:
let mapPair f g (x,y) = (f x, g y)
The generalized, inferred type is:

val mapPair : ('a -> 'b) -> ('c -> 'd) -> ('a * 'c) -> ('b * 'd)

Understanding the Value Restriction

F# sometimes requires a little help before a definition is automatically
generalized.Typically only function definitions are automatically generalized – for
historical reasons this is called the “value restriction”. For example, the following
definition does not result in a generic type and gives an error:
let empties = Array.create 100 []
----^^^^^^^
error: FS0030: Value restriction. Type inference has inferred the signature
val empties : '_a list []
but its definition is not a simple data constant. Either define 'empties' as a
simple data term, make it a function, or add a type constraint to instantiate the
type parameters.

The code attempts to create an array of empty lists. Here the error message indicates that
automatic generalization would give empties the type 'a list []. However, this type
makes no sense: it would imply that we’ve created an array of lists somehow suitable for
use with any type 'a, when in reality our array should only be usable with one type, e.g.
int list [] or string list [], but not both. (If it were usable with both then we could store
an integer list into the array and fetch it out as a string list!) The “value restriction”
ensures that declarations don’t result in this kind of confusion: automatic generalization is
not applied to declarations unless they are functions or simple, immutable data constructs.
You can work around this restriction in two ways. First, if you intended to create a
function that generated arrays of different types on demand than you can often make the
declaration into a function by adding a dummy argument:
let makeEmpties () = Array.create 100 []
let intEmpties : int list [] = makeEmpties()

Page | 2
let stringEmpties : string list [] = makeEmpties()

However, if you really meant to create one value then simply use an explicit type
annotation, e.g.
let empties : int list [] = Array.create 100 []

Types, Subtyping and Runtime Types

For the most part, programming in F# involves using types in a “simple” way, where
types are related through the use of explicit code to map from one type to another. For
example, values of the type int are distinct from values of the type float, and values of
one record type such as Person are distinct from values of another such as Company.
This is very often sufficient, partly because type inference and function values make it
easy to write generic code.
However, it is convenient for a language to also support values that can be sused at
multiple types. F# supports these implicit relationships thorugh subtyping. Subtyping in
F# is exactly the same as that used by the .NET Framework, so if you are familiar with
another .NET language you’ll already know how things things work.

Upcasts
We can explore how sub-typing works by using F# Interactive. Firstly, let’s look at how
some of the F# types we’ve already seen relate to the type obj (an abbreviation for the
.NET type System.Object):

> let xobj = (1 :> obj);;

val xobj : obj = 1
> let sobj = ("abc" :> obj);;
val sobj : obj = "abc"

Here we are simply investigating the subtyping relationship through the use of the built-in
coercion (or “up cast”) operator :>. This operator is used to convert a value to any of its
super-types. For some types this operation may involve a change of representation called
“boxing”. Boxing may also be performed with the F# library function box.
So far we have only investigated subtyping between ordinary types and the type obj.
Subtyping occurs between other kinds of types as well (the various kinds of type
definitions such as records, discriminated unions, classes and interfaces are discussed in
Chapter 6):
* All types are subtypes of System.Object
* Record and discriminated union types are subtypes of the interface types they
implement
* Interfaces types are subtypes of the other interfaces they extend
* Class types are subtypes of both the interfaces they implement and the classes they
extend
* Array types are subtypes of the .NET type System.Array
* Value types (e.g. types such as int32 that are abbreviations of .NET value types)
are subtypes of the .NET type System.ValueType. Likewise .NET enumeration
types are subtypes of System.Enum.

Page | 3
> let xobj = (1 :> obj);;
val xobj : obj = 1
> let sobj = ("abc" :> obj);;
val sobj : obj = "abc"

Downcasts
Values that may have subtypes also carry a “runtime type”, and runtime type tests may be
used to query the type of an object. This can be done in two main ways: through
downcasts and pattern type tests. As with most object-oriented languages, the “upcasts”
performed through subtyping is reversible through the use of “downcasts”, using the :?>
operator. We can see this through the following examples:

> let sobj = box "abc";;

val sobj : obj
> let s = (sobj :?> string);;
val s : string = "abc"

Downcasts are checked at runtime and is safe as all values of the obj type are implicitly
annotated with the “runtime type” of the value. The operator :?> will raise an exception if
the object is not of a suitable type:

> let xobj = box 1;;

val xobj : obj = 1
> let x = (xobj :?> string);;
error: InvalidCastException raised at or near stdin:(2,0)

Type Tests via Pattern Matching

A more convenient way of performing dynamic types tests is by using “type-test
patterns”, in particular the :? pattern construct, which we encountered in the context of
catching various .NET exception types. Here is an example where we use a pattern type
test to query the dynamic type of a value of type obj:
let checkObject (x: obj) =
match (box "abc") with
| :? string -> printf "the object is a string\n"
| :? int -> printf "the object is an integer\n"
| _ -> printf "the input is something else\n"

> checkObject (box "abc")

the input is a string

Such a pattern may bind the matched value at its more specific type:
let reportObject (x: obj) =
match (box "abc") with
| :? string as s -> printf "the input is the string '%s'\n" s
| :? int as d -> printf "the input is the integer '%d'\n" d
| _ -> printf "the input is something else\n"

Page | 4
> reportObject (box 17)
the input is the integer '17'

Generics and Subtyping

F# functions can be declared to accept parameters that are any subtype of a particular type
by using type annotations of the form #type, where type is some type that supports
subtyping. This is particularly common when working with .NET libraries that use
subtyping heavily, or when working with abstractions such as interface values. For
example,

> open System.Windows.Forms

> let setTextOfControl (c : #Control) (s:string) = c.Text <- s;;
val setTextOfControl: #Control -> string -> unit

This notation is shorthand for a generic function and a “constraint” on the type variable,
and we could equally have written:

> open System.Windows.Forms

> let setTextOfControl (c : 'a) (s:string) : _ when 'a :> Control = c.Text <- s;;
val setTextOfControl: #Control -> string -> unit

Types Annotations and Type Inference

TBD

Making Things Generic

In this section we discuss how to make existing code more generic, i.e. reusable, and how
to systematically represent the abstract parameters of generic algorithms.

Generic Algorithms through Explicit Arguments

A common pattern in F# programming is to accept function parameters in order to make
an algorithm abstract and reusable. A simple sample is the following algorithm to
compute the highest common factor of two numbers:
let rec hcf a b =
if a=0 then b
elif a<b then hcf a (b-a)
else hcf (a-b) b
For example:

hcf 18 12;;
val it : int = 6
hcf 33 24;;

Page | 5
val it : int = 3

However, this algorithm is not generic, since as written it works only over integers. In
particular, although the operator (-) is by default overloaded in F#, each particular use of
the operator must be associated with at most one type. Furthermore, the constant 0 is an
integer and is not overloaded. Overloading is described in more detail in the side panel on
page X. However, despite this, this algorithm can be easily generalized to work over any
type, though we must be given a zero, a subtraction function and an ordering that type.
Here’s how we do this:
let hcfGeneric (zero,(-),(<)) =
let rec hcf a b =
if a=zero then b
elif a<b then hcf a (b-a)
else hcf (a-b) b
hcf

let hcfInt = hcfGeneric (0, (-),(<))

let hcfInt64 = hcfGeneric (0L,(-),(<))
let hcfBigInt = hcfGeneric (0I,(-),(<))
Notice how simple the process of abstracting the algorithm has been: we have simply
created a generic version of the function by parameterizing it by a tuple (zero,(-),(<)).
Even operator names such as (-) can be used as variable names! When we instantiate the
generic function for the particular cases we are drawing on particular instances of the
default overloaded operator (-). We can check that the code is executing correctly as
follows:

> hcfInt 18 12;;

val it : int = 6
> hcfBigInt 1810287116162232383039576I
1239028178293092830480239032I;;
val it : bigint = 33224

Generic Algorithms through Records of Functions

One of the important uses of abstractions is to implement generic algorithms. For now we
give one example – a generic implementation of “Euclid’s algorithm” for finding the
highest-common-factor of two integers:
type NumericOps<'a> =
{ Zero: 'a;
Subtract: 'a -> 'a -> 'a;
LessThan: 'a -> 'a -> bool; }

let intOps = { Zero=0 ; Subtract=(-); LessThan=(<) }

let bigintOps = { Zero=0I; Subtract=(-); LessThan=(<) }
let int64Ops = { Zero=0L; Subtract=(-); LessThan=(<) }

let hcfGeneric (ops : NumericOps<'a>) =

let zero = ops.Zero
let (-) = ops.Subtract
Page | 6
 let (<) = ops.LessThan
let rec hcf a b =
if a= zero then b
elif a < b then hcf a (b-a)
else hcf (a-b) b
hcf

let hcfInt = hcfGeneric intOps

let hcfBigInt = hcfGeneric bigintOps

The inferred types are:

val hcfGeneric : NumericOps<'a> -> 'a -> 'a -> 'a

val hcfInt : (int -> int -> int)
val hcfBigInt : (bigint -> bigint -> bigint)

and an example of the use of the function is:

> hcfInt 18 12;;

val it : int = 6
> hcfBigInt 1810287116162232383039576I
1239028178293092830480239032I;;
val it : bigint = 33224I

Records of this kind are often called “dictionaries of operations”, and are similar to
vtables from object-oriented programming but are not associated with any particular
object. As we have seen dictionaries can be represented by both tuples and records.

GENERIC ALGORITHMS AND FUNCTION PARAMETERS

One of the remarkable features of functional programming with F# is that it

makes generic programming practical even when the types involved are not
explicitly related. For example, the generic algorithm above shows how
reusable code can be written without resorting to relating the types involved
through subtyping: the generic algorithm works over any type, provided an
appropriate set of operations is provided to manipulate values of that type.
This is a form of factoring by functions. Object-oriented inheritance
hierarchies are a form of factoring by library design, since the library
designer decides the relationships that must hold between various types.
Haskell’s type classes are another form of factoring by library design.
F# makes factoring by functions extremely convenient, and given the
simplicity and flexibility of this approach it is recommended as the approach
to use when writing applications and proto-typing frameworks. However,
“implicit” factoring by library design does play a role in F# programming.
For example, all F# values can be implicitly factored to the the type
System.Object, as it would be inconvenient to have to pass around functions
to marshal (box/unbox) types to System.Object and back. Similary many F#
values can be implicitly factored to the IDisposable interface. Implicit
factoring requires careful design choices and should generally only be used
where careful attention is given to the hierarchy of factors supported. The
.NET library contains definitions of most of the implicit factors you’ll use in
practice, e.g. IDisposable.

Page | 7
 Generic Algorithms through Interface Objects
For larger frameworks a carefully constructed classification of dictionaries represented by
interfaces are often used in place of records. We discuss interface declarations in more
detail in the Chapter 6, and the F# namespace Microsoft.FSharp.Math.Classifications
contains a number of numerical classification types. Here is an interface type definition
that plays the same role as the record in the example above:
type INumeric<’a> =
interface
abstract Zero : ’a;
abstract Subtract: ’a * ’a -> ’a;
abstract LessThan: ’a * ’a -> bool;
end
Interface values can be built and used in a similar way to record values:
let intOps =
{ new INumericOps<int>
with Zero = 0;
and Subtract(x,y) = x - y
and LessThan(x,y) = x < y }

val intOps : INumericOps<int> = 2

Page | 8