Shorthand and Partial Application

Curried shorthand syntax

OCaml provides a concise syntax for curried function definitions. The following two definitions are equivalent:

let prefix a b = a ^ b
(* val prefix : string -> string -> string = <fun> *)

let prefix = fun a -> fun b -> a ^ b
(* val prefix : string -> string -> string = <fun> *)

In general: let f x₁ ... xₙ = E is equivalent to:

fun x₁ -> ... -> fun xₙ -> E

Application uses the same syntax: f E₁ ... Eₙ means ((f E₁) ...) Eₙ.

Partial application

Partial application means supplying fewer arguments than a curried function expects, producing a new function with the remaining parameters.

let dub = prefix "Sir "
(* val dub : string -> string = <fun> *)

dub "Hamilton"
(* : string = "Sir Hamilton" *)

This is useful when fixing the first argument yields a function that is interesting in its own right.

Function lists and partial application

Curried functions interact naturally with lists of functions. Consider:

List.hd [dub; promote] "Hamilton"
(* : string = "Sir Hamilton" *)

Here List.hd extracts dub from the list of functions, and the resulting function is applied to "Hamilton". The type of this expression works because application associates to the left: (List.hd [dub; promote]) "Hamilton".

The idea of storing code in data structures and executing it later is fundamental to object-oriented programming.

Curried insertion sort

Passing an ordering predicate as a curried argument yields a general insertion sort:

let insort lessequal =
  let rec ins x = function
    | [] -> [x]
    | y::ys -> if lessequal x y then x :: y :: ys
               else y :: ins x ys
  in
  let rec sort = function
    | [] -> []
    | x::xs -> ins x (sort xs)
  in
  sort
(* val insort : ('a -> 'a -> bool) -> 'a list -> 'a list = <fun> *)

insort is a curried function: given an ordering predicate, it returns the sorting function itself. Usage:

insort (<=) [5; 3; 9; 8]  (* => [3; 5; 8; 9] *)
insort (>=) [5; 3; 9; 8]  (* => [9; 8; 5; 3] *)
insort (<=) ["bitten"; "on"; "a"; "bee"]  (* => alphabetical sort *)

The syntax (<=) turns the infix operator into a prefix function that can be passed as an argument. Passing (>=) yields a decreasing sort: this is valid because if ≤ is a partial ordering, then so is ≥.