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