Currying in Lambda Calculus and OCaml

Currying

Recall that in lambda calculus, a function can have more than one input, each preceded by a λ symbol.  Another way of thinking about more than one input is currying.  Currying a function of two inputs turns that function into a function with one input by passing one of the inputs into it.  In other words, currying turns f(x,y) to g(y) in which g is f with x passed into it.  And g only takes one input, y.  For example:

f(x,y) = x + y ; if x = 3 then
f(3,y) = 3 + y

Similarly in lambda calculus:

λx.λy.(x+y) 3 y
= λy.(3+y) y

One can curry recursively, and turn a function of any number of input to a function of that number of input minus one.  For example:

λx.λy.λz.(x+y+z) 3 4 5
= λy.λz.(3+y+z) 4 5
= λz.(3+4+z) 5
= (3+4+5)

Line 1 is a function that takes in 3 inputs (x,y,z).  Line 2 is a function that takes in 2 inputs (y,z).  Line 3 is a function that takes in 1 input (z).

Currying in OCaml

Currying is also applied in popular functional languages including Haskell and OCaml.  For example:

let fun1 x y z = x + y + z;;
val fun1 : int -> int -> int -> int = <fun>

In line 1 I defined a function in OCaml that takes inputs x,y,z.  Line 2 is the OCaml output, displaying the type signature of my function named fun1.  How do we read it?

The first 3 int are the input types of x,y,z.  The last int is the type of the output of fun1.  You can see that OCaml treats fun1 as a function that takes and passes in x (an int), and returns a function (with x passed in) that takes and passes in y, which returns a function (with x and y passed in) that takes in z.  Lastly, the function (with all x,y,z passed in) returns an int.

Let’s take a look at another example:

let is_larger_than fun1 y = fun1 y > 100;;
val is_larger_than : ('a -> int) -> 'a -> bool = <fun>

The first input type is (‘a -> int).  No currying is involved here.  It is a function that takes one input of a generic type (‘a), and returns an int.  OCaml treats is_larger_than as a function that takes in fun1, and returns a function (with fun1 passed in) that takes and passes in (‘a).  The output of is_larger_than is a bool.  If fun1 were to take more than one input, OCaml curries it:

let is_larger_than fun1 x y z = fun1 x y z > 100;;
val is_larger_than : ('a -> 'b -> 'c -> int) -> 'a -> 'b -> 'c -> bool = <fun>

Again, the first input is a function.  fun1 takes in 3 inputs x,y,z.  OCaml curries it, similar to above.  OCaml treats is_larger_than as a function that takes and passes in fun1, and returns a function (with fun1 passed in) that takes in (‘a), and so on.

Currying applies in many other instances too.  See this article.