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) ;;
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
``````