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 11E5E7F2AA for ; Fri, 21 Dec 2012 20:55:31 +0100 (CET) Received-SPF: None (mail4-smtp-sop.national.inria.fr: no sender authenticity information available from domain of pjfrey@sympatico.ca) identity=pra; client-ip=65.55.116.17; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="pjfrey@sympatico.ca"; x-sender="pjfrey@sympatico.ca"; x-conformance=sidf_compatible Received-SPF: Pass (mail4-smtp-sop.national.inria.fr: domain of pjfrey@sympatico.ca designates 65.55.116.17 as permitted sender) identity=mailfrom; client-ip=65.55.116.17; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="pjfrey@sympatico.ca"; x-sender="pjfrey@sympatico.ca"; 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@blu0-omc1-s6.blu0.hotmail.com) identity=helo; client-ip=65.55.116.17; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="pjfrey@sympatico.ca"; x-sender="postmaster@blu0-omc1-s6.blu0.hotmail.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Av8AAKe91FBBN3QRk2dsb2JhbAA8CYY6tmtVFg4BAQEBCQkLCRQDJIIeAQEFIwRSEAsYAgImAgJXFAILiAujR5J4gSKLOg2BCIIWMmEDiGKHfoZHhDoVjW8 X-IronPort-AV: E=Sophos;i="4.84,331,1355094000"; d="scan'208";a="166577576" Received: from blu0-omc1-s6.blu0.hotmail.com ([65.55.116.17]) by mail4-smtp-sop.national.inria.fr with ESMTP; 21 Dec 2012 20:55:29 +0100 Received: from BLU0-SMTP100 ([65.55.116.7]) by blu0-omc1-s6.blu0.hotmail.com with Microsoft SMTPSVC(6.0.3790.4675); Fri, 21 Dec 2012 11:55:28 -0800 X-EIP: [xHmP1Wq49/D+JNZKgudJOQcUBVQ0aV7X] X-Originating-Email: [pjfrey@sympatico.ca] Message-ID: Received: from [192.168.2.11] ([74.12.92.52]) by BLU0-SMTP100.blu0.hotmail.com over TLS secured channel with Microsoft SMTPSVC(6.0.3790.4675); Fri, 21 Dec 2012 11:55:27 -0800 From: Peter Frey To: caml-list@inria.fr CC: Eric Jaeger In-Reply-To: <003801cddcfa$f66325c0$e3297140$@jaeger@ssi.gouv.fr> References: <003801cddcfa$f66325c0$e3297140$@jaeger@ssi.gouv.fr> Content-Type: text/plain; charset="UTF-8" Date: Fri, 21 Dec 2012 14:55:26 -0500 MIME-Version: 1.0 X-Mailer: Evolution 2.28.3 Content-Transfer-Encoding: quoted-printable X-OriginalArrivalTime: 21 Dec 2012 19:55:27.0771 (UTC) FILETIME=[1FB606B0:01CDDFB5] Subject: Re: [Caml-list] Function returning recursive lists On Tue, 2012-12-18 at 09:37 +0100, Eric Jaeger wrote: > Hi everyone, >=20 >=20=20 >=20 > There are various discussions on recursive lists in the archive, yet I > was wondering whether or not it was possible in pure OCaml to write a > function returning non-constant recursive lists. >=20 >=20=20 >=20 > For example, I would like to have a function =E2=80=9Cdocycle:=E2=80=99a = list->=E2=80=99a > list=E2=80=9D that takes a non recursive list and transforms it into a > recursive list containing the same elements. That is, =E2=80=9Cdocycle > [1;2;3]=E2=80=9D would return a list structurally equivalent to =E2=80=9C= let rec > c=3D1::2::3::c in c=E2=80=9D. So far, my various attempts (OCaml 3.12) ha= ve not > been successful. Another good example is to have a List.map compatible > with recursive lists. >=20 >=20=20 >=20 > Please note that it is, in a way, a theoretical (and possibly na=C3=AFve) > question : >=20 > - I do not consider recursive lists as the perfect > implementation for my problem >=20 > - I do not care about efficiency >=20 > - I do not want to use an ad hoc mutable/lazy list datatype > (unless I=E2=80=99ve also a conversion function toward standard lists) >=20 > - I do not want to use Obj or other similar tricks >=20 > It=E2=80=99s just that I=E2=80=99m curious whether or not what I=E2=80=99= m trying to achieve > is possible. >=20 >=20=20 >=20 > Regards, Eric >=20 It sometimes helps to read read the various libraries. For example, this thing is a variation of Batteries.BatList.Append: module Cycle =3D struct type 'a mut_list =3D { hd: 'a; mutable tl: 'a list } external inj : 'a mut_list -> 'a list =3D "%identity" external jni : 'a list -> 'a mut_list =3D "%identity" =20 let docycle =3D function (* copy and convert to circular *) | [] -> raise (Failure"Cannot make [] circular") | h0 :: t -> let r =3D { hd =3D h0; tl =3D [] } in let rec loop dst =3D function | [] -> dst.tl <- inj r; dst.tl | h :: t -> let cell =3D { hd =3D h; tl =3D [] } in dst.tl <- inj cell; loop cell t in loop r t let docycle =3D function (* convert to circular in place *) | [] -> raise (Failure"Cannot make [] circular") | ll -> let rec aux dst =3D=20 if dst.tl =3D [] then begin (* at end : *) dst.tl <- ll; (* replace last cell with ll *) List.tl (inj dst) (* and rotate to begin *) end else aux (jni (dst.tl)); (* advance *) in aux (jni ll) end let a =3D Cycle.docycle (ExtLib.String.explode "1234") let _ =3D let open Printf in List.iter print_char (ExtLib.List.take 50 a)= =20 $peter@ubuntu:~/ocaml/dink$ ./a.out=20 12341234123412341234123412341234123412341234123412peter@ubuntu:~/ocaml/dink= $=20