From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <lambda.q.q@gmail.com>
X-Original-To: caml-list@sympa.inria.fr
Delivered-To: caml-list@sympa.inria.fr
Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82])
	by sympa.inria.fr (Postfix) with ESMTPS id D54007F249
	for <caml-list@sympa.inria.fr>; Wed, 31 Oct 2012 10:21:44 +0100 (CET)
Received-SPF: None (mail1-smtp-roc.national.inria.fr: no sender
  authenticity information available from domain of
  lambda.q.q@gmail.com) identity=pra; client-ip=209.85.215.54;
  receiver=mail1-smtp-roc.national.inria.fr;
  envelope-from="lambda.q.q@gmail.com";
  x-sender="lambda.q.q@gmail.com";
  x-conformance=sidf_compatible
Received-SPF: Pass (mail1-smtp-roc.national.inria.fr: domain of
  lambda.q.q@gmail.com designates 209.85.215.54 as permitted
  sender) identity=mailfrom; client-ip=209.85.215.54;
  receiver=mail1-smtp-roc.national.inria.fr;
  envelope-from="lambda.q.q@gmail.com";
  x-sender="lambda.q.q@gmail.com";
  x-conformance=sidf_compatible; x-record-type="v=spf1"
Received-SPF: None (mail1-smtp-roc.national.inria.fr: no sender
  authenticity information available from domain of
  postmaster@mail-la0-f54.google.com) identity=helo;
  client-ip=209.85.215.54;
  receiver=mail1-smtp-roc.national.inria.fr;
  envelope-from="lambda.q.q@gmail.com";
  x-sender="postmaster@mail-la0-f54.google.com";
  x-conformance=sidf_compatible
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: ApEEADjskFDRVdc2k2dsb2JhbABEMYVmvU4IIwEBAQEHCwsJFAQjgjcCDwQZATkDDQUfAgUhAhEBBCABBQFQB4dSAw8Emh6CCWIJA4thg0WFDCcNiU4BBQyBFJAAgRMDiFSJcIMyjmE/gViCPg
X-IronPort-AV: E=Sophos;i="4.80,687,1344204000"; 
   d="scan'208";a="179648196"
Received: from mail-la0-f54.google.com ([209.85.215.54])
  by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 31 Oct 2012 10:21:44 +0100
Received: by mail-la0-f54.google.com with SMTP id e12so1484442lag.27
        for <caml-list@inria.fr>; Wed, 31 Oct 2012 02:21:43 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20120113;
        h=sender:from:to:subject:date:message-id:user-agent:mime-version
         :content-type:content-transfer-encoding;
        bh=Ws8iaI4MsIOCqAQNAAiEjlStvdBizolSDeq5uGMx5mg=;
        b=ZyWBwFGGotmO0vE4LldThW70hXpUTzf89vEPBavZccEyv1JnbqBvHc1LqKLQW/AW91
         bDL/goDjuhtO31fOvOOpBc7jmG02GKarSo+DZ65lRbv8P9QuEeLa0axoOqUbEklKJEJ7
         uzMM4rSiTR48FxYs6KzQtdt86MFR2AhZ+YseRbAAsUAxxLJxdKXHRnCHgIleEvw+L7O+
         z8aZitNLIc6Bkjj6hSl9DIzi1/JyDntN8CVhPvK3yvqUANBt9Yy+t8zfKesDxm3gZw6F
         4RiRYBSJ6elC8+sAp1Ku/5EcKDErCjR/3/uZN/plOGUXrIY5nk26KJdb9u2oMM2U+kyD
         FfJQ==
Received: by 10.112.82.232 with SMTP id l8mr14237763lby.104.1351675303659;
        Wed, 31 Oct 2012 02:21:43 -0700 (PDT)
Received: from golf.niidar.ru.niidar.ru ([178.176.101.101])
        by mx.google.com with ESMTPS id bf3sm1180890lbb.16.2012.10.31.02.21.41
        (version=TLSv1/SSLv3 cipher=OTHER);
        Wed, 31 Oct 2012 02:21:42 -0700 (PDT)
Sender: Ivan Gotovchits <lambda.q.q@gmail.com>
From: Ivan Gotovchits <ivg@ieee.org>
To: caml-list@inria.fr
Date: Wed, 31 Oct 2012 13:26:51 +0400
Message-ID: <87625rhu04.fsf@golf.niidar.ru>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.2 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Subject: [Caml-list] Higher order functors over tuples


Good day,

1. A problem in general=20

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=20

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

that will, in a some way, =C2=ABmap/reduce=C2=BB computation on correspondi=
ng
modules.

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=20

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

   module type Generator =3D=20
   sig
     type t
     type r
     val create: unit  -> t=20
     val result: t -> r option=20=20
     val step:   t -> t option=20
   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
=C2=ABlist=C2=BB of different generators and do some arbitary iterations on=
 them.=20

The =C2=ABlist=C2=BB 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 =3D 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 "step=
s"
contained generators in a sequence (swapping them on each step).

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

     type r =3D G2.r

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

     let step =3D 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 =3D 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 =3D match M.step oe with=20
     | Some oe -> begin=20
       match M.result oe with
         | Some r -> print_int r; proceed oe
         | None   -> proceed oe
     end
     | None -> print_newline ();=20
         print_endline "generator finished"=20=20=20=20=20=20

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

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

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

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


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?

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?

Thanks for reading down to this line =3D) Any comments are welcome!

P.S. Sorry for such a long article. I haven't enough brains to make it
shorter =3D)

--=20
         (__)=20
         (oo)=20
   /------\/=20
  / |    ||=20=20=20
 *  /\---/\=20
    ~~   ~~=20=20=20
...."Have you mooed today?"...