From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by sympa.inria.fr (Postfix) with ESMTPS id 18EB77F249 for ; Wed, 31 Oct 2012 12:09:32 +0100 (CET) Received-SPF: None (mail4-smtp-sop.national.inria.fr: no sender authenticity information available from domain of didier.cassirame@gmail.com) identity=pra; client-ip=209.85.214.182; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="didier.cassirame@gmail.com"; x-sender="didier.cassirame@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail4-smtp-sop.national.inria.fr: domain of didier.cassirame@gmail.com designates 209.85.214.182 as permitted sender) identity=mailfrom; client-ip=209.85.214.182; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="didier.cassirame@gmail.com"; x-sender="didier.cassirame@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail4-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-ob0-f182.google.com) identity=helo; client-ip=209.85.214.182; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="didier.cassirame@gmail.com"; x-sender="postmaster@mail-ob0-f182.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Ai8CABAGkVDRVda2k2dsb2JhbABEhhe9TggjAQEBAQkJCwkUBCOCHgEBAQMBEgIPBBkBGx0BAwELBgMCCwM0AgIiAREBBQEcBhMIEweFboFjAQMJBpxXYgkDi2FPgnaEagoZJw1ZiHUBBQyRFIETA5JEgzKOYRYphBKBYw X-IronPort-AV: E=Sophos;i="4.80,687,1344204000"; d="scan'208";a="160993704" Received: from mail-ob0-f182.google.com ([209.85.214.182]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 31 Oct 2012 12:09:30 +0100 Received: by mail-ob0-f182.google.com with SMTP id wc20so2161692obb.27 for ; Wed, 31 Oct 2012 04:09:29 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=y+/pwnxULw9qqdzpFziD4BXmuy62NfoTyMeVle8Cynw=; b=XHuG9lQQupOeenMGt5hDpBeyCvx0TUMRxjE8/PKwVmRcdauPCuNo9g8f/jn+jw4/w8 7GRAifMWPie9JDkojRDrYtNwHdcLu7w6ZVTdTg24gscsCMHYUbHijCmvV1oPLrv2GTAb UVljYAAXEo+uB+ytNRT2Q5Tv4xa6S1oVjStZLvqQZDitp9j9LEdjVUc6mXyeku6MEp7B oW92Q/oitPwocb7JDtuaRq1u+Q0hem1aHh5evU45ambIIff3A1kbBJ8ZHoJFQLW0NLF4 ZqK8WC/2oIGYfcXhS9CnLbJNbmB7qiMhXxbVG2zNQqaHArb8MZImIfh7nD+2tMROmQPr UCzg== Received: by 10.60.31.101 with SMTP id z5mr32302404oeh.110.1351681769607; Wed, 31 Oct 2012 04:09:29 -0700 (PDT) MIME-Version: 1.0 Received: by 10.60.137.198 with HTTP; Wed, 31 Oct 2012 04:09:09 -0700 (PDT) In-Reply-To: <87625rhu04.fsf@golf.niidar.ru> References: <87625rhu04.fsf@golf.niidar.ru> From: Didier Cassirame Date: Wed, 31 Oct 2012 12:09:09 +0100 Message-ID: To: Ivan Gotovchits Cc: caml-list@inria.fr Content-Type: multipart/alternative; boundary=e89a8fb1f196ba135704cd58ef00 Subject: Re: [Caml-list] Higher order functors over tuples --e89a8fb1f196ba135704cd58ef00 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Hi Ivan, 2012/10/31 Ivan Gotovchits > > 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, =C2=ABmap/reduce=C2=BB computation on correspon= ding > 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 =3D > 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 > =C2=ABlist=C2=BB of different generators and do some arbitary iterations = on them. > > The =C2=ABlist=C2=BB can be made of pairs, using the cons (meta)construct= or: > > 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 > "steps" > 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 > 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 > | 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 =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? > 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 =3D sig ... end type m =3D (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 --e89a8fb1f196ba135704cd58ef00 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable 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

=C2=A0 =C2=A0module 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.

Do you wish to have parallel computation = done with these modules, or do you mean that you want them to be combined s= equentially?
=C2=A0

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.
<= /blockquote>

2. Particular problem

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

=C2=A0 =C2=A0module type Generator =3D
=C2=A0 =C2=A0sig
=C2=A0 =C2=A0 =C2=A0type t
=C2=A0 =C2=A0 =C2=A0type r
=C2=A0 =C2=A0 =C2=A0val create: unit =C2=A0-> t
=C2=A0 =C2=A0 =C2=A0val result: t -> r option
=C2=A0 =C2=A0 =C2=A0val step: =C2=A0 t -> t option
=C2=A0 =C2=A0end

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<= br> =C2=ABlist=C2=BB of different generators and do some arbitary iterations on= them.

The =C2=ABlist=C2=BB can be made of pairs, using the cons (meta)constructor= :

=C2=A0 =C2=A0module Cons :
=C2=A0 =C2=A0 =C2=A0functor(G1:Generator) -> functor(G2:Generator) ->= Generator

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

=C2=A0 =C2=A0M =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 "= ;steps"
contained generators in a sequence (swapping them on each step).

=C2=A0 =C2=A0module ConsGenerator
=C2=A0 =C2=A0 =C2=A0 =C2=A0(G1:Generator)
=C2=A0 =C2=A0 =C2=A0 =C2=A0(G2:Generator with type r =3D G1.r)
=C2=A0 =C2=A0 =C2=A0 =C2=A0: Generator with type r =3D G2.r =3D
=C2=A0 =C2=A0struct
=C2=A0 =C2=A0 =C2=A0type t =3D
=C2=A0 =C2=A0 =C2=A0 =C2=A0| G1G2 of (G1.t option * G2.t option )
=C2=A0 =C2=A0 =C2=A0 =C2=A0| G2G1 of (G2.t option * G1.t option )

=C2=A0 =C2=A0 =C2=A0type r =3D G2.r

=C2=A0 =C2=A0 =C2=A0let create () =3D
=C2=A0 =C2=A0 =C2=A0 =C2=A0G1G2 ((Some (G1.create ())), Some (G2.create ())= )

=C2=A0 =C2=A0 =C2=A0let step =3D function
=C2=A0 =C2=A0 =C2=A0 =C2=A0| G1G2 (g1, Some g2) =C2=A0 -> Some (G2G1 (G2= .step g2, g1))
=C2=A0 =C2=A0 =C2=A0 =C2=A0| G2G1 (g2, Some g1) =C2=A0 -> Some (G1G2 (G1= .step g1, g2))
=C2=A0 =C2=A0 =C2=A0 =C2=A0| G2G1 (Some g2, None) -> Some (G2G1 (G2.step= g2, None))
=C2=A0 =C2=A0 =C2=A0 =C2=A0| G1G2 (Some g1, None) -> Some (G1G2 (G1.step= g1, None))
=C2=A0 =C2=A0 =C2=A0 =C2=A0| G1G2 (None,None) | G2G1 (None,None) -> None=

=C2=A0 =C2=A0 =C2=A0let result =3D function
=C2=A0 =C2=A0 =C2=A0 =C2=A0| G1G2 (Some g1,_) -> G1.result g1
=C2=A0 =C2=A0 =C2=A0 =C2=A0| G2G1 (Some g2,_) -> G2.result g2
=C2=A0 =C2=A0 =C2=A0 =C2=A0| G1G2 (None,_) | G2G1 (None,_) -> None
=C2=A0 =C2=A0end

Function `proceed' iterates module M and print results

=C2=A0 =C2=A0let rec proceed oe =3D match M.step oe with
=C2=A0 =C2=A0 =C2=A0| Some oe -> begin
=C2=A0 =C2=A0 =C2=A0 =C2=A0match M.result oe with
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0| Some r -> print_int r; proceed oe
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0| None =C2=A0 -> proceed oe
=C2=A0 =C2=A0 =C2=A0end
=C2=A0 =C2=A0 =C2=A0| None -> print_newline ();
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0print_endline "generator finished&qu= ot;

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

=C2=A0 =C2=A0module Odd : Generator with type r =3D int =3D struct
=C2=A0 =C2=A0 =C2=A0type t =3D int
=C2=A0 =C2=A0 =C2=A0type r =3D int
=C2=A0 =C2=A0 =C2=A0let create () =3D -1
=C2=A0 =C2=A0 =C2=A0let step v =3D if v < 10 then Some (v+2) else None =C2=A0 =C2=A0 =C2=A0let result v =3D if v <=3D 9 then Some v else None =C2=A0 =C2=A0end

=C2=A0 =C2=A0module Even : Generator with type r =3D int =3D struct
=C2=A0 =C2=A0 =C2=A0type t =3D int
=C2=A0 =C2=A0 =C2=A0type r =3D int
=C2=A0 =C2=A0 =C2=A0let create () =3D 0
=C2=A0 =C2=A0 =C2=A0let step v =3D if v < 10 then Some (v+2) else None =C2=A0 =C2=A0 =C2=A0let result v =3D if v <=3D 8 then Some v else None =C2=A0 =C2=A0end

and the result was
=C2=A0 =C2=A0# module M =3D Cons(Even)(Cons(Cons(Odd)(Even))(Even))
=C2=A0 =C2=A0# let _ =C2=A0=3D proceed (M.create ())
=C2=A0 =C2=A022244618648365879
=C2=A0 =C2=A0generator finished
=C2=A0 =C2=A0- : 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?

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

- you can defin= e types based on module types like this.

module type M =3D sig ... end

type m =3D (module M)

and t= hen you should be able to build simple lists of type m.

=C2=A0
=
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
--e89a8fb1f196ba135704cd58ef00--