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