F# - how to write nested loops in a recursive way?

Question

Given the following C# code:

var product = new List<int>();
for (int n1 = 100; n1 < 1000; n1++)
{
    for (int n2 = 100; n2 < 1000; n2++)
    {
        product.Add(n1 * n2);
    }
 }

What would be the equivalent F# code written in a functional style?

Answer 1

I would just write it that way with the for-loops. Even a Haskell programmer would probably express this with a list comprehension, in which case you could write e.g.

let productsList =
    [for x in 2..4 do
     for y in 2..4 do
     yield x*y]

in F#.

Answer 2

Hi, the solution that Brian suggests is definitely the best option (in F#). Sequence expressions give you an easier way to express what you mean, so why not use them?

Anyway, if you're doing this just as an excercise, then you can rewrite the nested loop as single recursive function and the outer loop as second (as Imagist suggests):

let product = 
  let rec outer(n1) = 
    let rec nested(n2) = 
      if n2 > 4 then [] else (n1 * n2)::(nested(n2 + 1))
    if n1 > 4 then [] else nested(2) @ outer(n1 + 1)
  outer(2)

I'm using :: in the nested function to append elements to the beginning and @ to concatenate lists generated by individual nested function calls. The use of @ isn't very efficient and the code also isn't tail-recursive, so better version using accumulator parameter would look like this:

let product = 
  let rec outer n1 acc = 
    let rec nested n2 acc = 
      if n2 > 4 then acc else nested (n2 + 1) ((n1 * n2)::acc)
    if n1 > 4 then acc else outer (n1 + 1) (nested 2 acc)
  outer 2 [] |> List.rev

Hope this helps!