.. post:: 2017-07-25
:tags: OCaml, Monads, Generators
Monadic Generators in OCaml
===========================
Generators are one of those features that have been heavily popularized by
today's fashionable languages such as Python and ES6. So it's not the first time
I've encountered programmers who are curious about OCaml bring up with questions
along the lines of:
* Why doesn't OCaml support generators?
* Are there alternatives to generators in OCaml?
* How can I emulate generators in OCaml?
In this post, I'd like to briefly address these questions.
Where are the Generators?
-------------------------
I can only speculate but it seems self evident, OCaml doesn't have native
support for generators because it doesn't really need it. There's quite a few
satisfactory ways of emulating them to the point where the strong justification
for adding a feature to the language just isn't there.
With that being said, it's well known that people are working on algebraic
effects for OCaml and it's my understanding that it will be possible to
implement generators in direct style which would be indistinguishable from
direct support in the compiler. So this feature is effectively a strict superset
of generators and should settle this issue once and for all.
Alternatives to Generators
--------------------------
Maybe I'm just old fashioned, but I find myself rarely needing generators. I
usually find the bog standard `lazy lists` to be more convenient to work with.
Where my implementation of choice the one is the one that comes with `containers
`_.
Here's a simple lazy list of primes:
.. code-block:: ocaml
(* save to file.ml and run as $ utop file.ml *)
#require "containers.iter";;
module Llist = CCLazy_list
let primes =
let open Llist in
let rec next_prime n =
try
for i=2 to int_of_float (sqrt (float_of_int n)) do
if n mod i = 0 then raise_notrace Exit
done;
Cons (n, lazy (next_prime (n + 1)))
with Exit -> next_prime (n + 1) in
Lazy.from_val @@ Cons (2, lazy (next_prime 3))
let () =
let n = 100_000 in
let primes = Llist.length (Llist.take n primes) in
Printf.printf "Found: %d primes\n" primes
OK, maybe this isn't the prettiest code, but I've picked a bad example. Lazy
lists usually work much better. Promise.
The other candidate I usually reach for is the `gen` type:
.. code-block:: ocaml
type 'a gen = unit -> 'a option
Which comes with its own useful `gen `_ library.
The main advantage of this type is that it's structural. We can consume and
produce gens without ever depending on a library. ocaml-re uses this to great
effect `here `_
for example.
The disadvantage of this type is that implementing generators usually involves
ugly mutable code. Oh well, if I had a problem with this kind of mutation, I'd
be using Haskell.
.. code-block:: ocaml
let primes () =
let prime = ref 1 in
let rec loop () =
incr prime;
try
for i=2 to int_of_float (sqrt (float_of_int !prime)) do
if !prime mod i = 0 then raise_notrace Exit
done;
Some !prime
with Exit -> loop ()
in loop
let () =
let prime_gen = primes () in
for _ = 0 to 100_00 do
assert (prime_gen () != None);
done;
print_endline "There's more than 100_000 primes"
Note the type of this function:
.. code-block:: ocaml
val primes : unit -> (unit -> int option)
We must not forget to create a new generator whenever we want to iterate over
our generator from scratch.
Really Faking Generators
------------------------
While the approaches above were similar, they're still not capturing the essence
of generators - the ability to `yield` control back to the caller along with a
value anywhere inside a computation. How do we approach this problem? Like every
good functional programmer: with Monads!
Here's the signature we're aiming to implement:
.. code-block:: ocaml
module type Gen_intf = sig
type ('result, 'yield) t
val return : 'a -> ('a, _) t
val yield : 's -> (unit, 's) t
val (>>=) : ('a, 's) t -> ('a -> ('b, 's) t) -> ('b, 's) t
val iter : ('result, 'a) t -> f:('a -> unit) -> 'result
end
With this signature, we're modeling generators as computations that can produce
a final ``'result``` value and possibly many intermediate ``'yield'`` values
along the way. These computations can of course be sequenced (the essence of
monads), and finally executed to produce the final a result along with running a
callback for every yielded value.
Representing this behavior with a type we arrive at a generator:
.. code-block:: ocaml
type ('result, 'yield) t =
| Done of 'result
| Yield of (unit -> 'yield * ('result, 'yield) t)
A constructor for terminating the generator and continuing it along with a
yielded value. Note that we need to guard every yield behind a thunk. Otherwise
we will find it quite hard to pause our generator mid way.
Since this a monad instance,
.. code-block:: ocaml
let return a = Done a
let rec (>>=) x f =
match x with
| Done r -> f r
| Yield t -> Yield (fun () ->
let (y, next) = t () in
(y, next >>= f)
)
where ``return`` trivial and ``(>>=)`` is simply sequencing a generator along
with a computation that produces a generator from the result.
If you really want to get the hang of it, try implementing ``join`` from
scratch:
.. code-block:: ocaml
val join : (('a, 's) t, 's) -> ('a, 's) t
Now, finally we need ``yield`` to generate values:
.. code-block:: ocaml
let yield r = Yield (fun () -> (r, return ()))
Let's briefly contrast this to our ``return`` above. While ``return`` created a
generator that yielded no values and produced some result, ``yield`` creates a
generator that yields a single value and produces a trivial result.
With this kit, we can construct generators:
.. code-block:: ocaml
(* assuming that all these functions are in Gen*)
let primes : (unit, int) Gen.t =
let open Gen in
let rec loop n =
try
for i=2 to int_of_float (sqrt (float_of_int n)) do
if n mod i = 0 then raise_notrace Exit
done;
yield n >>= fun () ->
loop (n + 1)
with
Exit ->
loop (n + 1)
in loop 2
We're almost done here, all that remains is a way to run a generator:
.. code-block:: ocaml
let rec iter x ~f =
match x with
| Done s -> s
| Yield t ->
let (y, x) = t () in
f y;
iter x ~f
While this is a useful function in general, it doesn't quite work in our case
since our generator doesn't terminate.
No matter, we can have a variant that will only consume up to a constant number
of yields:
.. code-block:: ocaml
let take
: type a b. (a, b) t -> int -> b list
= fun t n ->
let rec loop acc t n =
match t, n with
| Done _, _
| _, 0 -> List.rev acc
| Yield t, n ->
let (a, next) = t () in
loop (a::acc) next (n - 1)
in loop [] t n
As an exercise, one can also implement a generator-returning version of this:
.. code-block:: ocaml
val take : ('a, 'b) t -> int -> (unit, 'b) t
And finally:
.. code-block:: ocaml
ignore (Gen.take primes 100_000)
What Else?
----------
First of all, let me first mention that this entire treatment is following Kwang
Yul Seo's original `exposition
`_.
Apart from the usual porting to OCaml, I took the liberty to get rid of the
transformer layer in my OCaml port. Transformers aren't necessary to thread
effects while yielding in OCaml, and a naive implementation would raise some
stack safety issues that would distract us from the topic at hand.
I should also note that a variant of all this work in OCaml can always be found
in some obscure Jane Street library. This time, it's not obscure at all but the
ubiquitous `Sequence.Generator
`_ module
in `Base `_. Their approach is more
sophisticated as it uses the `Stream Fusion
`_ step type to
construct the generator. Also, they have a solution to the problem of composing
monads with their sequence type. Which is similar to the problem I've avoided
with making ``yield`` play nicely with other binds.
Finally, I should note that the most honest to goodness emulation is actually
done with the infamous delimcc in this `blog post
`_.
But it would take me a lot of guts before I'd use delimcc in production, so it's
not worth dwelling on.
Happy generating!