Is this idiomatic F# for a fairly quick infinite recursive sequence?

Question

Whilst solving the 12th project euler problem I set about making an infinite sequence to get successive triangular numbers. My first attempt was:

let slowTriangularNumbers =

  let rec triangularNumbersFrom n = 
    seq { 
      yield seq { 0 .. n } |> Seq.sum
      yield! triangularNumbersFrom (n + 1) 
    }

   triangularNumbersFrom 1

This turned out to be very slow - each time getting the next item it had to compute all of the additions leading up to n.

My next attempt was:

let fasterTriangularNumbers =

  let cache = System.Collections.Generic.Dictionary<int, int>()
  cache.[0] <- 0         

  let rec triangularNumbersFrom n = 
  seq { 
    cache.[n] <- cache.[n - 1] + n                   
    yield cache.[n]
    yield! triangularNumbersFrom (n + 1) 
  }

  triangularNumbersFrom 1

Introducing the mutable dictionary has speeded it up considerably, but is this normal to have a mutable collection, or is there another way I could have represented state?

Answer 1

I think this is more idiomatic:

Seq.unfold (fun (i, n) -> Some(n, (i+1, n+i))) (2, 1)

You might prefer this alternative:

seq { 2 .. System.Int32.MaxValue }
|> Seq.scan (+) 1