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 mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id 7B0B77F75C for ; Sun, 7 Sep 2014 15:24:12 +0200 (CEST) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of yallop@gmail.com) identity=pra; client-ip=74.125.82.176; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="yallop@gmail.com"; x-sender="yallop@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of yallop@gmail.com designates 74.125.82.176 as permitted sender) identity=mailfrom; client-ip=74.125.82.176; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="yallop@gmail.com"; x-sender="yallop@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-we0-f176.google.com) identity=helo; client-ip=74.125.82.176; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="yallop@gmail.com"; x-sender="postmaster@mail-we0-f176.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AvoBAD1cDFRKfVKwlWdsb2JhbABZhDcEgnjOOgF8CBYQAQEBAQcNCQkSLIQEAQEEEhEdARsdAQMMBgULDwImAgIiAREBBQEcBhMiiAsBAxGafGuLMIFygxCISwoZJw1mhXQBEQEFDoEejW4zB4J5gVMFnHKTOhgphRM8L4JPAQEB X-IPAS-Result: AvoBAD1cDFRKfVKwlWdsb2JhbABZhDcEgnjOOgF8CBYQAQEBAQcNCQkSLIQEAQEEEhEdARsdAQMMBgULDwImAgIiAREBBQEcBhMiiAsBAxGafGuLMIFygxCISwoZJw1mhXQBEQEFDoEejW4zB4J5gVMFnHKTOhgphRM8L4JPAQEB X-IronPort-AV: E=Sophos;i="5.04,482,1406584800"; d="scan'208";a="78041406" Received: from mail-we0-f176.google.com ([74.125.82.176]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 07 Sep 2014 15:24:11 +0200 Received: by mail-we0-f176.google.com with SMTP id q58so1096326wes.21 for ; Sun, 07 Sep 2014 06:24:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=h4fnupxLTHmdncgwPcYxx7aN9CythwSqwp9gzNgSLf8=; b=v/chZq7cdXeLI/Bssz12n4m0LSTlmAoU4lj+UM1/GTVhJ1HU843SqQIJITamPeisd5 r2AahSmkf4o0OhF68+p9nxdm164lv0lk3t/nVawkyYb6s3vR7r3QJrU/cxNhviCFFgAx Pc/ZMWaH13vjrMFilfo1+tdSbX9Qm/EeWPv2fUoCJOPOW6v2pEWJkzuVndTLy1swqQHS l+dw4votuDBp2sgIteauli50tZNiTfC/uvz5tlBs6sBwTRP6kOOOYmm7f9TKeJn37bHM KmqVWig2zSr+aC9ij/W890Ia8Y+IxnU69ioJlVMVkgmioPfBX+sa1NJEukSl6rWt+dZM dV2A== MIME-Version: 1.0 X-Received: by 10.194.179.197 with SMTP id di5mr96366wjc.125.1410096250592; Sun, 07 Sep 2014 06:24:10 -0700 (PDT) Received: by 10.217.129.194 with HTTP; Sun, 7 Sep 2014 06:24:10 -0700 (PDT) In-Reply-To: <91F16B653D20446DA42F7B673FD5509D@PCdejd> References: <91F16B653D20446DA42F7B673FD5509D@PCdejd> Date: Sun, 7 Sep 2014 14:24:10 +0100 Message-ID: From: Jeremy Yallop To: Jean-Denis Eiden Cc: Caml List Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Subject: Re: [Caml-list] listes qui bouclent [This message is intentionally but regrettably written in English.] Dear Jean-Denis, Caml Light is not really maintained any more, so unless you have a special reason to use it it might be better to switch to OCaml. I'll suggest an answer to your question for OCaml, which might not apply directly to Caml Light. 2014-09-07 10:31 GMT+01:00 Jean-Denis Eiden : > Cela =C3=A9tant, j'aimerais pouvoir faire la m=C3=AAme chose en param=C3= =A9trant la p=C3=A9riode > ; par exemple, j'aimerais cr=C3=A9er [ 0 ; 1 ; 2 ; ... ; n-1 ; 0 ; 1 ; 2 = ; ... ] I don't know of a way to create cyclic lists of a runtime specified period using the built-in list type, and I suspect that it isn't possible. However, if you're willing to use an alternative list type then it is possible to accomplish what you want. The natural setting for a cyclic immutable value is a lazy language. OCaml is eagerly evaluated by default, but provides support for introducing laziness explicitly. We can define a type of lazy lists in OCaml as follows: type 'a llist_aux =3D LNil | LCons of 'a * 'a llist and 'a llist =3D 'a llist_aux Lazy.t Using this definition we can write a function which creates cyclic values of a given period: let lcyclic period =3D if period <=3D 0 then invalid_arg "lcyclic"; let rec loop i =3D if i =3D period then l else lazy (LCons (i, loop (i + 1))) and l =3D lazy (Lazy.force (loop 0)) in l If you trace through the operation of lcyclic you'll see that a call like t= his lcyclic 3 builds a value that's equivalent to the value created by writing this let rec l3 =3D lazy (LCons (0, lazy (LCons (1, lazy (LCons (2, l3)))))))) Since OCaml has special support for lazy values there's less overhead than you might imagine in programming with values like this. Once every element of the list has been examined the runtime system can make the representation exactly the same as a corresponding value of the built-in list type. However, there's still a little overhead involved in examining values of llist. A second approach to building cyclic lists of runtime-specified period is to use mutation. If you make the tail of your list values mutable then you can build the list up to the cyclic point, then patch things up so that the tail of the last cons cell points back to the front of the list. Here's a type definition: type 'a mlist =3D MNil | MCons of 'a mcons and 'a mcons =3D { mhead : 'a; mutable mtail : 'a mlist } and here's a corresponding function for building cyclic lists: let mcyclic period =3D if period <=3D 0 then invalid_arg "mcyclic"; let rec mlast =3D { mhead =3D period - 1; mtail =3D MCons mlast } and loop i head =3D if i =3D 0 then head else loop (i - 1) (MCons { mhead =3D i - 1; mtail =3D head }) in let l =3D loop (period - 1) (MCons mlast) in mlast.mtail <- l; l Once again, if you trace through the evaluation of an expression like this mcyclic 3 you'll see that it builds a value equivalent to the value created by writing this let rec m3 =3D MCons {mhead =3D 0; mtail =3D MCons {mhead =3D 1; mtail =3D MCons {mhead =3D 2; mtail =3D m3}}} Using mutation here introduces a little extra representation overhead in OCaml, since mutation requires a record, which involves allocating an extra block for every cons cell. There's consequently also an extra level of indirection when examining values of mlist compared to examining values of the built-in list type. I hope that helps a bit, Jeremy.