# F Sharp Programming/Higher Order Functions

A higher-order function is a function that takes another function as a parameter, or a function that returns another function as a value, or a function that does both.

## Familiar Higher Order Functions

To put higher order functions in perspective, if you've ever taken a first-semester course on calculus, you're undoubtedly familiar with two functions: the limit function and the derivative function.
The limit function is defined as follows:
    $\lim _{x\to p}f(x)=L$
The limit function, lim, takes another function f(x) as a parameter, and it returns a value L to represent the limit.
Similarly, the derivative function is defined as follows:
    $deriv(f(x))=\lim _{h\to 0}{f(x+h)-f(x) \over h}=f'(x)$
The derivative function, deriv, takes a function f(x) as a parameter, and it returns a completely different function f'(x) as a result.
In this respect, we can correctly assume the limit and derivative functions are higher-order functions. If we have a good understanding of higher-order functions in mathematics, then we can apply the same principles in F# code.
In F#, we can pass a function to another function just as if it were a literal value, and call it just like any other function. For example, here's a very trivial function:
In F# notation, passFive has the following type:
    val passFive : (int -> 'a) -> 'a
In other words, passFive takes a function f, where f must take an int and return any generic type 'a. Our function passFive has the return type 'a because we don't know the return type of f 5 in advance.
These functions have the following types:
Unlike many other languages, F# makes no distinction between functions and values. We pass functions to other functions in the exact same way that we pass ints, strings, and other values.

### Creating a Map Function

A map function converts one type of data to another type of data. A simple map function in F# looks like this:
This has the type val map : 'a -> ('a -> 'b) -> 'b. In other words, map takes two parameters: an item 'a, and a function that takes an 'a and returns a 'b; map returns a 'b.
Let's examine the following code:
These functions have the following signatures:
The first function passes a datatype int and a function with the signature (int -> int); this means the placeholders 'a and 'b in the map function both become ints.
The second function passes a datatype int and a function (int -> string), and map predictably returns a string.
The third function passes a datatype bool and a function (bool -> string), and map returns a string just as we expect.
Since our generic code is typesafe, we would get an error if we wrote:
Because the true constrains our function to a type (bool -> 'b), but the square function has the type (int -> int), so it's obviously incorrect.

### The Composition Function (<< operator)

In algebra, the composition function is defined as compose(f, g, x) = f(g(x)), denoted f o g. In F#, the composition function is defined as follows:
Which has the somewhat cumbersome signature val << : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b.
If I had two functions:
    f(x) = x^2
    g(x) = -x/2 + 5
And I wanted to model f o g, I could write:
Note that fog doesn't return a value, it returns another function whose signature is (float -> float).
There's no reason why the compose function must be limited to numbers. Since it's generic, it can work with any datatype, such as int arrays, tuples, strings, and so on.
There also exists the >> operator, which similarly performs function composition, but in reverse order. It is defined as follows:
This operator's signature is as follows: val >> : ('a -> 'b) -> ('b -> 'c) -> 'a -> 'c.
The advantage of doing composition using the >> operator is that the functions in the composition are listed in the order in which they are called.
This first applies f and then applies g on the result.

## The |> Operator

The pipe forward operator, |>, is one of the most important operators in F#. The definition of the pipe forward operator is remarkably simple:
Let's take 3 functions:
Let's also say we had a complicated function that squared a number, added five to it, and converted it to a string? Normally, we'd write this:
We can improve the readability of this function somewhat using the pipe forward operator:
x is piped to the square function, which is piped to add 5 method, and finally to the toString method.

## Anonymous Functions

Until now, all functions shown in this book have been named. For example, the function above is named add. F# allows programmers to declare nameless, or anonymous functions using the fun keyword.
Anonymous functions are convenient and find a use in a surprising number of places.

### A Timer Function

The duration function has the type val duration : (unit -> 'a) -> 'a. This program prints:
    Note: the actual duration to execute these functions vary from machine to machine.

## Currying and Partial Functions

A fascinating feature in F# is called "currying", which means that F# does not require programmers to provide all of the arguments when calling a function. For example, let's say we have a function:
add takes two integers and returns another integer. In F# notation, this is written as val add : int -> int -> int
We can define another function as follows:
The addFive function calls the add function with one of its parameters, so what is the return value of this function? That's easy: addFive returns another function, which is waiting for the rest of its arguments. In this case, addFive returns a function that takes an int and returns another int, denoted in F# notation as val addFive : (int -> int).
You call addFive just in the same way that you call other functions:

### How Currying Works

The function let add x y = x + y has the type val add : int -> int -> int. F# uses the slightly unconventional arrow notation to denote function signatures for a reason: arrows notation is intrinsically connected to currying and anonymous functions. Currying works because, behind the scenes, F# converts function parameters to a style that looks like this:
The type int -> int -> int is semantically equivalent to (int -> (int -> int)).
When you call add with no arguments, it returns fun x -> fun y -> x + y (or equivalently fun x y -> x + y), another function waiting for the rest of its arguments. Likewise, when you supply one argument to the function above, say 5, it returns fun y -> 5 + y, another function waiting for the rest of its arguments, with all occurrences of x being replaced by the argument 5.
Currying is built on the principle that each argument actually returns a separate function, which is why calling a function with only part of its parameters returns another function. The familiar F# syntax that we've seen so far, let add x y = x + y, is actually a kind of syntactic sugar for the explicit currying style shown above.

### Two Pattern Matching Syntaxes

You may have wondered why there are two pattern matching syntaxes:
| Traditional Syntax | Shortcut Syntax |
| let getPrice food = match food with | "banana" -> 0.79 | "watermelon" -> 3.49 | "tofu" -> 1.09 | _ -> nan | let getPrice2 = function | "banana" -> 0.79 | "watermelon" -> 3.49 | "tofu" -> 1.09 | _ -> nan |
Both snippets of code are identical, but why does the shortcut syntax allow programmers to omit the food parameter in the function definition? The answer is related to currying: behind the scenes, the F# compiler converts the function keyword into the following construct:
In other words, F# treats the function keyword as an anonymous function that takes one parameter and returns one value. The getPrice2 function actually returns an anonymous function; arguments passed to getPrice2 are actually applied and evaluated by the anonymous function instead.