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 mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by sympa.inria.fr (Postfix) with ESMTPS id DB7B67F1C9 for ; Mon, 12 Nov 2012 07:45:03 +0100 (CET) Received-SPF: None (mail1-smtp-roc.national.inria.fr: no sender authenticity information available from domain of jeannin@cs.cornell.edu) identity=pra; client-ip=128.84.103.139; receiver=mail1-smtp-roc.national.inria.fr; envelope-from="jeannin@cs.cornell.edu"; x-sender="jeannin@cs.cornell.edu"; x-conformance=sidf_compatible Received-SPF: None (mail1-smtp-roc.national.inria.fr: no sender authenticity information available from domain of jeannin@cs.cornell.edu) identity=mailfrom; client-ip=128.84.103.139; receiver=mail1-smtp-roc.national.inria.fr; envelope-from="jeannin@cs.cornell.edu"; x-sender="jeannin@cs.cornell.edu"; x-conformance=sidf_compatible Received-SPF: None (mail1-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@exch-hub2.cs.cornell.edu) identity=helo; client-ip=128.84.103.139; receiver=mail1-smtp-roc.national.inria.fr; envelope-from="jeannin@cs.cornell.edu"; x-sender="postmaster@exch-hub2.cs.cornell.edu"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Ah4FAGSaoFCAVGeLbmdsb2JhbABEw3lDGweCIAU6UQE8AkInBBsTh28LmiGXO4kIkX5hA4hajSKBHJI0 X-IronPort-AV: E=Sophos;i="4.80,759,1344204000"; d="scan'208";a="181052320" Received: from mail-hub-2.cs.cornell.edu (HELO exch-hub2.cs.cornell.edu) ([128.84.103.139]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-MD5; 12 Nov 2012 07:45:02 +0100 Received: from gobo.cs.cornell.edu ([128.84.96.141]) by exch-hub2.cs.cornell.edu ([128.84.103.139]) with mapi; Mon, 12 Nov 2012 01:44:58 -0500 From: Jean-Baptiste Jeannin To: "caml-list@inria.fr" Date: Mon, 12 Nov 2012 01:44:55 -0500 Thread-Topic: Cyclic data structures: internal representation Thread-Index: AQHNwKE6ufYAtdxafECVM00FR3UBMA== Message-ID: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: acceptlanguage: en-US Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Subject: [Caml-list] Cyclic data structures: internal representation Good morning, One can create cyclic data structures in OCaml, using the keyword let rec. = For example: # let rec l0 =3D 1 :: 2 :: l0;; var l0 : int list =3D [1; 2; 1; 2; 1; 2; 1; 2; 1; 2; 1; 2; 1; 2; 1; 2; 1; 2; ...] I am wondering what the internal representation (in the AST) of such a data= structure is. It could be a cyclic data structure on the AST itself, but I= doubt it because it would make it difficult to manipulate. Another solutio= n I see is keeping a data structure with free variables inside (or referenc= es, for that matter) and binding these free variables in some other place. = l0 would then bounded directly to [1 ; 2 ; l0 ] in the AST. Any idea what = the internals of OCaml do? Related questions: - is there any easy way to check if a list is cyclic or not? The only way I= see is to go down the list, checking at every step if this particular subl= ist has already been seen. But it's rather heavy. - the documentation on the =3D sign (http://caml.inria.fr/pub/docs/manual-o= caml/libref/Pervasives.html) mentions that "Equality between cyclic data st= ructures may not terminate." It seems to terminate if one or the other of t= he data structures is not cyclic. Does it ever terminate when both data sst= ructures are cyclic, or does it always loop? # let l1 =3D [1; 2] in l0 =3D l1;; - : bool =3D false # l0 =3D l0;; (* doesn't finish *) Thank you, Jean-Baptiste Jeannin=