# Infinite lazy fibonacci stream

What i want to do is the following:
-Create a stream
-Use a generator function (a,b)->(b,a+b) for the next element.
-Create an infinite stream of numbers.
-Take and evaluate (force) the first 20 of it.
-Print the first 20 elements.

I know this can be done in a few lines. But once I know how to do this on a short program i can apply this knowledge for something more complicated. Could someone provide this snippet ?

You could start from this and add some laziness

I won’t implement the entire code here but I will point you to the `Seq` module in the standard library, it has everything you need. Specifically, the `unfold`, `take`, and `iter` functions will do the job.

EDIT: `take` was added in OCaml version 4.14, so if you don’t want to upgrade yet, you can use the `oseq` library which also implements the same function.

Currently on Ocaml version 4.11.2. I’ll check seq.
An easier problem is an infinite sequence of natural numbers which i will try first.
But i don’t know here to start. Links ?

No examples,
https://v2.ocaml.org/api/Seq.html

Did you check the documentation of the `unfold` function? There is an example there. I recommend running it and playing around with it to see how it works.

I found this snippet but it’s using jane-street API,

``````let natural_numbers =
Base.Sequence.unfold ~init:0 ~f:(fun state ->
Some ( state     (* yield an element*)
, state + 1 (* next state *)
))
``````

Also there i am clueless

For the seq.unfold i tried

``````let _ =
let helper x = match x with
| [] -> None
| h::t -> Some (h::t) in
Seq.unfold helper 1::2::[] in
``````

But I have the wrong types …

Yup, that’s just an example of converting an existing list to a seq. In your case you want to unfold a new seq of Fibonacci numbers ‘out of nothing’, i.e. you are generating them from the initial numbers in the sequence: 0, 1,…

If we look at the type of `Seq.unfold`:

``````val unfold : ('b -> ('a * 'b) option) -> 'b -> 'a t
``````

We know we want a Fibonacci sequence, so presumably we want an `int Seq.t`, so in this case `'a = int`. The other thing to figure out is the type of `'b`. We said above that we can generate the entire Fibonacci sequence from the initial two numbers in the sequence, and `unfold` takes an unfolding function and an initial argument of type `'b`. This suggests that `'b = int * int` (other types are possible but this is the simplest one). So finally, the unfolding function that we pass as the first argument needs to take a pair of ints and return an option of (next number in the sequence, (previous number, number before previous number)).

After that we can use `Seq.take` and `Seq.iter` to handle the sequence.

I’m slowly closing in,

``````let _ =
let helper = fun z -> match z with
| (a,b)-> Some (a,(b,a+b)) in
let u = Seq.unfold helper (0,1) in
let t = Seq.take 7 u in  (*Unbound seq.take *)
let _ = Seq.iter print_int t in
()
``````

I think i need to explicitly write the “take”

As I mentioned earlier,

On 4.14 next worked perfectly,

``````let _ =
let helper z = match z with a, b -> Some (a, (b, a + b)) in
let u = Seq.unfold helper (0, 1) in
let t = Seq.take  7 u in
let _ = Seq.iter print_int t in
()
``````

From pedagogical level it’s very interesting to define myself a take function on an older version of ocaml.
I tried but it gave one error,
I know i’m close but not yet there.
Below an errorfull tryout

``````let _ =
let rec seqtake n xs =
if n = 0 then None
else
match xs with
| None -> None
| Some (x, xs) -> Some (x, seqtake (n - 1) xs )
in
let helper z: ((int * (int * int)) option) = match z with a, b -> Some (a, (b, a + b)) in
let u = Seq.unfold helper (0, 1) in
let t = seqtake 7 u in
(*Unbound seq.take *)
let _ = Seq.iter print_int t in
()

``````

I’m there. Type type system is strong & the LSP server was very helpfull,

``````(* manually unfold take, sequence of integer fibonaci numbers *)
(* Nil, empty not used here as the sequence has no end *)
type intseq = Cons of (int * int) * (unit -> intseq)

let _ =
let rec afib (ab : int * int) : intseq =
match ab with a, b -> Cons (ab, fun () -> afib (b, a + b))
in
let fibs : intseq = afib (0, 1) in
let head (Cons (h, _)) : int * int = h in
let tail (Cons (_, tf)) : intseq = tf () in
(*force-evaluate the tail*)
let rec mytake (num : int) (seq : intseq) : 'a list =
if num = 0 then [] else head seq :: mytake (num - 1) (tail seq)
in
let take10 : (int * int) list = mytake 10 fibs in
let rec fgetnth (n : int) (lst : 'a list) : int * int =
if n = 1 then List.hd lst else fgetnth (n - 1) (List.tl lst)
in
let x : int = snd (fgetnth 10 take10) in
print_int x
``````

A simplification, `(a, b)` is an ‘irrefutable pattern’, meaning it can never be any other shape than a pair of elements, so we don’t need to use the `match` syntax on it. We can directly ‘destructure’ it in the function header: `let rec afib (a, b) = ...`