# F Sharp Programming/Higher Order Functions

F# : 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 which does both.

## Contents

### 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(a+h)-f(a)\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 was a literal value, and we call it just like we call any other function. For example, here's a very trivial function:

```let passFive f = (f 5)
```

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.

```open System
 
let square x = x * x    
 
let cube x = x * x * x
 
let sign x =
    if x > 0 then "positive"
    else if x < 0 then "negative"
    else "zero"
 
let passFive f = (f 5)
 
printfn "%A" (passFive square)  // 25
printfn "%A" (passFive cube)    // 125
printfn "%A" (passFive sign)    // "positive"
```

These functions have the following types:

```val square : int -> int
val cube : int -> int
val sign : int -> string
val passFive : (int -> 'a) -> 'a
```

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:

```let map item converter = converter item
```

This has the type `val map : 'a -> ('a -> 'b) -> 'b`. In other words, `map` takes a 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:

```open System
 
let map x f = f x
 
let square x = x * x
 
let cubeAndConvertToString x =
    let temp = x * x * x
    temp.ToString()
 
let answer x =
    if x = true then "yes"
    else "no"
 
let first = map 5 square
let second = map 5 cubeAndConvertToString
let third = map true answer
```

These functions have the following signatures:

```val map : 'a -> ('a -> 'b) -> 'b
 
val square : int -> int
val cubeAndConvertToString : int -> string
val answer : bool -> string
 
val first : int
val second : string
val third : string
```

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 `int`s.

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:

```let fourth = map true square
```

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:

```let inline (<<) f g x = f (g x)
```

Which has the somewhat cumbersome signature `val << : ('b -> 'c) -> ('a -> 'b) -> 'a -> 'c`.

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:

```open System
 
let f x = x*x
let g x = -x/2.0 + 5.0
 
let fog = f << g
 
Console.WriteLine(fog 0.0) // 25
Console.WriteLine(fog 1.0) // 20.25
Console.WriteLine(fog 2.0) // 16
Console.WriteLine(fog 3.0) // 12.25
Console.WriteLine(fog 4.0) // 9
Console.WriteLine(fog 5.0) // 6.25
```

Note that `fog` doesn't return a value, it returns another function whose signature is `(float -> float)`.

Of course, there's no reason why the compose function needs to be limited to numbers; since it's generic, it can work with any datatype, such as `int array`s, `tuple`s, `string`s, and so on.

There also exists the `>>` operator, which similarly performs function composition, but in reverse order. It is defined as follows:

```let inline (>>) f g x = g (f x)
```

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.

```let gof = f >> g
```

This will first apply `f` and then apply `g` on the result.

### The `|>` Operator

The pipeline operator, `|>`, is one of the most important operators in F#. The definition of the pipeline operator is remarkably simple:

```let inline (|>) x f = f x
```

Let's take 3 functions:

```let square x = x * x
let add x y = x + y
let toString x = x.ToString()
```

Let's also say we had a complicated function which squared a number, added five to it, and converted it to a string? Normally, we'd write this:

```let complexFunction x =
    toString (add 5 (square x))
```

We can improve the readability of this function somewhat using the pipeline operator:

```let complexFunction x =
    x |> square |> add 5 |> toString
```

`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.

```let complexFunction =
    2                            (* 2 *)
    |> ( fun x -> x + 5)         (* 2 + 5 = 7 *)
    |> ( fun x -> x * x)         (* 7 * 7 = 49 *)
    |> ( fun x -> x.ToString() ) (* 49.ToString = "49" *)
```

Anonymous functions are convenient and find a use in a surprising number of places.

#### A Timer Function

```open System
 
let duration f = 
    let timer = new System.Diagnostics.Stopwatch()
    timer.Start()
    let returnValue = f()
    printfn "Elapsed Time: %i" timer.ElapsedMilliseconds
    returnValue
 
let rec fib = function
    | 0 -> 0
    | 1 -> 1
    | n -> fib (n - 1) + fib (n - 2)
 
let main() =
    printfn "fib 5: %i" (duration ( fun() -> fib 5 ))
    printfn "fib 30: %i" (duration ( fun() -> fib 30 ))
 
main()
```

The `duration` function has the type `val duration : (unit -> 'a) -> 'a`. This program prints:

```Duration (ms): 0.976500
fib 5: 5
Duration (ms): 24.412500
fib 30: 832040
```
Note: the actual duration to execute these functions will 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, lets say we have a function:

```let add x y = x + y
```

`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:

```let addFive = add 5
```

The `addFive` calls the `add` function with one 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:

```open System
 
let add x y = x + y
 
let addFive = add 5
 
Console.WriteLine(addFive 12) // prints 17
```

#### How Currying Works

The function `let add x y = x + y` has the type `val add : int -> int -> int`. F# use 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:

```let add = (fun x -> (fun y -> x + y) )
```

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 syntatic 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:

```let getPrice2 =
    (fun x ->
        match x with
        | "banana" -> 0.79
        | "watermelon" -> 3.49
        | "tofu" -> 1.09
        | _ -> nan)
```

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.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 2, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8837265372276306, "perplexity_flag": "middle"}