How to diagnose source of failure in F# interactive

Question

I am learning the ropes of F# through Project Euler, and ran into the following issue a few times. I write a function, run it in the F# interactive window, and the program hangs there. I suspect the function is failing, but I am not getting any significant error message which would help me figure out what is going wrong. Is there any way to debug a program running in F# interactive?
As an illustration, here is an example, from Problem 12. FindFirstTriangle(0,0,100) runs fine, but when the divisor is around 150, things get stuck.
Note: this is not about what is wrong about this code, but about how to figure out where things go wrong!

let NumberOfDivisors n =
  [1 .. n] |> List.filter (fun i -> n % i = 0) |> List.length;;

let HasMoreThanDDivisors n d =
  if NumberOfDivisors n >= d then
    true
  else
    false

let rec FindFirstTriangle (index, number, divisors) =
  if HasMoreThanDDivisors number divisors then
    number
  else
    let nextIndex = index + 1
    let nextNumber = number + index
    FindFirstTriangle (nextIndex, nextNumber, divisors);;

Answer 1

If you have e.g. 'windows task manager' running you'll see that your CPU is running flat out while the thing is hung. You've just created too much work; you need a more efficient algorithm. Press the 'interrupt' key in F# interactive (Ctrl-. in the FSI window in Visual Studio) to stop processing.

If the big-oh isn't clear, you might consider adding some prints to show how much work is being done. E.g.

let NumberOfDivisors n = 
  printf "%d" n // added
  seq {1 .. n} |> Seq.filter (fun i -> n % i = 0) |> Seq.length;; 

let HasMoreThanDDivisors n d = 
  if NumberOfDivisors n >= d then 
    true 
  else 
    false 

let rec FindFirstTriangle (index, number, divisors) = 
  printfn "" // added
  if HasMoreThanDDivisors number divisors then 
    number 
  else 
    let nextIndex = index + 1 
    let nextNumber = number + index 
    FindFirstTriangle (nextIndex, nextNumber, divisors);;

and then run FindFirstTriangle with larger and larger numbers to get a sense of what's happening.

Answer 2

A program hangs usually due to two reasons:

1. dead loop

2. inefficient code

In a FP language, like F#, it is very rare that you write a dead loop that runs forever.

This is my debugging straggle when doing Euler:

1. test each function using small test cases. When you have written a function, test it. It is very unlikely a algorithm works for 1 - 100 and fails at 101 especially when you are using a 'safe' language like F#.

2. estimate the running time of your algorithm. If it is O(n^2), then n=10000 may be the upper limit for your algorithm. In this problem, the answer is over 70M, a brute force O(n^2) algorithm runs forever. And F# interactive provides #time to profile the running behaviors of your program, like running time and number of garbage collections.

As Brain said, you need a more efficient NumberOfDivisors implementation: http://en.wikipedia.org/wiki/Euler%27s_totient_function