Re: [Caml-list] Higher order functors over tuples

[Didier Cassirame <didier.cassirame@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 5049 bytes --]

Hi Ivan,

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

[-- Attachment #2: Type: text/html, Size: 6293 bytes --]