How to use Base.Sequence? (and how to find stuff like this out in the future)

Learning
1

Hi. I’m learning OCaml. I did most of the tutorials on ocaml.org, and now I’m reading Real World OCaml. At first, I thought it was weird to use an alternative standard library, but I generally appreciate the design of Base a little more than Pervasives, especially the preference for result variants over exceptions.

Anyway, before I started using Base, I was playing with Seq, which I like. As one does, I tried using it to implement infinite lazy Fibonacci. It was easy enough:

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

*I realize that should be bigints for “production Fibonacci.”

Anyway, after I started using Base, I was getting warnings about not using stuff from Pervasives directly, so I took a look to see what Base’s alternative is to Seq. I found Sequence. It doesn’t appear to be similar to Seq at all, and I was unable to divine its proper usage from the the documentation. I gather than Sequence.Step must somehow be involved, but I’m not really sure what to do there, or maybe it’s done with Sequence.unfold_step?

So, I looked at the code of the module itself and eventually figured out maybe it needs to be something like this:

let rec fibs a b =
  Sequence.unfold_step ~init:(a, b)
    ~f:(fun (a, b) ->
      Sequence.Step.Yield(a, (b, a+b)));;

This works, in any case, and I guess I understand how, but I’m not used to reading the implementation of a library in order to understand how to use the interface. While there is obviously a lot of benefit to reading the code you use, the difficulty at this point in learning OCaml is that I end up seeing a lot of things I don’t understand.

For example:

type +_ t =
  | Sequence : 's * ('s -> ('a,'s) Step.t) -> 'a t

Not really clear on what +_ means or what : means in the definition of a constructor (being accustomed to of). I think this has something to GADTs, but I haven’t gotten that far in the book yet and, though I’ve peaked ahead, I really have no idea what all that is about. Which is fine. I’ll get there when I get there.

I’m just wondering if this is the normal way to learn OCaml libraries or if there is a better way.

2

The top comment in Sequence has the following paragraph:

The elements are computed on demand, possibly repeating work if they are demanded multiple times. A sequence can be built by unfolding from some initial state, which will in practice often be other containers.

Admittedly, this isn’t super direct, but basically you are right in saying that the unfold_* functions are how Sequence.ts are constructed. The main one is unfold_step, which is slightly more expressive than what Seq gives you because it allows you to transform the state while not producing an element yet.

Sequence.unfold is more similar to the interface of Seq.t:

```(** [unfold_step ~init ~f] constructs a sequence by giving an initial state [init] and a
    function [f] explaining how to continue the next step from a given state. *)
val unfold_step : init:'s -> f:('s -> ('a, 's) Step.t) -> 'a t

(** [unfold ~init f] is a simplified version of [unfold_step] that does not allow
    [Skip]. *)
val unfold : init:'s -> f:('s -> ('a * 's) option) -> 'a t

I think you shouldn’t have had to read the implementation to figure out how to use the interface—in that case, our documentation needs improvement! (Please feel free to point out things that need explaining.)

As for the implementation itself, Sequence stands out as a module that uses a lot of OCaml’s advanced features, such as GADTs (which you correctly figured from the type definition), and variance annotations (which is what the +_ part is—it means that 'a Sequence.t can be treated as a subtype of 'b Sequence.t if 'a is a subtype of 'b). It can be pretty hard to wrap your head around it.

Most of the other modules in Base do not rely on as many advanced type system techniques (e.g., Hashtbl), although some rely on fairly intimate knowledge of the OCaml runtime (e.g., Option_array).

1 Like
3

Thanks for the explanation. I used unfold_step because I based my code on the implementation of of_list, which also uses unfold_step.

I think I more-or-less grok the logic behind Sequence, after letting it sink in a bit–It’s very similar to the iteration interface in Julia, with which I’m quite familiar.

The thing I would have found most helpful in this case would be some examples of general usage and sequence construction, which is essentially what I was looking for when I went to the source code. I often struggle to understand abstract descriptions of interfaces without sample code–though it’s less of a problem in languages where I have more experience and familiarity with the lingo.

Thanks again for your help!

1 Like
4

You’re welcome! I agree that adding examples of general usage would be helpful, and it’s something we’re actively working on in terms of our documentation.

3 Likes