Which Style to Choose?
This is no matter of religion or esthetics; a priori
neither style is prettier or holier than the other. On the contrary,
one style may be more adequate than the other depending on the problem
to be solved.
The first rule to apply is the rule of simplicity. Whether the
algorithm to use implemented is written in a book, or whether its seed
is in the mind of the programmer, the algorithm is itself described in
a certain style. It is natural to use the same style when
implementing it.
The second criterion of choice is the efficiency of the program. One
may say that an imperative program (if well written) is more efficient
that its functional analogue, but in very many cases the difference is
not enough to justify complicating the code to adopt an imperative
style where the functional style would be natural. The function
map in the previous section is a good example of a problem
naturally expressed in the functional style, which gains nothing from
being written in the imperative style.
Sequence or Composition of Functions
We have seen that as soon as a program causes side effects, it is
necessary to determine precisely the order of evaluation for the
elements of the program. This can be done in both styles:

functional:
 using the fact that Objective CAML is a strict
language, which means that the argument is evaluated before applying
the function. The expression (f
(g
x)) is computed by
first evaluating (g
x), and then passing the result as
argument to f. With more complex expressions, we can name an
intermediate result with the let in construction, but the idea
remains the same:
let
aux=
(g
x)
in
(f
aux).
 imperative:
 using sequences or other control structures
(loops). In this case, the result is not the value returned by a
function, but its side effects on memory:
aux
:=
(g
x)
;
(f
!
aux).
Let us examine this choice of style on an example. The quick
sort algorithm, applied to a vector, is described recursively as
follows:

Choose a pivot: This is the index of an element of the vector;
 Permute around the pivot: Permute the elements of the vector so
elements less than the value at the pivot have indices less than the
pivot, and vice versa;
 sort the subvectors obtained on each side of the pivot, using
the same algorithm: The subvector preceding the pivot and the
subvector following the pivot.
The choice of algorithm, namely to modify a vector so that its
elements are sorted, incites us to use an imperative style at least to
manipulate the data.
First, we define a function to permute two elements of a vector:
# let
permute_element
vec
n
p
=
let
aux
=
vec.
(n)
in
vec.
(n)
<
vec.
(p)
;
vec.
(p)
<
aux
;;
val permute_element : 'a array > int > int > unit = <fun>
The choice of a good pivot determines the efficiency of the algorithm,
but we will use the simplest possible choice here: return the index
of the first element of the (sub)vector.
# let
choose_pivot
vec
start
finish
=
start
;;
val choose_pivot : 'a > 'b > 'c > 'b = <fun>
Let us write the algorithm that we would like to use to permute the
elements of the vector around the pivot.

Place the pivot at the beginning of the vector to be
permuted;
 Initialize i to the index of the second element of the vector;
 Initialize j to the index of the last element of the vector;
 If the element at index j is greater than the pivot, permute
it with the element at index i and increment i; otherwise,
decrement j;
 While i<j, repeat the previous operation;
 At this stage, every element with index <i (or equivalently,
j) is less than the pivot, and all others are greater; if the
element with index i is less than the pivot, permute it with
the pivot; otherwise, permute its predecessor with the pivot.
In implementing this algorithm, it is natural to adopt imperative
control structures.
# let
permute_pivot
vec
start
finish
ind_pivot
=
permute_element
vec
start
ind_pivot
;
let
i
=
ref
(start+
1
)
and
j
=
ref
finish
and
pivot
=
vec.
(start)
in
while
!
i
<
!
j
do
if
vec.
(!
j)
>=
pivot
then
decr
j
else
begin
permute_element
vec
!
i
!
j
;
incr
i
end
done
;
if
vec.
(!
i)
>
pivot
then
decr
i
;
permute_element
vec
start
!
i
;
!
i
;;
val permute_pivot : 'a array > int > int > int > int = <fun>
In addition to its effects on the vector, this function returns the
index of the pivot as its result.
All that remains is to put together the different stages and add the
recursion on the subvectors.
# let
rec
quick
vec
start
finish
=
if
start
<
finish
then
let
pivot
=
choose_pivot
vec
start
finish
in
let
place_pivot
=
permute_pivot
vec
start
finish
pivot
in
quick
(quick
vec
start
(place_pivot
1
))
(place_pivot+
1
)
finish
else
vec
;;
val quick : 'a array > int > int > 'a array = <fun>
We have used the two styles here. The chosen pivot serves as argument
to the permutation around this pivot, and the index of the pivot after
the permutation is an argument to the recursive call. By contrast,
the vector obtained after the permutation is not returned by the
permute_pivot function; instead, this result is produced by
side effect. However, the quick function returns a vector,
and the sorting of subvectors is obtained by composition of recursive
calls.
The main function is:
# let
quicksort
vec
=
quick
vec
0
((Array.length
vec)
1
)
;;
val quicksort : 'a array > 'a array = <fun>
It is a polymorphic function because the order relation < on
vector elements is itself polymorphic.
# let
t1
=
[
4
;8
;1
;1
2
;7
;3
;1
;9
]
;;
val t1 : int array = [4; 8; 1; 12; 7; 3; 1; 9]
# quicksort
t1
;;
 : int array = [1; 1; 3; 4; 7; 8; 9; 12]
# t1
;;
 : int array = [1; 1; 3; 4; 7; 8; 9; 12]
# let
t2
=
[
"the"
;
"little"
;
"cat"
;
"is"
;
"dead"
]
;;
val t2 : string array = ["the"; "little"; "cat"; "is"; "dead"]
# quicksort
t2
;;
 : string array = ["cat"; "dead"; "is"; "little"; "the"]
# t2
;;
 : string array = ["cat"; "dead"; "is"; "little"; "the"]
Shared or Copy Values
When the values that we manipulate are not mutable, it does not matter
whether they are shared or not.
# let
id
x
=
x
;;
val id : 'a > 'a = <fun>
# let
a
=
[
1
;
2
;
3
]
;;
val a : int list = [1; 2; 3]
# let
b
=
id
a
;;
val b : int list = [1; 2; 3]
Whether b is a copy of the list a or the very same
list makes no difference, because these are intangible values anyway.
But if we put modifiable values in place of integers, we need to know
whether modifying one value causes a change in the other.
The implementation of polymorphism in Objective CAML causes immediate values
to be copied, and structured values to be shared. Even though
arguments are always passed by value, only the pointer to a structured
value is copied. This is the case even in the function id:
# let
a
=
[
1
;
2
;
3
]
;;
val a : int array = [1; 2; 3]
# let
b
=
id
a
;;
val b : int array = [1; 2; 3]
# a.
(1
)
<
4
;;
 : unit = ()
# a
;;
 : int array = [1; 4; 3]
# b
;;
 : int array = [1; 4; 3]
We have here a genuine programming choice to decide which is the most
efficient way to represent a data structure. On one hand, using
mutable values allows manipulations in place, which means without
allocation, but requires us to make copies sometimes when immutable
data would have allowed sharing. We illustrate this here with two
ways to implement lists.
# type
'a
list_immutable
=
LInil

LIcons
of
'a
*
'a
list_immutable
;;
# type
'a
list_mutable
=
LMnil

LMcons
of
'a
*
'a
list_mutable
ref
;;
The immutable lists are strictly equivalent to lists built into
Objective CAML, while the mutable lists are closer to the style of C, in
which a cell is a value together with a reference to the following cell.
With immutable lists, there is only one way to write concatenation,
and it requires duplicating the structure of the first list; by
contrast, the second list may be shared with the result.
# let
rec
concat
l1
l2
=
match
l1
with
LInil
>
l2

LIcons
(a,
l11)
>
LIcons(a,
(concat
l11
l2))
;;
val concat : 'a list_immutable > 'a list_immutable > 'a list_immutable =
<fun>
# let
li1
=
LIcons(1
,
LIcons(2
,
LInil))
and
li2
=
LIcons(3
,
LIcons(4
,
LInil))
;;
val li1 : int list_immutable = LIcons (1, LIcons (2, LInil))
val li2 : int list_immutable = LIcons (3, LIcons (4, LInil))
# let
li3
=
concat
li1
li2
;;
val li3 : int list_immutable =
LIcons (1, LIcons (2, LIcons (3, LIcons (4, LInil))))
# li1==
li3
;;
 : bool = false
# let
tlLI
l
=
match
l
with
LInil
>
failwith
"Liste vide"

LIcons(_,
x)
>
x
;;
val tlLI : 'a list_immutable > 'a list_immutable = <fun>
# tlLI(tlLI(li3))
==
li2
;;
 : bool = true
From these examples, we see that the first cells of li1 and
li3 are distinct, while the second half of li3 is
exactly li2.
With mutable lists, we have a choice between modifying arguments
(function concat_share) and creating a new value (function
concat_copy).
# let
rec
concat_copy
l1
l2
=
match
l1
with
LMnil
>
l2

LMcons
(x,
l11)
>
LMcons(x,
ref
(concat_copy
!
l11
l2))
;;
val concat_copy : 'a list_mutable > 'a list_mutable > 'a list_mutable =
<fun>
This first solution, concat_copy, gives a result similar to
the previous function, concat. A second solution shares its
arguments with its result fully:
# let
concat_share
l1
l2
=
match
l1
with
LMnil
>
l2

_
>
let
rec
set_last
=
function
LMnil
>
failwith
"concat_share : impossible case!!"

LMcons(_,
l)
>
if
!
l=
LMnil
then
l:=
l2
else
set_last
!
l
in
set_last
l1
;
l1
;;
val concat_share : 'a list_mutable > 'a list_mutable > 'a list_mutable =
<fun>
Concatenation with sharing does not require any allocation, and
therefore does not use the constructor LMcons. Instead, it
suffices to cause the last cell of the first list to point to the
second list. However, this version of concatenation has the potential
weakness that it alters arguments passed to it.
# let
lm1
=
LMcons(1
,
ref
(LMcons(2
,
ref
LMnil)))
and
lm2
=
LMcons(3
,
ref
(LMcons(4
,
ref
LMnil)))
;;
val lm1 : int list_mutable =
LMcons (1, {contents=LMcons (2, {contents=LMnil})})
val lm2 : int list_mutable =
LMcons (3, {contents=LMcons (4, {contents=LMnil})})
# let
lm3
=
concat_share
lm1
lm2
;;
val lm3 : int list_mutable =
LMcons (1, {contents=LMcons (2, {contents=LMcons (...)})})
We do indeed obtain the expected result for lm3. However,
the value bound to lm1 has been modified.
# lm1
;;
 : int list_mutable =
LMcons (1, {contents=LMcons (2, {contents=LMcons (...)})})
This may therefore have consequences on the rest of the program.
How to Choose your Style
In a purely functional program, side effects are forbidden, and this
excludes mutable data structures, exceptions, and input/output. We
prefer, though, a less restrictive definition of the functional style,
saying that functions that do not modify their global environment may
be used in a functional style. Such a function may manipulate mutable
values locally, and may therefore be written in an imperative style,
but must not modify global variables, nor its
arguments. We permit them to raise exceptions in addition. Viewed
from outside, these functions may be considered ``black boxes.''
Their behavior matches a function written in a purely functional
style, apart from being able of breaking control flow by raising an
exception. In the same spirit, a mutable value which can no longer be
modified after initialization may be used in a functional style.
On the other hand, a program written in an imperative style still benefits
from the advantages provided by Objective CAML: static type safety,
automatic memory management, the exception mechanism, parametric
polymorphism, and type inference.
The choice between the imperative and functional styles depends on the
application to be developed. We may nevertheless suggest some guidelines
based on the character of the application, and the criteria
considered important in the development process.

choice of data structures: The choice whether to use
mutable data structures follows from the style of programming
adopted. Indeed, the functional style is essentially incompatible
with modifying mutable values. By contrast, constructing and
traversing objects are the same whatever their status. This touches
the same issue as ``modification in place vs copying'' on
page ??; we return to it again in
discussing criteria of efficiency.
 required data structures: If a program must modify mutable data structures, then the imperative
style is the only one possible. If, on the other hand,
you just have to traverse values, then adopting the functional
style guarantees the integrity of the data.
Using recursive data structures requires the use of functions that are
themselves recursive. Recursive functions may be defined using either
of the two styles, but it is often easier to understand the creation
of a value following a recursive definition, which corresponds to a
functional approach, than to repeat the recursive processing on this
element. The functional style allows us to define generic iterators over the
structure of data, which factors out the work of development and makes
it faster.
 criteria of efficiency: Modification in place is far
more efficient than creating a value. When code efficiency is the
preponderant criterion, it will usually tip the balance in favor of
the imperative style. We note however that the need to avoid sharing
values may turn out to be a very hard task, and in the end costlier
than copying the values to begin with.
Being purely functional has a cost. Partial application and using
functions passed as arguments from other functions has an execution
cost greater than total application of a function whose declaration is
visible. Using this eminently functional feature must thus be
avoided in those portions of a program where efficiency is crucial.
 development criteria: the higher level of abstraction of
functional programs permits them to be written more quickly, leading
to code that is more compact and contains fewer errors than the
equivalent imperative code, which is generally more verbose. The
functional style is better suited to the constraints imposed by
developing substantial applications. Since each function is not dependent upon its evaluation context,
functional can be easily divided into small units that can be examined
separately; as a consequence, the code is easier to read.
Programs written using the functional style are more easily reusable
because of its better modularity, and because functions may be passed
as arguments to other functions.
These remarks show that it is often a good idea to mix the two
programming styles within the same application. The functional
programming style is faster to develop and confers a simpler
organization to an application. However, portions whose execution
time is critical repay being developed in a more efficient imperative
style.