As already suggested above, you'd better use seq instead of list. I just fired up fsi and got the code below, maybe not as elegant as you expect but should be just fine. Btw, what's the correct answer? I'm too lazy to register to play with euler.

1
2
3
4
5
6
7

> let rec fibs a b =
  { if a > 1000000 then yield! []
    else
      if a%2 = 0 then yield a
      yield! fibs b (a+b) } in
  fibs 1 1 |> Seq.fold1 (+);;
val it : int = 1089154

List's are actually a bad idea for this problem, the reason Seq's are so useful here is that the actual elements of the Seq aren't stored in memory but are calculated as we need them so we never actually store the Fibonacci numbers, which would be a bad thing since we are only interested in the sum. With list's, however, the values are stored by the list so we would be creating a list of one million elements when we don't need to.

Chris's solution in the blog can actually be made slightly simpler, all we are after is the sum smaller then one million so it doesn't actually matter weather the Seq contains one million elements or ten million elements as long as there is enough for the sum to pass one million. In addition, because, Seq's aren't stored in memory there's nothing to stop us from creating an infinite sequence with all of the numbers of the fibonacci sequence (this is mentioned at the end of the blog) so you could just do:

let problem2 =
(1,1)
|> Seq.unfold (fun (n0,n1) -> Some (n0, (n1, n0 + n1)))
|> Seq.fold
(fun acc x ->
if x % 2 = 0 && x < 1000000 then
acc + x
else
acc) 0

Edit: I just noticed I misread the question but I'll leave this post anyway.

First off, I'm glad to see that people actually do read my blog :)

I've written up a quick solution to the generation step:

// Gets the next number in the fibonacci sequence given the previous sequence in reverse

let genNextFib reverseFibs = [List.hd reverseFibs + List.hd (List.tl reverseFibs)] @ reverseFibs

// Generates the first x fibonacci numbers as a list, in reverse

let rec getFibsAsList x =

match x with

| x when x < 1 -> failwith "Error: x must be positive"

| 1 -> [1];

| 2 -> [1;1];

| 3 -> [2;1;1];

| 4 -> [3;2;1;1]

| x -> genNextFib (getFibsAsList (x - 1))

/// Calculates the list of fibonacci numbers less that 1E6

let mutable i = 1

let mutable fibsList = [1]

while fibsList.Head < 1000000 do

fibsList <- getFibsAsList i

i <- i + 1

// Reverse it

fibsList <- List.rev fibsList

The biggest challenge when working with lists is to avoid unnessecarily itterating through the elements (wasting time) and to take advantage of tail recursion (wasting stack space). Consider the following code (but please, don't put it into fsi.exe!)

let rec getLastTwoOfList list =

match list with

| first :: second :: [] -> (first, second)

| first :: second :: third -> getLastTwoOfList list.Tail

| _ -> failwith "List should have at least two elements."

(* Don't use this, will chew up stack space and crash fsi.exe!*)

let rec getFibList x =

match x with

| high when high > 100 -> failwith "Will cause stack overflow..."

| _ when x < 1 -> failwith "Error: x must be positive"

| 1 -> [1]

| 2 -> [1;1]

| 3 -> [1;1;2]

| 4 -> [1;1;2;3]

| x -> let allFibsBefore = getFibList (x - 1)

let (x_minus_1, x_minus_2) = getLastTwoOfList allFibsBefore

allFibsBefore @ [x_minus_1 + x_minus_2]

Although perhaps a tad easier to understand and read, the problem here is that 1.) it is slow. Notice that since the fib list is kept in order, to get the last two elements you are forced to walk through each element of the list. Which is on order O(n^2) to generate the first n elements. Also, it isn't tail recursive so you run the risk of a StackOverflow. (Jomo's Blog has a great post on Tail Recursion.)

Hope that helps!

-Chris