Functions

CS3110

 2020/01/28 

From Textbook: Functions

Functions

Definition: let f x1 x2 ... xn = e (f is the function name; xi is input, and there can be multiple inputs; e is the output)

We can think of t1 -> t2 -> u as the type of a function that takes two inputs, the first of type t1 and the second of type t2, and returns an output of type u. Likewise for a function that takes n arguments.

A function is already a value (that’s how you assign the value “function” to a variable name), so there is nothing to be evaluated when we evaluate its dynamic semantic.

Anonymous Function

Definition: fun x -> x+1 (fun is a keyword indicating an anonymous function)

Anonymous functions are also called lambda expressions, a term that comes out of the lambda calculus, which is a mathematical model of computation in the same sense that Turing machines are a model of computation. In the lambda calculus, fun x -> e would be written $λx.e.$ The λ denotes an anonymous function.

Function Application

Normal way:(fun x -> e3) ((fun x -> e2) e1);;
Pipeline: e1 |> fun x->e2 |> fun x->e3;;

They are semantically the same as “let expressions” : let x = e1 in let x = e2 in e3 (In fact, the let expression is just a syntactic sugar of function application)

Function application is left-associative: g f x = (g f) x, while function types are right-associative: g -> f -> x = g -> (f -> x)

Polymorphic Functions

The 'a is a type variable: it stands for an unknown type, just like a regular variable stands for an unknown value.

Labeled Arguments

OCaml supports labeled arguments to functions. You can declare this kind of function using the following syntax:

1 2	# let f ~name1:arg1 ~name2:arg2 = arg1 + arg2;; val f : name1:int -> name2:int -> int = <fun>

This function can be called by passing the labeled arguments in either order:

1	f ~name2:3 ~name1:4;;

A sugar of declaring function with labeled arguments is

1	let f ~name1 ~name2 = name1 + name2

Partial Application

A function of two variables: let add x y = x + y

A composite function: let addx x = fun y -> x + y

1
2
3

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

The top two are just syntactic sugar for the last statement. Now, think about what does the last line mean? Does the fun y -> x+y actually knows that there exists an x? The answer is yes. That’s because the statement fun y -> x+y is in the scope of x‘s declaration.

For the codes below, the outermost function actually takes in a value of type t1 and produces a function that is of type t2 -> (t3 -> t4)

And the type of such a function

1	t1 -> t2 -> t3 -> t4

really means the same as

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

That is, function types are right associative: there are implicit parentheses around function types, from right to left. The intuition here is that a function takes a single argument and returns a new function that expects the remaining arguments.

Below is an example of Partial Application: The bottom two are syntactic sugars of the first statement

1
2
3

let comp = fun f g -> fun x -> g(f x);;
let compa f g = fun x -> g(f x);;
let compb f g x = g(f x);;

Applying comp to other functions:

utop # let inc x = x+1;;
val inc : int -> int = <fun>
────────────────────────────────────────────────────────
utop # let inc2 = comp inc inc;;
val inc2 : int -> int = <fun>
────────────────────────────────────────────────────────
utop # inc 1;;
- : int = 2
────────────────────────────────────────────────────────
utop # inc2 1;;
- : int = 3

A useful application of Partial Application is precomputation: When we want to use a process multiple times, we can just write a function that takes in other function and do that job. g. predefine comp so that when we want to composite two functions, we only need to apply it to the function comp instead of writing out the composite function on ourselves every time.

Unit Function

There is only one value of this type, which is written () and is also pronounced “unit”. So unit is like bool, except there is one fewer value of type unit than there is of bool. Unit is therefore used when you need to take an argument or return a value, but there’s no interesting value to pass or return.

Type Inference

How to determine the type of a very complicated function?

Add right-associative parameters; Rewrite the function as a more understandable let expression
Find out which variables have to take in a value (then it must be a function), which doesn’t (then it can be anything)
Determine the type of each variable from the last statement, and write their types from left to right in the sequence they were taken in.

Take fun f g -> fun x -> g(f x) as an example:

let h = fun f g -> ( fun x -> g(f x) )
- x doesn’t take in a value, so x is a variable of type a’
- f takes in x, so f must be a function of type a’ -> b’
- g takes in the output of f, so g must be a function of type b’ -> c’

The type of this function is

1 2	f g x (output:g(f x)) (a' -> b') -> (b' -> c') -> a' -> c'

Take fun f g -> fun x -> (g f) x as another example:

let h = fun f g -> (fun x -> (g f) x)
- x doesn’t take in a value, so x is a variable of type a’
- f doesn’t take in a value, so f is a variable of type b’
- g takes in f, so g must be a function whose input is of type b’; plus its output takes in another variable x, so its output is also a function, which takes in a type a’. Therefore, g is of type b' -> (a' -> c')

The type of this function is