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.