This post covers some of the major features of OCaml while solving Problem 1 from Project Euler.

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Let’s get started on this problem by looking at the math facilities provided by
OCaml. Start a new interactive session using `utop`

.

```
$ utop
```

Now we can play with some math. Note that to end a statement in OCaml you use
not one, but two, semi-colons (`;;`

). This is a peculiarity of an OCaml
interactive environment and not necessary for standalone compiled programs.

## Integers and Floats

```
utop # 2 + 3;;
- : int = 5
```

Our problem asks us to find multiples of natural numbers, which are divide with a remainder of zero.

```
utop # 9 / 3;;
- : int = 3
utop # 5 / 5;;
- : int = 1
utop # 10 / 3;;
- : int = 3
utop # 10.0 / 3.0;;
- : int = 3
```

Trying this a few times, we can see that the division operator `/`

on values of
type `int`

(integers) returns a value of type `int`

and ignores the remainder.
In fact, the `/`

operator is only valid for integer types. Try it on values of
type `float`

:

```
utop # 10.0 / 3.0 ;;
Line 1, characters 0-4:
Error: This expression has type float but an expression was expected of type
int
```

OCaml uses notation to distinguish between `float`

and `int`

. Numeric literals
followed by a `.`

are of type `float`

, and infix operators followed by a `.`

are
of type `float`

. For example, the expression `2.5 +. 6.`

is valid, whereas the
expression `2.5 +. 6`

fails type checking because the literal `6`

is of type
`int`

not `float`

(i.e. we forgot the `.`

after `6`

). Thankfully, the compiler
is at least kind enough to give us a hint:

```
utop # 2.5 +. 6. ;;
- : float = 8.5
utop # 2.5 +. 6 ;;
Line 1, characters 7-8:
Error: This expression has type int but an expression was expected of type
float
Hint: Did you mean `6.'?
```

In general, OCaml requires you to be explicit about the numeric types you use.

## Let Bindings and Variables

To solve our problem, we will likely need some variables for remembering the
value of certain expressions. In OCaml, the `let`

keyword creates a *binding*
between a value and a name. For example, to give the value of the expression `4 + 3`

the name `x`

we use a let binding that we can refer to later:

```
# let x = 4 + 3;;
val x : int = 7
# let y = 5 + 2;;
val y : int = 7
# x + y;;
- : int = 14
```

The only gotcha with OCaml syntax is that variables must start with a lowercase letter — uppercase notation is reserved for constructors.

```
# let X = 4 + 3;;
Line 1, characters 4-5:
Error: Unbound constructor X
```

Functions are also defined using let bindings. In OCaml, functions are
first-class and are treated like any other value — there is no difference
between using a let binding to name a value and using one to name a function. In
OCaml, function arguments are separated by spaces instead of by a combination of
parentheses and commas. The following let binding creates the variable named
`square`

and refers that variable to a function taking an integer variable `x`

and computing `x * x`

:

```
# let square x = x * x;;
val square : int -> int = <fun>
```

The OCaml compiler was able to intuit the type of our function by the type of
the parameters and return value. Here, `int -> int`

is a function type
indicating that the parameter to the function is of type `int`

and that the
return value from the function is also of type `int`

.

## Lists

We will need to iterate over the numbers up to `1000`

to solve our problem,
which makes the `List`

module useful. Within the `List`

module, we can access
the `range`

function to create a sequence of numbers between a range:

```
# List.range 1 1000;;
- : int list =
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21; 22;
23; 24; 25; 26; 27; 28; 29; ...]
```

Filtering is a common operation in functional programming that condenses a list
to include only values that meet certain criteria. To do this, we require a function
that returns a boolean stating whether or not our criteria for list inclusion is
met. For our problem, that criteria is whether or not a number is cleanly
divisible by three or five. Here, I introduce the `%`

operator which returns the
remainder of division, the boolean equality infix operator `=`

, and the logical
OR operator `||`

. The type signature of our function shows that it takes a
parameter of type `int`

and returns value of type `bool`

.

```
# let is_multiple x = (x % 3 = 0 || x % 5 = 0);;
val is_multiple : int -> bool = <fun>
```

We can use `is_multiple`

to test if values are divisible by three or five:

```
# is_multiple 10;;
- : bool = true
# is_multiple 8;;
- : bool = false
```

Now let’s take a closer look at how to filter our list using the `filter`

function. Calling the function with no arguments from `utop`

gives us a hint at
how to use the function by examining it’s type signature.

```
# List.filter;;
- : 'a list -> f:('a -> bool) -> 'a list = <fun>
```

Type signatures take some practice to read. This one states that `filter`

is a
function of two arguments: `'a list`

which is a list of unknown or generic type
(`'a`

), and a function `f`

that takes a parameter of the same type of the list
(`'a`

) and returns a `bool`

(this is our `is_multiple`

function).

```
'a list * a list of type 'a
f:('a -> bool) * a function with parameter type 'a returning type bool
'a list * a list of type 'a
```

This type signature also introduces the concept of *named* or *labeled*
arguments. You will notice the notation `f:`

in the function signature. This
notation assigns a label to the parameter and allows us to pass a labeled
argument that gets passed to the correct label in the function signature using
`~`

syntax. Labeled arguments have no concept of position and can be used
anywhere when calling the function. For example, the following are equivalent:

```
List.filter ~f:is_multiple [10; 9; 8];;
- : int list = [10; 9]
List.filter [10; 9; 8] ~f:is_multiple;;
- : int list = [10; 9]
```

Note that in OCaml, list members are separated by `;`

, not `,`

!

## Solving Problem 1

We now have enough OCaml under our belts to solve Problem 1 of Project Euler. We
can start by combining `List.range`

, `List.filter`

, and `is_multiple`

to create
a list of integers that are multiples of 3 and 5:

```
# let is_multiple x = (x % 3 = 0 || x % 5 = 0);;
# List.filter (List.range 1 1000) ~f:is_multiple;;
```

What’s left is to sum the result, which can be done using the `List.fold`

function from the Base
module.
In functional programming, the concept of folding over a list applies a function
to each element of the list recursively, starting with a base condition. For
addition, we take each element of the list, apply the addition function, and
then call `fold`

on the rest of the list. For example, if we have the list `[1; 2; 3]`

and an initial condition `0`

, folding the list using addition can be
expanded in a simplified way as:

```
List.fold ~f:(+) ~init:0 [1; 2; 3];;
List.fold ~f:(+) ~init:(0 + 1) [2; 3];;
List.fold ~f:(+) ~init:(0 + 1 + 2) [3];;
List.fold ~f:(+) ~init:(0 + 1 + 2 + 3) [];;
```

Since there are no more elements in the list, the folding operation is complete and we can return the summation. We can now add folding to our solution to finish Project Euler’s problem 1.

```
# let is_multiple x = (x % 3 = 0 || x % 5 = 0);;
# List.fold ~f:(+) ~init:0 (List.filter (List.range 1 1000) ~f:is_multiple);;
- : int = 233168
```