CODEWITHSUNDEEP
f#functional-programmingfibonaccilazy-sequences
is7s
is7s

Reputation: 3480

Infinite fibonacci sequence

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())))))

Upvotes: 8

Views: 1680

Answers (4)

Ed'ka
Ed'ka

Reputation: 7148

Yet another way:

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

Upvotes: 3

Søren Debois
Søren Debois

Reputation: 5688

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).

Upvotes: 2

Mau
Mau

Reputation: 14478

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>

Upvotes: 6

kvb
kvb

Reputation: 55195

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)
}

Upvotes: 9

Related Questions