无限的斐波那契序列

Question

我试图用F序模仿Haskell在F#中着名的无限斐波纳契列表.为什么以下序列没有按预期进行评估？它是如何评估的？

let rec fibs = lazy (Seq.append 
                        (Seq.ofList [0;1]) 
                        ((Seq.map2 (+) (fibs.Force()) 
                                       (Seq.skip 1 (fibs.Force())))))

Answer 1

问题是你的代码仍然不够懒惰:在Seq.append访问结果之前评估参数,但是评估第二个参数(Seq.map2 ...)需要评估它自己的参数,这会强制定义相同的惰性值.这可以通过使用该Seq.delay函数来解决.你也可以放弃lazy包装器,lists已经seq是s,所以你不需要Seq.ofList:

let rec fibs = 
    Seq.append [0;1]
        (Seq.delay (fun () -> Seq.map2 (+) fibs (Seq.skip 1 fibs)))

但是,我个人建议使用一个序列表达式,我发现它更令人愉快(更容易正确编写):

let rec fibs = seq {
    yield 0
    yield 1
    yield! Seq.map2 (+) fibs (fibs |> Seq.skip 1)
}

Answer 2

要添加到kvb答案,您还可以使用Seq.unfold生成(懒惰)序列:

let fibs = Seq.unfold (fun (a, b) -> Some(a+b, (b, a+b))) (0, 1)

val fibs:seq <int>