Values and Functions

Introduction

In OCaml, functions are treated as values, so you can use functions as arguments to functions and return them from functions. This tutorial introduces the relationship between expressions, values, and names. The first four sections address non-function values. The following sections, starting atFunction as Values, address functions.

We use UTop to understand these concepts by example. You are encouraged to modify the examples to gain a better understanding.

What is a Value?

Like most functional programming languages, OCaml is anexpression-oriented programming language. That means programs are expressions. Actually, almost everything is an expression. In OCaml, statements don't specify actions to be taken on data. All computations are made through expression evaluation. Computing expressions produce values. Below, you'll find a few examples of expressions, their types, and the resulting values. Some include computation and some do not:

#"Every expression has a type";;-:string="Every expression has a type"#2 * 21;;-:int=42#int_of_float;;-:float->int=<fun>#int_of_float(3.14159*.2.0);;-:int=6#funx->x*x;;-:int->int=<fun>#print_endline;;-:string->unit=<fun>#print_endline"Hello!";;Hello!-:unit

An expression's type (before evaluation) and its resulting value's type (after computation) are the same. This allows the compiler to avoid runtime type checks in binaries. In OCaml, the compiler removes type information, so it's not available at runtime. In programming theory, this is calledsubject reduction.

Global Definitions

Every value can be named. This is the purpose of thelet … = … statement. The name is on the left; the expression is on the right.

• If the expression can be evaluated, it is.
• Otherwise, the expression is turned into a value as-is. That's the case of function definition.

This is what happens when writing a definition in UTop:

#letthe_answer=2*3*7;;valthe_answer:int=42

Global definitions are those entered at the top level. Here,the_answer is defined globally.

Local Definitions

Local definitions bind a name inside an expression:

#letd=2*3ind*7;;-:int=42#d;;Error:Unboundvalued

Local definitions are introduced by thelet … = … in … expression. The name bound before thein keyword is only bound in the expression after thein keyword. Here, the named is bound to6 inside the expressiond * 7.

A couple of remarks:

• No global definition is introduced in this example, which is why we get an error.
• Computation of2 * 3 will always take place befored * 7.

Local definitions can be chained (one after another) or nested (one inside another). Here is an example of chaining:

#letd=2*3inlete=d*7ind*e;;-:int=252#d;;Error:Unboundvalued#e;;Error:Unboundvaluee

Here is how scoping works:

• d is bound to6 insidelet e = d * 7 in d * e
• e is bound to42 insided * e

Here is an example of nesting:

#letd=lete=2*3ine*5ind*7;;-:int=210#d;;Error:Unboundvalued#e;;Error:Unboundvaluee

Here is how scoping works:

• e is bound to6 insidee * 5
• d is bound to30 insided * 7

Arbitrary combinations of chaining or nesting are allowed.

In both examples,d ande are local definitions.

Forms of Pattern Matching

Pattern matching is a programming language construct that generalizes case analysis, it makes subexpression inspection possible and applies to values of any type.

In the following sections, we explore matching insidelet bindings, which is a special case. In the next chapter onBasic Data Types and Pattern Matching, we examine pattern matching in general cases usingmatch...with. The chapter onError Handling explores how destructuring values aids in error handling when usingtry...with.

Pattern Matching in Definitions

When pattern matching only has one case, it can be used in name definitions and inlet ... = andfun ... -> expressions. In that case, less or more than onename may be defined. This applies to tuples, records, and custom single-varianttypes.

Pattern Matching on Tuples

A common case is tuples. It allows the creation of two names with a singlelet.

#List.split;;-:('a*'b)list->'alist*'blist#let(x,y)=List.split[(1,2);(3,4);(5,6);(7,8)];;valx:intlist=[1;3;5;7]valy:intlist=[2;4;6;8]

TheList.split function turns a list of pairs into a pair of lists. Here, each resulting list is bound to a name.

Pattern Matching on Records

We can pattern match on records:

#typename={first:string;last:string};;typename={first:string;last:string;}#letrobin={first="Robin";last="Milner"};;valrobin:name={first="Robin";last="Milner"}#let{first=given_name;last=family_name}=robin;;valgiven_name:string="Robin"valfamily_name:string="Milner"

Pattern Matching in Function Parameters

Single-case pattern matching can also be used for parameter declaration.

Here is an example with tuples:

#letget_country((country,{first;last}):string*name)=country;;valget_country:string*name->string=<fun>

Here is an example with thename record:

#letintroduce{first;last}="I am"^first^""^last;;valintroduce:name->string=<fun>

Note Using thediscard pattern for parameter declaration is also possible.

#letget_meaning_=42;;valget_meaning:'a->int=<fun>

Pattern Matching onunit

A special case of combined definition and pattern matching involves theunit type:

#let()=print_endline"ha ha";;haha

Note: As explained in theTour of OCaml tutorial, theunit type has a single value(), which is pronounced "unit."

Above, the pattern does not contain any identifier, meaning no name is defined. The expression is evaluated and the side effect takes place (printingha ha to standard output).

Note: In order for compiled files to only evaluate an expression for its side effects, you must write them afterlet () =.

Pattern Matching on User-Defined Types

This also works with user-defined types.

#typecitizen=string*name;;typecitizen=string*name#let((country,{first=forename;last=surname}):citizen)=("United Kingdom",robin);;valcountry:string="United Kingdom"valforename:string="Robin"valsurname:string="Milner"

Nested Pattern Matching on User-Defined Types

Pattern matching also works with nested user-defined types. In the example below, we deconstruct nested tuples:

#let(name,(street,city,zip),(email,phone))=("John Doe",("123 Elm St","Springfield",12345),("john@example.com",1234567890));;valname:string="John Doe"valstreet:string="123 Elm St"valcity:string="Springfield"valzip:int=12345valemail:string="john@example.com"valphone:int=1234567890

In the following example, we deconstruct a tuple nested within a record.

Records require explicit type definitions wherein field names are annotated with types. We first define aperson record type, then create an instance of that type namedjane:

#typeperson={name:string;street:string;city:string;zip:int;contact:string*int;};;typeperson={name:string;street:string;city:string;zip:int;contact:string*int;}#letjane={name="Jane Doe";street="123 Elm St";city="Springfield";zip=12345;contact=("jane@example.com",1234567890);};;valjane:person={name="Jane Doe";street="123 Elm St";city="Springfield";zip=12345;contact=("jane@example.com",1234567890)}

The following examples demonstrate two methods by which we can extract Jane'semail andphone number data in the nestedcontact tuple. We will do so first by using nested deconstruction, then demonstrate another approach by first extractingcontent followed by accessing theemail andphone by deconstructingcontact.

First, let's use nested deconstruction to access the contents of thecontact tuple directly:

#let{name;street;city;zip;contact=(email,phone)}=jane;;valname:string="Jane Doe"valstreet:string="123 Elm St"valcity:string="Springfield"valzip:int=12345valemail:string="jane@example.com"valphone:int=1234567890

Notice thatcontact is not available in our top-level scope:

#contact;;Error:Unboundvaluecontact

This is because "contact" is not a top-level definition; rather, it is a local definition from deconstructive pattern-matching.

Next, we demonstrate the two-phase approach for accessingemail andphone. This bringscontact into our top-level scope and requires two steps:

(* Step 1: deconstruct all record fields*)#let{name;street;city;zip;contact}=jane;;valname:string="Jane Doe"valstreet:string="123 Elm St"valcity:string="Springfield"valzip:int=12345valcontact:string*int=("jane@example.com",1234567890)(* Step 2: deconstruct the tuple*)#let(email,phone)=contact;;valemail:string="jane@example.com"valphone:int=1234567890

Notice thatcontact is now available at the top-level as a bound variable:

#contact;;-:string*int=("jane@example.com",1234567890)

Discarding Values Using Pattern Matching

When pattern matching, it is possible to discard or ignore values that are not desired. The method by which this is done depends on the data structure being destructured.

Continuing from the abovejane record example, we can simply omit thezip field in the pattern if we don't want to bind it to a variable:

#let{name;street;city;contact=(email,phone)}=john;;valname:string="Nohn Doe"valstreet:string="123 Elm St"valcity:string="Springfield"valemail:string="jane@example.com"valphone:int=1234567890

Tuples behave differently from records; contained data is anonymous, and its position is used to access it. To discard theemail value from the tuple of thecontact field, we need to use the catch-all pattern (_):

#let{name;street;city;contact=(_,phone)}=john;;valname:string="Jane Doe"valstreet:string="123 Elm St"valcity:string="Springfield"valphone:int=1234567890

Scopes and Environments

Without oversimplifying, an OCaml program is a sequence of expressions or globallet definitions.

Execution evaluates each item from top to bottom.

At any time during evaluation, theenvironment is the ordered sequence of available definitions. Theenvironment is also known ascontext in other languages.

Here, the nametwenty is added to the top-level environment.

#lettwenty=20;;valtwenty:int=20

The scope oftwenty is global. This name is available anywhere after the definition.

Here, the global environment is unchanged:

#letten=10in2*ten;;-:int=20#ten;;Error:Unboundvalueten

Evaluatingten results in an error because it hasn't been added to the global environment. However, in the expression2 * ten, the local environment contains the definition often.

Although OCaml is an expression-oriented language, it has a few statements. The globallet modifies the global environment by adding a name-valuebinding.

Top-level expressions are also statements because they are equivalent tolet _ = definitions.

#(1.0+.sqrt5.0)/.2.0;;-:float=1.6180339887498949#let_=(1.0+.sqrt5.0)/.2.0;;-:float=1.6180339887498949

Inner Shadowing

Once you create a name, define it, and bind it to a value, it does not change. That said, a name can be defined again to create a new binding:

#leti=21;;vali:int=21#leti=7ini*2;;-:int=14#i;;-:int=21

The second definitionshadows the first. Inner shadowing is limited to the local definition's scope. Therefore, anything written after will still take the previous definition, as shown above. Here, the value ofi hasn't changed. It's still21, as defined in the first expression. The second expression bindsi locally, insidei * 2, not globally.

Same-Level Shadowing

Another kind of shadowing takes place when there are two definitions with the same name at the same level.

#leth=2*3;;valh:int=6#lete=h*7;;vale:int=42#leth=7;;valh:int=7#e;;-:int=42

There are now two definitions ofh in the environment. The firsth is unchanged. When the secondh is defined, the first one becomes unreachable.

Function as Values

In OCaml, functions are values. This is the key concept offunctional programming. In this context, it is also possible to say that OCaml hasfirst-class functions.

Applying Functions

When several expressions are written side by side, the leftmost one should be a function. All the others are arguments. In OCaml, no parentheses are needed to express passing an argument to a function. Parentheses serve a single purpose: associating expressions to create subexpressions.

#max(21*2)(int_of_string"713");;-:int=713

Themax function returns the largest of its two arguments, which are:

• 42, the result of21 * 2
• 713, the result ofint_of_string "713"

When creating subexpressions, usingbegin ... end is also possible. This is the same as using brackets( ... ). As such, the above could also be rewritten and get the same result:

#maxbegin21*2endbeginint_of_string"713"end;;-:int=713

#String.starts_with ~prefix:"state""stateless";;-:bool=true

Some functions, such asString.starts_with have labelled parameters. Labels are useful when a function has several parameters of the same type; naming arguments allows to guess their purpose. Above,~prefix:"state" indicates"state" is passed as labelled argumentprefix.

Labelled and optional parameters are detailed in theLabelled Arguments tutorial.

There are two alternative ways to apply functions.

The Application Operator

The application operator is@@.

#sqrt9.0;;-:float=3.#sqrt@@9.0;;-:float=3.

The@@ application operator applies an argument (on the right) to a function (on the left). It is useful when chaining several calls, as it avoids writing parentheses, which creates easier-to-read code. Here is an example with and without parentheses:

#int_of_float(sqrt(float_of_int(int_of_string"81")));;-:int=9#int_of_float@@sqrt@@float_of_int@@int_of_string"81";;-:int=9

The Pipe Operator

The pipe operator (|>) also avoids parentheses but in reversed order: function on right, argument on left.

#"81"|>int_of_string|>float_of_int|>sqrt|>int_of_float;;-:int=9

This is just like a Unix shell pipe.

Anonymous Functions

Functions don't have to be bound to a name unless they arerecursive. Take these examples:

#funx->x;;-:'a->'a=<fun>#funx->x*x;;-:int->int=<fun>#funst->s^""^t;;-:string->string->string=<fun>#function[]->None|x::_->Somex;;-:'alist->'aoption=<fun>

Function values not bound to names are calledanonymous functions.

In order, here is what they are:

• The identity function, which takes anything and returns it unchanged
• The square function, which takes an integer and returns it squared
• The function that takes two strings and returns their concatenation with a space character in between
• The function that takes a list and either returnsNone, if the list is empty, or returns its first element.

Anonymous functions are often passed as arguments to other functions.

#List.map(funx->x*x)[1;2;3;4];;-:intlist=[1;4;9;16]

Defining Global Functions

You can globally bind a function to a name using a global definition.

#letf=funx->x*x;;valf:int->int=<fun>

The expression, which happens to be a function, is turned into value and bound to a name. Here is another way to do the same thing:

#letgx=x*x;;valg:int->int=<fun>

The former explicitly binds the anonymous function to a name. The latter uses a more compact syntax and avoids thefun keyword and the arrow symbol.

Defining Local Functions

A function may be defined locally.

#letsqx=x*xinsq7*sq7;;-:int=2401#sq;;Error:Unboundvaluesq

Callingsq gets an error because it was only defined locally.

The functionsq is only available inside thesq 7 * sq 7 expression.

Although local functions are often defined inside the function's scope, this is not a requirement.

Closures

This example illustrates aclosure usingSame-Level Shadowing

#letj=2*3;;valj:int=6#letkx=x*j;;valk:int->int=<fun>#k7;;-:int=42#letj=7;;valj:int=7#k7;;(* What is the result?*)-:int=42

Here is how this makes sense:

1. Constantj is defined, and its value is 6.
2. Functionk is defined. It has a single parameterx and returns the value ofx * j.
3. Computek of 7, and its value is 42
4. Create a new definitionj, shadowing the first one
5. Computek of 7 again, the result is the same: 42

Although the new definition ofjshadows the first one, the original remains the one the functionk uses. Thek function's environment captures the first value ofj, so every time you applyk (even after the second definition ofj), you can be confident the function will behave the same.

However, all future expressions will use the new value ofj (7), as shown here:

#letm=j*3;;valm:int=21

Partially applying arguments to a function also creates a new closure.

#letmax_42=max42;;valmax_42:int->int=<fun>

Inside themax_42 function, the environment contains an additional binding between the first parameter ofmax and the value 42.

Recursive Functions

In order to perform iterated computations, a function may call itself. Such a function is calledrecursive.

#letrecfibon=ifn<=1thennelsefibo(n-1)+fibo(n-2);;valfibo:int->int=<fun>#letu=List.init10Fun.id;;valu:intlist=[0;1;2;3;4;5;6;7;8;9]#List.mapfibou;;-:intlist=[0;1;1;2;3;5;8;13;21;34]

This is a classic (and very inefficient) way to computeFibonacci numbers. The number of recursive calls created doubles at each call, which creates exponential growth.

In OCaml, recursive functions must be defined and explicitly declared by usinglet rec. It is not possible to accidentally create a recursive function, and recursive functions can't be anonymous.

Note:List.init is a standard library function that allows you to create a list by applying a given function to a sequence of integers, andFun.id is the identity function, which returns its argument unchanged. We created a list with the numbers 0 - 9 and named itu. We applied thefibo function to every element of the list usingList.map.

This version does a better job:

#letrecfib_loopmni=ifi=0thenmelsefib_loopn(n+m)(i-1);;valfib_loop:int->int->int->int=<fun>#letfib=fib_loop01;;valfib:int->int=<fun>#List.init10Fun.id|>List.mapfib;;-:intlist=[0;1;1;2;3;5;8;13;21;34]

The first versionfib_loop has two extra parameters: the two previously computed Fibonacci numbers.

The second versionfib uses the first two Fibonacci numbers as initial values. There is nothing to be computed when returning from a recursive call, so this enables the compiler to perform an optimisation calledtail call elimination.

Note: Notice that thefib_loop function has three parametersm n i but when definingfib only two arguments were passed0 1, using partial application.

Functions with Multiple Parameters

Defining Functions with Multiple Parameters

To define a function with multiple parameters, each must be listed between the name of the function (right after thelet keyword) and the equal sign, separated by space:

#letsweet_catxy=x^""^y;;valsweet_cat:string->string->string=<fun>#sweet_cat"kitty""cat";;-:string="kitty cat"

Anonymous Functions with Multiple Parameters

We can use anonymous functions to define the same function in a different way:

#letsour_cat=funx->funy->x^""^y;;valsour_cat:string->string->string=<fun>#sour_cat"kitty""cat";;-:string="kitty cat"

Observesweet_cat andsour_cat have the same body:x ^ " " ^ y. They only differ in the way parameters are listed:

1. Asx y between name and= insweet_cat
2. Asfun x -> fun y -> after= insour_cat (and nothing but name before=)

Also observe thatsweet_cat andsour_cat have the same type:string -> string -> string.

If you check the assembly code generated usingcompiler explorer, you'll see it is the same for both functions.

The waysour_cat is written corresponds more explicitly to the behaviour of both functions. The namesour_cat is bound to an anonymous function having parameterx and returning an anonymous function having parametery and returningx ^ " " ^ y.

The waysweet_cat is written is an abbreviated version ofsour_cat. Such a way of shortening syntax is calledsyntactic sugar.

Partial Application and Closures

We want to define functions of typestring -> string that append"kitty " in front of its arguments. This can be done usingsour_cat andsweet_cat

#letsour_kittyx=sour_cat"kitty"x;;valsour_kitty:string->string=<fun>#letsweet_kitty=funx->sweet_cat"kitty"x;;valsweet_kitty:string->string=<fun>#sour_kitty"cat";;-:string="kitty cat"#sweet_kitty"cat";;-:string="kitty cat"

However, both definitions can be shortened using something calledpartial application

#letsour_kitty=sour_cat"kitty";;valsour_kitty:string->string=<fun>#letsweet_kitty=sweet_cat"kitty";;valsweet_kitty:string->string=<fun>

Since a multiple-parameter function is a series of nested single-argument functions, you don't have to pass all arguments at once.

Passing a single argument tosour_kitty orsweet_kitty returns a function of typestring -> string.The first argument, here"kitty", is captured and the result is aclosure.

These expressions have the same value:

• fun x -> sweet_cat "kitty" x
• sweet_cat "kitty"

Types of Functions of Multiple Parameters

Let's look at the types here:

#letdummy_cat:string->(string->string)=sweet_cat;;valdummy_cat:string->string->string=<fun>

Here the type annotation: string -> (string -> string) is used to explicitly state the type ofdummy_cat.

However, OCaml answers claiming the fresh definition has typestring -> string -> string. This is because typesstring -> string -> string andstring -> (string -> string) are the same.

With parentheses, it is obvious that a multiple-argument function is a single-parameter function that returns an anonymous function with one parameter removed.

Putting the parentheses the other way does not work:

#letbogus_cat:(string->string)->string=sweet_cat;;Error:Thisexpressionhastypestring->string->stringbutanexpressionwasexpectedoftype(string->string)->stringTypestringisnotcompatiblewithtypestring->string

Functions having type(string -> string) -> string take a function as a parameter. The functionsweet_cat has a function as a result, not a function as a parameter.

The type arrow operatorassociates to the right. Function types without parentheses should be treated as if they have parentheses to the right in the same way that the type ofdummy_cat was declared above. Except they are not displayed.

Tuples as Function Parameters

In OCaml, atuple is a data structure used to group a fixed number of values, which can be of different types. Tuples are surrounded by parentheses, and the elements are separated by commas. Here's the basic syntax to create and work with tuples in OCaml:

#("felix",1920);;-:string*int=("felix",1920)

It is possible to use the tuple syntax to specify function parameters. Here is how it can be used to define yet another version of the running example:

#letspicy_cat(x,y)=x^""^y;;valspicy_cat:string*string->string=<fun>#spicy_cat("hello","world");;-:string="hello world"

It looks like two arguments have been passed:"hello" and"world". However, only one, the("hello", "world") tuple, has been passed. Inspection of the generated assembly would show it isn't the same function assweet_cat. It contains some more code. The contents of the tuple passed tospicy_cat (x andy) must be extracted before evaluation of thex ^ " " ^ y expression. This is the role of the additional assembly instructions.

In many imperative languages, thespicy_cat ("hello", "world") syntax reads as a function call with two arguments; but in OCaml, it denotes applying the functionspicy_cat to a tuple containing"hello" and"world".

Currying and Uncurrying

In the previous sections, two kinds of multiple-parameter functions have been presented.

• Functions returning a function, such assweet_cat andsour_cat
• Functions taking a tuple as a parameter, such asspicy_cat

Interestingly, both kinds of functions provide a way to pass several pieces of data while being functions with a single parameter. From this perspective, it makes sense to say: “All functions have a single argument.”

This goes even further. It is always possible to translate back and forth between functions that look likesweet_cat (orsour_cat) and functions that look likespicy_cat.

These translations have names:

• Currying goes from thespicy_cat form into thesour_cat (orsweet_cat) form.
• Uncurrying goes from thesour_cat (orsweet_cat) form into thespicy_cat form.

It also said thatsweet_cat andsour_cat arecurried functions whilstspicy_cat isuncurried.

Functions with the following types can be translated back and forth:

• string -> (string -> string) — curried function type
• string * string -> string — uncurried function type

These translations are attributed to the 20th-century logicianHaskell Curry.

Here, this is shown usingstring as an example, but it applies to any group of three types.

You can change the curried form into the uncurried form when refactoring, or the other way round.

However, it is also possible to implement one from the other to have both forms available:

#letuncurried_cat(x,y)=sweet_catxy;;valuncurried_cat:string*string->string=<fun>#letcurried_catxy=uncurried_cat(x,y);;valcurried_cat:string->string->string=<fun>

In practice, curried functions are the default because:

• They allow partial application
• No parentheses or commas
• No pattern matching over a tuple takes place

Functions With Side Effects

To explain side effects, we need to define whatdomain andcodomain are. Let's look at an example:

#string_of_int;;-:int->string=<fun>

For the functionstring_of_int:

• Itsdomain isint, the type of its parameters
• Thecodomain isstring, the type of its results

In other words, thedomain is left of the-> and thecodomain is on the right. These terms help avoid saying the "type at the right" or "type at the left" of a function's type arrow.

Some functions operate on data outside of their domain or codomain.This behaviour is called an effect, or a side effect.

Doing input and output (I/O) with the operating system is the most common form of side effects. The result of functions returning random numbers (such asRandom.bits does) or the current time (such asUnix.time does) is influenced by external factors, which is also called an effect.

Similarly, any observable phenomena triggered by the computation of a function is an out-of-codomain output.

In practice, what is considered an effect is an engineering choice. In most circumstances, system I/O operations are considered as effects, unless they are ignored. The heat emitted by the processor when computing a function isn't usually considered a relevant side-effect, except when considering energy-efficient design.

In the OCaml community, as well as in the wider functional programming community, functions are often said to be eitherpure or impure. The former does not have side effects, the latter does. This distinction makes sense and is useful. Knowing what the effects are, and when are they taking place, is a key design consideration. However, it is important to remember this distinction always assumes some sort of context. Any computation has effects, and what is considered a relevant effect is a design choice.

Since, by definition, effects lie outside function types, a function type can't reflect a function's possible effects. However, it is important to document a function's intended side effects. Consider theUnix.time function. It returns the number of seconds elapsed since January 1, 1970.

#Unix.time;;-:unit->float=<fun>

Note: If you're getting anUnbound module error in macOS, run this first:#require "unix";;.

The result of theUnix.time function is determined only by external factors. To perform the side effect, the function must be applied to an argument. Since no data needs to be passed, the argument is the() value.

Considerprint_endline. It prints the string it was passed to standard output, followed by a line termination.

#print_endline;;-:string->unit=<fun>

Since the purpose of the function is only to produce an effect, it has no meaningful data to return; it returns the() value.

This illustrates the relationship between functions that have side effects and theunit type. The presence of theunit type does not indicate the presence of side effects. The absence of theunit type does not indicate the absence of side effects. But when no data needs to be passed as input or can be returned as output, theunit type is used.

What Makes Functions Different From Other Values

Functions are like other values; however, there are restrictions:

1. Function values cannot be displayed in interactive sessions. The placeholder<fun> is displayed instead. This is because there is nothing meaningful to print. Once parsed and typed-checked, OCaml discards the function's source code and nothing remains to be printed.

#sqrt;;-:float->float=<fun>

1. Equality between functions can't be tested.

#pred;;-:int->int=<fun>#succ;;-:int->int=<fun>#pred=succ;;Exception:Invalid_argument"compare: functional value".

There are two main reasons explaining this:

• There is no algorithm that takes two functions and determines if they return the same output when provided the same input.
• Assuming it was possible, such an algorithm would declare that implementations of quicksort and bubble sort are equal. That would mean one could replace the other, and that may not be wise.

Conclusion

At the heart of OCaml lies the concept of the environment. The environment works as an ordered, append-only, key-value store. This means that items cannot be removed. Furthermore, it maintains order by preserving the sequence of available definitions.

When we use alet statement, we introduce zero, one, or more name-value pairs into the environment. Similarly, when applying a function to some arguments, we extend the environment by adding names and values corresponding to its arguments.