# First Class Functions and Functional Programming

Posted by Beetle B. on Sat 13 August 2016

Functions can take other functions as arguments. Consider:

```fun compose (f, n, x) =
if n = 0
then x
else f(compose(f, n-1, x))
```

This calls the function f on x n times. So compose(f, 3, x) is f(f(f(x))).

What is the type of this function? ('a -> 'a) * int * 'a

## Anonymous Functions

```fn arg => e

(* Example *)
fn (x, y) => x + y
```

## Some Very Useful Functions

### Map

```fun map (f,xs) =
case xs of
[] => []
| x::xs' => (f x)::(map(f,xs'))
```

This has type ('a -> 'b) * 'a lst -> 'b lst

It exists in the library as List.filter.

### Filter

```fun filter (f,xs) =
case xs of
[] => []
| x::xs' => if f x
then x::(filter (f,xs'))
else filter (f,xs')
```

This has type ('a -> bool) * 'a lst  -> 'a lst

It exists in the library as List.filter.

### Fold

```fun fold (f, acc, xs) =
case xs of
[] => acc
| x::xs' => fold (f, f(acc, x), xs')
```

This is an example of fold left. You can write one that folds to the right. The differences are:

• If f cares about the order, you will get different results.
• fold right cannot make use of tail recursion optimization.

The type of this fold is:

(`a * `b -> `a) * `a * `b list -> `a

The acc is usually the “initial” value.

## Functions That Return Functions

A function can return a function.

What if a function returns a function that returns a function, etc? How is its type written?

In general, what does this mean?

t1 -> t2 -> t3 -> t4

This is equivalent to:

t1 -> (t2 -> (t3 -> t4))

This means the function takes t1 as an argument, and returns a function that takes t2 as an argument, which returns a function that takes t3 as an argument and returns t4.

## Creating an Infix Function

```infix !>
fun x !> f = f x
fun sqrt_of_abs i = i !> abs !> Real.fromInt !> Math.sqrt

(* This means take the absolute value of i, pass it to fromInt, etc)
```

In this code, !> is a function, not an operator. Its arguments are x and f.

## Currying

Currying means a function that takes one argument, and returns another function that takes one argument, and so on.

Example:

```val sorted3 = fn x => fn y => fn z => z >= y andalso y >= x
```

To call this, we could do:

```val t2 = ((sorted3 7) 9) 11
```

But it’s easier to write as:

```val t3 = sorted3 7 9 11
```

See the Basics page for an explanation of why it works.

We can even make the function definition simpler:

```fun sorted3_nicer x y z = z >= y andalso y >= x
```

This is syntactic sugar.

Note that in the standard library, the following functions all use currying (and should be invoked as such!):

• List.map
• List.filter
• List.foldl
• List.exists

### Partial Application

When you call a curried function with fewer arguments, you get back a function that has/is a closure. It can be quite handy.

### Converting From Curried to Uncurried Functions and Back

You may have a function that is curried, and would rather have a function that takes tuples, or vice versa. Use these functions:

```fun curry f x y = f (x,y)

fun uncurry f (x,y) = f x y
```

### Efficiency

Are tupled functions more efficient than curried ones? No clear answer - it will depend on the implementation.