F#中的递归序列

Question

假设我想计算整数的阶乘.F#中一个简单的方法是:

let rec fact (n: bigint) =
    match n with
    | x when x = 0I -> 1I
    | _ -> n * fact (n-1I)

但是,如果我的程序需要动态编程,那么在使用memoization时如何维持函数式编程呢？

我对此有一个想法是制作一系列懒惰元素,但我遇到了一个问题.假设以下代码在F#中是可接受的(它不是):

let rec facts = 
    seq {
        yield 1I
        for i in 1I..900I do 
            yield lazy (i * (facts |> Seq.item ((i-1I) |> int)))
    }

F#中有什么类似的想法吗？(注意:我知道我可以使用.NET Dictionary而不是调用".Add()"方法命令式样式？)

另外,有什么办法可以用函数来概括这个吗？例如,我可以创建一个由函数定义的collat​​z函数的长度序列:

let rec collatz n i = 
    if n = 0 || n = 1 then (i+1)
    elif n % 2 = 0 then collatz (n/2) (i+1) 
    else collatz (3*n+1) (i+1)

Answer 1

如果你想懒洋洋地做,这是一个很好的方法:

let factorials =
    Seq.initInfinite (fun n -> bigint n + 1I)
    |> Seq.scan ((*)) 1I
    |> Seq.cache

这Seq.cache意味着您不会重复评估您已经枚举过的元素.

然后,您可以使用例如特定数量的阶乘Seq.take n,或者使用特定阶乘Seq.item n.