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


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.


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.


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 means a function that takes one argument, and returns another function that takes one argument, and so on.


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


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