Introduction

The idea of type is fundamental to programming. A variable’s type governs the values that the variable can hold, and the operations in which it can participate. In strictly typed languages, type is determined at compile time, and the compiler enforces strict value and operational constraints. In general, this strict type checking is valuable in that it prevents accidental misuse of a variable, and enables the compiler to generate efficient code. Sometimes, however, strict type checking can get in the way of expressiveness and flexibility.

When we develop algorithms, we tend to think about them in a type-free manner. In other words, we tend to abstract them from type and think about them generically. A classic example is sorting. It doesn’t make a difference if we are sorting integers, strings, or FileInfo objects – the idea of putting “things in a given order” is an abstract idea that applies to many different kinds of entities. Generics enable us to model data structures and algorithms in a type-agnostic way. They allow for the definition of structure while deferring type specifics.

F# Generic Functions

Systems that support generics use a type placeholder for the eventually specified concrete type or types. In other words, a generic type represents a type to be specified later. F# uses '<identifier> syntax to specify a type placeholder. We see this illustrated in the following example:

let first(a, b, c) = a
val first : 'a * 'b * 'c -> 'a

Here, the F# type inference system has determined that the function first takes a 3-member tuple, each element potentially of a different type. 'a is the first type placeholder, 'b the second, and 'c the third. These may all be different types. We can see from this definition that the function evaluates to a type of 'a.

The following is paraphrased from the MSDN documentation on F# generics:

In F#, functions, methods, properties, and aggregate types such as classes, records, and discriminated unions can be generic. Generic constructs contain at least one type parameter. Generic functions and types enable you to write code that works with a variety of types without repeating the code for each type. Making your code generic can be very simple in F#, because often your code is implicitly inferred to be generic by the compiler's type inference and automatic generalization mechanisms.

What does all this mean? In a nutshell, F# will attempt to make your structures generic, unless there is a reason it cannot. This enables and promotes code clarity, succinctness and reuse.

Automatic Generalization

When F# determines the type of a value, function or data structure, it looks at context such as function parameters, the function body, how parameters are combined in operations, etc. If F# determines that the operations, etc., are independent of type, it will automatically apply generic typing to the function at hand. We saw an example of this in the example above.

The compiler performs automatic generalization only on complete function definitions that have explicit arguments, and on simple immutable values.

Note that if you explicitly specify a type in your function parameter list or within the body of the function, you prevent automatic generalization on that value; however, F# can still apply automatic generalization to the other parameters and values.

Making Functions Generic

Due in large part to automatic generalization, when you write a function (or other construct), you can largely ignore explicitly spelling out that parameters, etc. are generic. If you run into a situation where you need to do this, F# supports this capability. In the following example, we write two swap functions. In the first case, F# determines swap to be generic.  In the second case, we tell F# that swape is generic.

let swap(a, b) = (b, a)

let swape(a:'a, b:'b) = (b, a)

Both of these functions, swap and swape (e for explicit), have exactly the same type:

val swap : 'a * 'b -> 'b * 'a
val swape : 'a * 'b -> 'b * 'a

Note that F# did not assume that a and b were of the same type. It was quite permissive, attempting to make the function as generic as possible, imposing no particular constraints on the types. Contrast this to the following function:

let f a b = a + b   // val f : int -> int -> int

In this case, F# does not generalize the function – it can’t, since operator (+) works over numerics and strings, but doesn’t work “in general” with other types. F# must bind the parameters to some type, and in this case it chooses int. I do not know the algorithm F# uses to choose this binding. I can only assume it uses the “most natural” one, perhaps defaulting to int for numeric operatons.

When you call a generic function, e.g., swap, with typed parameters, the compiler substitutes the function’s generic types with those of the passed-in parameters. Understanding this, you can make a function generic, but limit the parameters to being of the same type. In the following example, we add another function to the swap family. We’ll call this swapi, since we’re forcing the types passed in to be identical.

let swapi(x:'a, y:'a) = (y, x)

Whereas we can call the original swap function with parameters of different concrete types, we can call swapi only with parameters of the same type (indicated in the definition by 'a). We can see this in the following example:

let r1 = swap("hello", 10)          // ok

let r2 = swapi("hello", 10)         // error: string expected, got int

let r3 = swapi("hello", "goodbye")  // ok

Note that we’ve only covered generics insofar as they related to F# functions. As we proceed through the book, we’ll discover types, etc. that can also be made generic.

Limitations of Generic Functions

In a generic type or function definition, you can use only those members (properties, methods, etc.) that are known to be available on the type parameter. This is required to check function and method calls at compile time. You can apply a constraint to a generic type parameter to notify the compiler that certain methods and functions are available. We will see uses of this later, when we discuss more object-oriented types such as classes.

It is possible to write generic code that compiles but still throws an exception at runtime. Here is a simple example:

let max a b = if a > b then a else b

val max : 'a -> 'a -> 'a

This function, max, compiles fine, and will run, so long as the elements passed in are of the same type and implement .NET’s IComparable interface. Let’s look at a few calls:

let r1 = max 10 20              // ok

let r2 = max 10.0 20.0          // ok   

let r3 = max 10.0 20            // error: mismatched types

let r4 = max "hello" "dolly"    // ok, since string implements IComparable

Since all of the types we’ve studies so far implement IComparable, we need to come up with a custom types that doesn’t, so that we can demonstrate writing generic code that compiles yet still fails. Don’t worry if you don’t understand the class syntax or its use yet – we’ll get there:

type MyClass1(x: int, y: int) =

   do printfn "%d %d" x y

   new() = MyClass1(0, 0)

let mc1 = new MyClass1(10,20)

let mc2 = new MyClass1(10,30)

let r5 = max mc1 mc2
    // error, throws exception since MyClass1 does not implement IComparable

What You Need to Know

·         Generics provide a powerful and elegant mechanism for defining functions, and other data structures (that we’ll study) that can accept a wide variety of types.

·         Generics promote and support data structure and algorithm reuse.

·         F# uses an apostrophe in front of an identifier to indicate a generic type, e.g., 'a or 'b.

·         Automatic generalization describes F# ability to automatically make generic function parameters based on program context.

·         Given F#’s automatic generalization, the need for our explicitly defining generic functions is reduced compared to many other languages.

·         Automatic generalization applies to types (classes) as well as function.

·         You can override F#’s automatic generalization using explicit type definitions – either by using concrete types, or by explicitly limiting the breadth of the generics via type constraints.

·         Even though generic code may compile, it doesn’t mean that it will execute successfully at runtime. The generic types and the operations performed on those types must be consistent and compatible; otherwise, your program will throw an exception.

Feedback

We welcome your feedback. If you have comments or questions about this chapter, please feel free to e-mail us at

Keep Reading

Next Chapter...