2012/10/31 Ivan Gotovchits <ivg@ieee.org>

Good day,

1. A problem in general

In general, the problem is to compute a tuple of objects that have
types different, but conforming to the same interface, i.e., given a
group of modules (A,B,C), conforming to signature S to construct some

module M: functor(A:S) -> functor(B:S) -> functor(C:S) -> S

that will, in a some way, «map/reduce» computation on corresponding
modules.

Do you wish to have parallel computation done with these modules, or do you mean that you want them to be combined sequentially?

The problem can be generalized further, but, it seems to me, that it is
already quite (too?) abstract.

As far as I can see, there is no ad hoc solution for this problem in
OCaml, except, of course, objects with their late binding. But, in some
circumstances, the late binding can be avoided. In particular, when
types of modules and their amount are known and fixed at compile time.

2. Particular problem

For example, we have several different data generator modules conforming
to the signature

module type Generator =
sig
type t
type r
val create: unit -> t
val result: t -> r option
val step: t -> t option
end

Each generator can be stepped forward and queried for a result. Generator
can expire, in such case it will return None as a result. I want to make a
«list» of different generators and do some arbitary iterations on them.

The «list» can be made of pairs, using the cons (meta)constructor:

module Cons :
functor(G1:Generator) -> functor(G2:Generator) -> Generator

So, if I have three modules A,B,C, I can construct module

M = Cons(A)(Cons(B)(C))

and call M.step, to move a chain of generators forward, or M.result to
get the current result.

3. Particular solution

Here is the implementation on Cons module (named ConsGenerator), that "steps"
contained generators in a sequence (swapping them on each step).

module ConsGenerator
(G1:Generator)
(G2:Generator with type r = G1.r)
: Generator with type r = G2.r =
struct
type t =
| G1G2 of (G1.t option * G2.t option )
| G2G1 of (G2.t option * G1.t option )

type r = G2.r

let create () =
G1G2 ((Some (G1.create ())), Some (G2.create ()))

let step = function
| G1G2 (g1, Some g2) -> Some (G2G1 (G2.step g2, g1))
| G2G1 (g2, Some g1) -> Some (G1G2 (G1.step g1, g2))
| G2G1 (Some g2, None) -> Some (G2G1 (G2.step g2, None))
| G1G2 (Some g1, None) -> Some (G1G2 (G1.step g1, None))
| G1G2 (None,None) | G2G1 (None,None) -> None

let result = function
| G1G2 (Some g1,_) -> G1.result g1
| G2G1 (Some g2,_) -> G2.result g2
| G1G2 (None,_) | G2G1 (None,_) -> None
end

Function `proceed' iterates module M and print results

let rec proceed oe = match M.step oe with
| Some oe -> begin
match M.result oe with
| Some r -> print_int r; proceed oe
| None -> proceed oe
end
| None -> print_newline ();
print_endline "generator finished"

Just for a completness of the example a pair of simple generators:

module Odd : Generator with type r = int = struct
type t = int
type r = int
let create () = -1
let step v = if v < 10 then Some (v+2) else None
let result v = if v <= 9 then Some v else None
end

module Even : Generator with type r = int = struct
type t = int
type r = int
let create () = 0
let step v = if v < 10 then Some (v+2) else None
let result v = if v <= 8 then Some v else None
end

and the result was
# module M = Cons(Even)(Cons(Cons(Odd)(Even))(Even))
# let _ = proceed (M.create ())
22244618648365879
generator finished
- : unit = ()

4. Question

And now the questions!

1) Is there any idiomatic solution to this pattern?

2) If not, can my solution be improved in some way? And how?

Thanks to a very recent post, I rediscovered that OCaml can handle modules as first class values (since ver. 3.12) :

- you can define types based on module types like this.

module type M = sig ... end

type m = (module M)

and then you should be able to build simple lists of type m.

3) My intution says that it can be solved with monads (Generator really
incapsulates side effects in a step. Several computation are combined in
one big chain... ). Am I right? If so, how to implement it in monads?

I guess that you could use the type above with regular monads too.

If you don't have access to that feature, you could perhaps use higher order functors?

Cheers,

didier