f# - Infinite fibonacci sequence

Question

I'm trying to imitate Haskell's famous infinite fibonacci list in F# using sequences. Why doesn't the following sequence evaluate as expected? How is it being evaluated?

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

Answer 1

The problem is that your code still isn't lazy enough: the arguments to Seq.append are evaluated before the result can be accessed, but evaluating the second argument (Seq.map2 ...) requires evaluating its own arguments, which forces the same lazy value that's being defined. This can be worked around by using the Seq.delay function. You can also forgo the lazy wrapper, and lists are already seqs, so you don't need Seq.ofList:

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

However, personally I'd recommend using a sequence expression, which I find to be more pleasant to read (and easier to write correctly):

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

Answer 2

To add to kvb's answer, you can also use Seq.unfold to generate a (lazy) sequence:

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

val fibs : seq<int>

Answer 3

Yet another way:

let rec fib = seq { yield 0; yield! Seq.scan (+) 1 fib }

Answer 4

In addition to @kvb's answer: if you just want lazy and not necessarily the zip trick, you can do this:

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

This makes Seq.take n fibs run in time O(n).