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 30E247EE86 for ; Mon, 12 Nov 2012 12:24:33 +0100 (CET) Received-SPF: None (mail4-smtp-sop.national.inria.fr: no sender authenticity information available from domain of gdsfh1@gmail.com) identity=pra; client-ip=209.85.220.54; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="gdsfh1@gmail.com"; x-sender="gdsfh1@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail4-smtp-sop.national.inria.fr: domain of gdsfh1@gmail.com designates 209.85.220.54 as permitted sender) identity=mailfrom; client-ip=209.85.220.54; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="gdsfh1@gmail.com"; x-sender="gdsfh1@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-pa0-f54.google.com) identity=helo; client-ip=209.85.220.54; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="gdsfh1@gmail.com"; x-sender="postmaster@mail-pa0-f54.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Aj8DACnaoFDRVdw2lGdsb2JhbABEhhq9NQgjAQEBAQkJCwkSKYIfAQUjBBkBGxYIAwwGBQsPAiYCAiIBEQEFARwGiAoBAw8LnCeLY0+CeIQgChknDVmIdQEFDIEWkCqBEwOVfIEcjUYWKYQT X-IronPort-AV: E=Sophos;i="4.80,761,1344204000"; d="scan'208";a="162148497" Received: from mail-pa0-f54.google.com ([209.85.220.54]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 12 Nov 2012 12:24:32 +0100 Received: by mail-pa0-f54.google.com with SMTP id bi1so5327717pad.27 for ; Mon, 12 Nov 2012 03:24:30 -0800 (PST) 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 :content-type:content-transfer-encoding; bh=MWm1wGEDLoa6mVL+ZuWu+LKFZCFzRHvhgHdMA9K5T6c=; b=OjuFHJP/6sTku3BvdRzJly9FYsR/zXnyyOTWTnpQ9nAt8NmyRC0LTkyiqFWUDuu1AZ q0yhkASXbUv4h2MaCy0CLaDU5PA00wLyb/JWQe/hg7ydwqN1+Ni6U3iUvB8oc3WtTaz2 S1DFOVX0Ci76LperUZRe8V97MeQQyau3TpMjVq98YJKpVb1hly0IwmcjMGIFdSli7vpZ cnOO8f8uwyg6lmAM3b2TaOJNqjjV5xZ+LrKAVE4SjzLZygIgDuth+E5IWo4EePmtAm5z 9wDjibzX6vnUXsOSJtbRUck+0vEeQjs+ulGm7vt134SItqdNxL2/+gIdWcIUCzb6ymv1 0cdA== MIME-Version: 1.0 Received: by 10.68.231.69 with SMTP id te5mr56124978pbc.81.1352719470395; Mon, 12 Nov 2012 03:24:30 -0800 (PST) Received: by 10.66.146.68 with HTTP; Mon, 12 Nov 2012 03:24:30 -0800 (PST) In-Reply-To: References: Date: Mon, 12 Nov 2012 13:24:30 +0200 Message-ID: From: Dmitry Grebeniuk To: Jean-Baptiste Jeannin Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Subject: Re: [Caml-list] Cyclic data structures: internal representation Hello. > - 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 su= blist has already been seen. But it's rather heavy. > - the documentation on the =3D sign (http://caml.inria.fr/pub/docs/manual= -ocaml/libref/Pervasives.html) mentions that "Equality between cyclic data = structures may not terminate." It seems to terminate if one or the other of= the data structures is not cyclic. Does it ever terminate when both data s= structures are cyclic, or does it always loop? Both these questions are solved with my library ocaml-cyclist: https://forge.ocamlcore.org/projects/ocaml-cyclist/ I don't remember exact details, but generally I use "tortoise and hare" algorithm. Also note that lists with a cycle can also contain some prefix that doesn't appear in the cycle (it happens when list with cycle is appended to "linear" list). That's also covered by ocaml-cyclist: value length : list 'a -> (int * int); (** Returns [(prefix_len, cycle_len)] of the argument. (0, 0) for empty list, (n, 0) for linear list, (0, n) for circular list, (n, m) for generic-shaped cyclic list. (n, m > 0) *) As for equality, you can use value for_all2 : ?strict:bool -> ('a -> 'b -> bool) -> list 'a -> list 'b -> bool; to write the code like let list_eq a b =3D Cyclist.for_all2 ~strict:true ( =3D ) a b which will run correctly. However, the following lists will be considered equal: [{1; 2; 3}] and [1; 2; {3; 1; 2; 3; 1; 2}] (curly braces denote the cycle of list; it's for illustration purposes only). Using other library functions you can strenghten your equality relation.