In F# the type of each function argument is automatically resolved for you through context whenever possible. The compiler examines how the arguments are used and attempts to provide a type that satisfies the most general case allowed by the underlying CLR type system. This process is called automatic generalization.

Consider this function which simply returns the minimum of two arguments:

> let min arg1 arg2 = if arg1 < arg2 then arg1 else arg2;;

val min : 'a -> 'a -> 'a when 'a : comparison

Here the type inference engine saw that arg1 and arg2 were compared with the less-than operator inside of the min function and so inferred that the arguments to min must have the same restrictions as the arguments to less-than. That is, they both must be the same type and have the comparison constraint. The less-than operator could just as well be another function. In that case the argument types would be inferred based on the signature of that other function.

There are a few important caveats to this. The first is that numerical operators are resolved to int if not observed being used in another context. For example, if you define a simple add function without any context you might expect it to generalize to all of the potential inputs of the plus operator. This is not the case; instead it will take and return integers by default.

> let add a b = a + b;;

val add : int -> int -> int

If you give the compiler an external context for this function, it will resolve the arguments in terms of that context.

> let add a b = a + b
add 2.0 3.0;;

val add : float -> float -> float

However, as the function signature has now been solidified to take two floats and returns another, if you now attempt to use this function with the int type, it will fail.

> add 2 3;;

  add 2 3;;
  ----^

C:UsersRickAppDataLocalTempstdin(6,5): error FS0001: This expression
was expected to have type
    float
but here has type
    int

Of course, this is less than ideal. Why should you need to write a specific version of our add function for each basic data type? Thankfully, you don't. There is a solution to this problem: the inline keyword and statically resolved type parameters.

Much like in other languages supporting this keyword, when a function is defined with inline the resulting function is injected directly into the locations from which it is called at compile-time. In older languages this was done for the sake of execution speed. In a tight loop, function calls can have significant overhead.

However, with modern processors this has become much less of an issue. These days our processors are often sitting idle, starved for information. The cost of a function call is usually a small drop in the overall bucket. Also, modern compilers are much better at optimization and will often do automatic inlining when appropriate. For these reasons the C# and VB.NET languages opted to not include this feature.

In F#, inline is mainly used for its effect on type inference. An inlined function supports much more robust type inference as it is not bound to the rules of the CLR as tightly. It can infer arguments in terms of statically resolved type parameters.

So, whereas in the previous section we saw that our add function was being automatically restricted to only accept a single type of input parameter, if we define the same function as inline it can now accept either.

> let inline add a b = a + b;;

val inline add :
   ^a ->  ^b ->  ^c
    when ( ^a or  ^b) : (static member ( + ) :  ^a *  ^b ->  ^c)

> add 2.0 3.0;;
val it : float = 5.0

> add 2 3;;
val it : int = 5

In this case the compiler is generalizing on the plus operator even though it is not generic. As long as the passed arguments support a plus operator that takes the other type, it will resolve correctly. The only caveat is that this type of inference can only happen at compile-time. Functions defined as inline will not be usable from other .NET languages.

It is sometimes necessary to explicitly describe your type parameters in F#. Most often type inference works incorrectly due to a bug elsewhere in your program. However, occasionally the compiler cannot determine the type of your parameter for you or will infer a type you don't expect. Whatever the case may be, understanding type annotations is essential to writing F# effectively.

Basic type annotation syntax is simple; you just wrap the argument in parentheses, add a colon after the argument name and express the type after it.

> let plusOne (x: int) = x + 1;;

val plusOne : int -> int

In this example we are annotating x but the return type is still inferred. To annotate the return type, place a colon after the argument list and follow it with the to-be-returned type.

> let plusOne x : int = x + 1;;

val plusOne : int -> int

The return type, as well as each argument, may or may not be annotated individually.

> let plus x (y: double) = x + y;;

val plus : double -> double -> double

It is often necessary to only annotate one argument to ensure type inference works correctly or to find that pesky bug causing your program to fail compilation. It ends up working quite a lot like dominos. When one type is correctly identified, many others fall into place as well. Once the types around it are resolved, incorrect code will stand out like a sore thumb.

F#'s type system isn't limited to just basic types. It supports the full range of generics and type constraints as other .NET languages. In fact, its type system can infer most of these automatically.

For example if you were to write a function that compares two arguments with the equals operator, the arguments automatically generalize to a generic type with the equality comparison constraint.

> let areEqual arg1 arg2 =
    arg1 = arg2;;

val areEqual : 'a -> 'a -> bool when 'a : equality

However, it is also possible to explicitly mandate these constraints when making type annotations. This can be done through application of the when keyword.

> let areEqual<'a when 'a : equality> (arg1: 'a) (arg2: 'a) =
    arg1 = arg2;;

val areEqual : 'a -> 'a -> bool when 'a : equality

In some cases you may want to have multiple constraints on a type. To do this, separate each constraint with the and keyword.

> let isNull<'a when 'a : equality and 'a : null> (arg: 'a) =
    arg = null;;

val isNull : 'a -> bool when 'a : equality and 'a : null

A list of commonly used generic type constraints follows.

As mentioned in the previous section on the inline keyword, F# also supports a much richer set of compile-time-only type constraints. To use them you must trade in generic type parameters for something called statically resolved type parameters. Parameters defined in this way are only available to F# functions marked as inline.

One particularly useful example is the member restriction type constraint. This constraint allows you to generalize a type on methods, properties, and even operators.

type PresentFromTheGods(isGood) =
     member x.IsGood : bool = isGood

let inline IsItGood< ^a when ^a : (member IsGood : bool)> (container: ^a)  =
    let isgood = (^a : (member IsGood : bool ) container)
    isgood

In this example the IsItGood function may take any object that has a gettable IsGood property that returns a bool. When passed an argument of a type defined by the member restriction statically resolved type parameter, some special syntax must be used to extract the value of that member. Here the value of the container's IsGood member is extracted into the isgood variable and then returned.

> IsItGood (new PresentFromTheGods(true));;
val it : bool = true

At compile time inline code will be generated in place of the function call. This allows for shared code that is fast and has liberal constraints.

However, as you can see from this example, statically resolved type parameters have syntax that is quite esoteric. In most cases it's best to stick with a combination of inline inference and CLR supported type constraints. This way, you can be sure that they will hold at runtime and that your functions will be available when calling F# assemblies from other languages.

In F#, partial application is done through a process called currying. A curried function is a function that internally has been broken down into a series of one parameter functions. When a parameter is passed in, another function is returned whose argument is the next parameter. This occurs until all parameters are filled in and the function is executed. This is done automatically for you in F#, but let's take a look at what it looks like conceptually.

> let explicitCurryAddTwoNumbers x =
    function y -> x + y

val explicitCurryAddTwoNumbers : int -> int -> int

Here we have a function which takes a single argument, x, and returns another function of a different argument, y. This returned function has x captured inside of it, ready for use later. This capturing of variables bound in a parent is called a closure.

> let plusOne = explicitCurryAddTwoNumbers 1;;
val plusOne : (int -> int)
> plusOne 2;;
val it : int = 3

After passing a value into the function, the internal function is returned with x bound. This function can then have another argument applied to it. This ends up being functionally equivalent to the implicit currying in F#.

> let addTwoNumbers x y = x + y
let plusOne = addTwoNumbers 1;;

val addTwoNumbers : int -> int -> int
val plusOne : (int -> int)
> plusOne 2;;
val it : int = 3

As you can see by comparing the two examples above, explicit currying requires an additional nested function for each parameter. For example, three arguments would require two nested functions.

> let explicitCurryAddThreeNumbers x =
    function y -> function z -> (x + y + z);;

val explicitCurryAddThreeNumbers : int -> int -> (int -> int)

Although this is possible to do in languages that don't support currying, simulating it with closures becomes tedious quickly. You need to explicitly nest each function, and each time a function is called, you are restricted to passing in only a single argument at a time. F# supports currying by default, so neither of these steps are necessary.

As useful as they are, for the sake of efficiency and interoperability F# has imposed a few restrictions on functions and curried methods. Not knowing about these beforehand can cause quite a bit of difficulty because they are somewhat nonintuitive.

First, functions defined outside the scope of a class cannot be overloaded. This makes sense because conceptually a free floating function is bound to a name that does not include its full type signature.

> let square x: int = x * x
let square x: double = x * x;;
error FS0037: Duplicate definition of value 'square'

Just as with data values, you cannot have multiple instances that have the same name within the same scope. However, you can bind a function to an existing name in a subscope as long as the type signature is exactly the same. Neither of these restrictions applies to class methods. As in other .NET languages, class methods may be overloaded.

> type SquareHelper =
    static member square (x: int) = x * x
    static member square (x: double) = x * x;;

type SquareHelper =
  class
    static member square : x:int -> int
    static member square : x:double -> double
  end

However, curried class methods cannot be overloaded. And any member of more than a single argument will be curried by default.

> type BadMultHelper =
    static member multiply (x: int) (y: int) = x * y
    static member multiply (x: double) (y: double) = x * y;;

      static member multiply (x: int) (y: int) = x * y;
  ------------------^^^^^^^^

The method 'multiply' has curried arguments but has the same name as another
method in this type. Methods with curried arguments cannot be overloaded.
Consider using a method taking tupled arguments.

The currying of class methods can be prevented by using tuple syntax for function arguments.

> type GoodMultHelper =
    static member multiply (x: int, y: int) = x * y
    static member multiply (x: double, y: double) = x * y;;

type GoodMultHelper =
  class
    static member multiply : x:int * y:int -> int
    static member multiply : x:double * y:double -> double
  end

Don't be concerned about the possible performance impact in potentially creating a tuple just to pass in. In actuality, F# tupled arguments turn into normal .NET calls with discrete arguments under the hood. Both types of functions will look the same from other .NET languages. The only real difference is in how they are used in the F# language syntax.

Much as a data type can have a reference to itself, a true first class function should be able to as well. In fact, it should be able to call itself using that reference just as it might any other function. A function that does this is called a recursive function and the process of using recursive functions is called recursion.

To write recursive functions in F#, you must define the function with the rec keyword. This keyword binds the function in such a way as to be visible to itself.

let rec pow x n = if n <> 0
                  then x * pow (x) (n - 1)
                  else 1.0

This pow function raises its argument x to the nth power. It does this by calling itself repeatedly, each time reducing the value of its n parameter by one and multiplying x by the result of the last call to pow. However, in F# this is a poor implementation of pow.

To understand why, you first need to understand how this function will execute at runtime. Each time pow calls itself, another stack frame is generated. In the ideal case, n eventually becomes zero and pow will return 1 instead of calling itself again. Each layered call will then return, and the result will be multiplied by x. Finally, the result of all of those multiplications will be returned.

However, each function call takes up additional stack memory, and the stack is only a finite size. If n is too large, eventually your program will run out of stack memory and throw a StackoverFlowException.

> pow 2.0 100000;;
Process is terminated due to StackOverflowException.

This, combined with the overhead of each additional function call, makes for a convincing argument against recursion in other .NET languages. However, F# supports two features that make it very good at recursion. First, F# has been heavily optimized to allow for deep recursion.

> pow 2.0 1000;;
val it : float = 1.071508607e+301

Second, it has a feature called tail call optimization that allows the compiler to turn some recursive calls into fast loops under the hood. The caveat to this is that it only applies to recursive functions whose final call leaves no work left to be done. If after calling itself the function has to do anything other than return, it can't be optimized. This may sound like it might make tail call recursion all but useless, but as you'll see here and in following chapters, it is profoundly important for both speed and safety.

To make the above example tail recursive, you need to define the same problem in a way that does not cause any work to be done after the recursive call is made. This is most easily done by introducing a new argument to hold whatever it was you were relying on the stack to hold previously. A function argument used solely to pass itself data while performing recursion is called an accumulator.

let rec tailpow x n r = if n <> 0
                        then tailpow (r * x) (n - 1) r
                        else r

In this better example r acts as the accumulator. It holds the result of the previous computation. Instead of performing the computation lazily as the recursive calls return, they are performed at each step and the result is passed into r. Finally, when n is equal to zero, the result is returned.

It might seem as though having the additional parameter is a big problem. However, it's a simple matter to embed this function inside another and so hide the accumulator.

let pow x n =
    let rec tailpow (x:float) n r = if n <> 0
                                    then tailpow x (n - 1) (r * x)
                                    else r
    tailpow x n 1.0

In fact, using techniques mentioned in the "Creating Functions at Runtime" section make this even easier and opens up even more possibilities for recursion.

Higher order functions are functions that use one particular property of a first class function. That is, they take and/or return other functions. As an example, take a look at a simple function that takes another function of no arguments.

> let square x = x * x
let performAndAddOne func = func() + 1;;

val square : int -> int
val performAndAddOne : (unit -> int) -> int

> performAndAddOne (fun () -> square 2);;
val it : int = 5

The function we pass in takes no arguments and returns the square of 2. When this is passed in to performAndAddOne it is executed, 4 is returned and 1 is added to it. What is interesting about this is not what is being done, but how. The passed in function, as well as the function it is passed in to, could just as well manipulate complex binary data.

Another slightly more advanced example of this from the .NET framework would be List<T>'s generic ForEach function. ForEach takes a function and applies it to each member in a data set. Popular functional examples include map, reduce, and fold, which are discussed in Chapter 16.

Beyond the simple idea of what higher order functions are, is the much more complex idea of what they enable. Ultimately, they allow the programmer to define a program in terms of a series of discrete data transformations instead of a series of state changes. Indeed, this idea is at the core of functional programming.

In languages without higher order functions, while, do-while, for, and foreach must be implemented in the compiler. The same would go for a generalized map, reduce, and fold. Even when using a somewhat imperative style, higher order functions enable you to write these on your own.

> let rec forEach (func: 'a -> unit) (collection: list<'a>) =
    if (Seq.isEmpty collection) then
        ()
    else
        func (List.head collection)
        forEach func (List.tail collection)

let printNum num = printfn "%i" num

let testList = [ 0; 1; 2; 3; 4 ];;

val forEach : ('a -> unit) -> 'a list -> unit
val printNum : int -> unit
val testList : int list = [0; 1; 2; 3; 4]

> forEach printNum testList;;
0
1
2
3
4
val it : unit = ()

Without some of the more advanced constructs like recursion, higher order functions provide little value other than syntactic sugar. Truly, it is the whole of the ideas presented in this part of the book that when used together make functional programming so useful.

One important idea to take away from this is that, like many functional programming constructs, higher order functions enable language-oriented programming. By leveraging them you can now accomplish much of what you would have previously needed a new compiler to do.

Although it is possible to do a great deal with only the ability to pass and return functions from other functions, storing functions in the same way as other data types grants even more power. For example, this technique is often leveraged to reuse a partially applied function over and over within the same scope.

> let processEachDataset (data1, data2, data3) =
    let transform = getDataTransform()
    let newData1 = transform data1
    let newData2 = transform data2
    let newData3 = transform data3
    (newData1, newData2, newData3);;

val processEachDataset : 'a * 'a * 'a -> 'a * 'a * 'a

It is also possible to perform some work with a set of functions that you have previously accumulated.

> let processDatasetWithCurrentTransforms data =
    let transforms = getDataTransforms()
    let rec applyTransforms data transforms =
        match transforms with
        | [] -> data
        | thisTransform :: otherTransforms ->
            applyTransforms (thisTransform data) otherTransforms
    applyTransforms data transforms;;

val processDatasetWithCurrentTransforms : 'a -> 'a

One particularly strong example of this is F#'s asynchronous workflows. Using the Async module you can take a collection of functions and send them off to separate threads to execute with little code. Without the ability to put functions into collections, powerful constructs like this would be impossible.

The ability to pass and return functions from other functions is powerful alone. Greatly enhancing this is the ability to create new functions at runtime.

In F# this can be accomplished in a number of ways that are each useful for a wide range of practical applications. Closures provide the ability to bind variables out of the scope in which a function is defined. First-class functional composition is used to build new functions out of others.

let approxDerivative f dx x = (f(x + dx) - f(x - dx)) / 2 * dx;;

let approxDerivative f dx =
    let derivative x = (f(x + dx) - f(x - dx)) / 2.0 * dx in
    derivative

let lamdbaDerivative f dx = fun x -> (f(x + dx) - f(x - dx)) / 2.0 * dx

let calcApproxDerivative f dx x = (f(x + dx) - f(x - dx)) / 2.0 * dx

let square (x: float) = x * x
let derivativeOfSquare = calcApproxDerivative square 0.001;;