## Project Euler 1 in F# using Sequences

I have written previously about solving the first problem on the Project Euler website using F# and Haskell.

The problem is to find the sum of the natural numbers that are divisible by 3 or 5 that are less than 1000. To solve this in F#, my first solution looked like this:

```[0..999]
|> List.filter (fun x -> x % 3 = 0 || x % 5 = 0)
|> List.sum```

This works. However, it was pointed out to me that using lists to generate the numbers below 1000 in my F# solution was memory hungry as the list will be created and stored in memory then piped to the filter and so on. The list is evaluated eagerly. This isn’t a problem with a small list like this, but it could create issues with more elements.

I took a look at sequences in F#, which are evaluated lazily. To get an idea of what this means, consider the sequence of natural numbers:

```let countingNumbers =
seq {
for i in 1 .. System.Int32.MaxValue do
printfn "Yielding: %d" i
yield i
}```

If you are unfamiliar with lazy evaluation, it might look like this will create all the natural numbers up to System.Int32.MaxValue (2147483647) and print each number as it goes. However, if you run this with F# Interactive (aka `fsi`), it creates a `seq<int>` without printing anything out. At this point, the sequence is yet to be enumerated.

The ingenious thing about sequences is that we can work with them without enumerating them. Consider these lines:

```let max = 999
let firstUpToMax = Seq.take max countingNumbers```

The `Seq.take` function allows us to take the first elements in a sequence. However, running these lines in `fsi` does not cause the `for` loop in the sequence above to be run. The print and yield statements are not run.

F#’s ability to delay enumeration is not limited to sequences. Queries also allow us to describe a sequence of numbers without enumerating them.

I define the following function that will be used to filter the sequence:

```let isDivisibleBy3Or5 x =
x % 3 = 0 || x % 5 = 0```

and then create this query:

```let divisibleBy3Or5 =
query {
for countingNumber in firstUpToMax do
where (isDivisibleBy3Or5 countingNumber)
select countingNumber
}```

Programmers who are familiar with SQL or LINQ should have no problem understanding this query. In plain English, we might say “we will go through the sequence and find the values that match the given criterion.” Note the use of the future tense. Running this code in `fsi` does not result in enumeration of our sequence and the printing of the “Yielding…” lines.

I could find the sum of the numbers matching our criteria using a built in function like this:

`let seqSum = Seq.sum divisibleBy3Or5`

This will cause the sequence to be enumerated and finds the same sum as the list method above.

However, by defining the following function:

```let noisySum total next =
printfn "Adding %d to %d" next total
total + next```

I will be able to see the order in which the sequence is enumerated and when the values are pumped down the pipeline to be folded into the sum.

```let seqFoldSum =
divisibleBy3Or5
|> Seq.fold noisySum 0```

At this point we get the following out put at `fsi`:

```Yielding: 1
Yielding: 2
Yielding: 3
Yielding: 4
Yielding: 5
Yielding: 6
...
Yielding: 996
Yielding: 997
Yielding: 998
Yielding: 999