f# - 这是一个相当快速的无限递归序列的惯用 F# 吗？

Question

在解决第 12 个项目欧拉问题时，我着手制作一个无限序列来获得连续的三角形数。我的第一次尝试是：

let slowTriangularNumbers =

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

   triangularNumbersFrom 1

结果证明这非常慢 - 每次获取下一个项目时，它都必须计算导致 . 的所有加法n。

我的下一个尝试是：

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

引入可变字典已经大大加快了它的速度，但是拥有一个可变集合是正常的，还是有另一种方法可以表示状态？

Answer 1

我认为这是更惯用的：

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

您可能更喜欢这种选择：

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