From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 D36517F3B1 for ; Tue, 25 Feb 2020 20:05:02 +0100 (CET) Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=yann.salmon@prepas.science; spf=None smtp.mailfrom=yann.salmon@prepas.science; spf=None smtp.helo=postmaster@mo29.mail-out.ovh.net Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of yann.salmon@prepas.science) identity=pra; client-ip=178.32.228.29; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="yann.salmon@prepas.science"; x-sender="yann.salmon@prepas.science"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of yann.salmon@prepas.science) identity=mailfrom; client-ip=178.32.228.29; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="yann.salmon@prepas.science"; x-sender="yann.salmon@prepas.science"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mo29.mail-out.ovh.net) identity=helo; client-ip=178.32.228.29; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="yann.salmon@prepas.science"; x-sender="postmaster@mo29.mail-out.ovh.net"; x-conformance=sidf_compatible IronPort-PHdr: =?us-ascii?q?9a23=3AsTT3fRZEjI6pa3O9dEK063f/LSx+4OfEezUN459i?= =?us-ascii?q?sYplN5qZpsy6bB7h7PlgxGXEQZ/co6odzbaP7+axAydZuMbJmUtBWaIPfidNsd?= =?us-ascii?q?8RkQ0kDZzNImzAB9muURYHGt9fXkRu5XCxPBsdMs//Y1rPvi/6tmZKSV3wOgVv?= =?us-ascii?q?O+v6BJPZgdip2OCu4Z3TZBhDiCagbb9oIxi6sArcutMSjId8Jao91wbFr3hVcO?= =?us-ascii?q?lK2G1kIk6ekBn76sqs5pBo7j5eu+gm985OUKX6e7o3QLlFBzk4MG47+dPmuwDb?= =?us-ascii?q?QQSA+nUTXGMWkgFVAwfe9xH1Qo3xsirhueVj3iSRIND7Qqo1WTSm6KdrVQPohS?= =?us-ascii?q?IaPDM37G3blsp9h79drRm8pRJw3pTUbZmLOvR+Y63Tft0USmROUclNWCJMGZ+8?= =?us-ascii?q?YogVAuYdIepVoYvwql0TphW+HwmsA+bvxydKiXDs26061fkqHxzc0wwkGtIOt3?= =?us-ascii?q?LUp8jyOaYSS++1yq/IwS/Yb/xM3Tf97Y/IchY6rPGUR7J/b9LRxlM0Fw/flVWf?= =?us-ascii?q?tY3lMC2T1usRrWeW9uxtXv+hhW4grgF+uDmvxsE0h4jJnI0VzFbE9T5jz4YxIN?= =?us-ascii?q?24T0h7bcSqEJtKsSyRKoh4Qts6Tm11uis3yacKtJClcCQQ1pgr2R3SZ+aZf4WM?= =?us-ascii?q?+h7uV/idLS1miH9qeb+znRa//Va6xuD8S8W4yEpGojBZntXWqnwBzQDf586aQf?= =?us-ascii?q?Zj+kehxC2P1xzN5eFePE40lKvaJIA5z7IskJcYrF7NETXsmErsia+bbkUk9fas?= =?us-ascii?q?6+Tgerjmo5icO5Fwhw3kN6QhgM2/AeAhPggJQmib5f6w1Lr9/U35WrlKiOM5kr?= =?us-ascii?q?XBvJDbI8QUuLK5DhdI3osh6BuzFTmr3MoCkXUZMl5IewiLg5btNl3WJfD3F/a/?= =?us-ascii?q?g1CikDdxwPDGO6XsA5XXIXjFlrftZ6195FRYyAo2ytBf4YlZCqkbIP3tQk/+rs?= =?us-ascii?q?fYAgUiMwOowuboFtN92Z8AVm6XGK+WLLvSsUOU5uIoO+SDeJUauDP5K/Q84/7u?= =?us-ascii?q?jGQ5mUMGcKmy3ZoXbWi4Ee58L0WYZ3rsmNYBHn0QsgowVuzmkFiCUTlOaHmsR6?= =?us-ascii?q?88/TQ7CJ6+DYvaQYCtnaCB0D+7HpJIYmBGDUiBEXf2eImaRfsAcieSLdVgkjwA?= =?us-ascii?q?T7ShTJEh1RG0uA/81bVnMvLY+iwetZ39yNh4//HfmQsu+TBuE8iRyX2BQ3lunm?= =?us-ascii?q?wUXz82wLx/oUtlx1ify6d4hvhYGcVX5/NISQc6KYXRz+18C9DoWwLOZM2FSFi8?= =?us-ascii?q?QobuPTZkRds0x5oKYl1hM9SklBHKmSSwUJEPkLneNZUy9Orn1nz0IMA1n2fP0q?= =?us-ascii?q?9nlFAiR8xJHXW8i7Z27E7IDI/ElU6UwfX5PZ8A1TLAoT/QhVGFu1tVBVYpDff1?= =?us-ascii?q?GEsHb06TluzXo1vYRubwW6w9PxNI0oiZIapHbNbk3w0fGaXTfe/Gamf0oF+eQB?= =?us-ascii?q?aFwrTWN9jvfD9MmiDUCUxBlB0Pu3GYNU44Czvz+zuPXgwrLkrmZgbXycc7rXq6?= =?us-ascii?q?SkEuyATTMR95zbet8wVTnvedRvUY0+BctQ=3D=3D?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0DcVgCOb1VefR3kILJlHAEBASgJAQYBB?= =?us-ascii?q?AQBAQIBBwEBgVWBPgKBUwNTMYN+QI8KbIEAhBOXTwkBAwEMHxAEAQGETYFzHAY?= =?us-ascii?q?GNBMCEAEBBQEBAQIBAgMEARMBAQsUCBsIAYVDDII7IoMZFw8BXxwCJgJsCAEBg?= =?us-ascii?q?yIBgn+SXJt5gTKFSoMzgRsdBoEOKAIBAYwiD4FMP4ERJwyCYIVWgkSCXgSwEQU?= =?us-ascii?q?Hgj8EdASGVYgxhl0GHII5jFKMI4RWkxaSc4FpgXozGoNgTxgNk06JGEGPOAEB?= X-IPAS-Result: =?us-ascii?q?A0DcVgCOb1VefR3kILJlHAEBASgJAQYBBAQBAQIBBwEBgVW?= =?us-ascii?q?BPgKBUwNTMYN+QI8KbIEAhBOXTwkBAwEMHxAEAQGETYFzHAYGNBMCEAEBBQEBA?= =?us-ascii?q?QIBAgMEARMBAQsUCBsIAYVDDII7IoMZFw8BXxwCJgJsCAEBgyIBgn+SXJt5gTK?= =?us-ascii?q?FSoMzgRsdBoEOKAIBAYwiD4FMP4ERJwyCYIVWgkSCXgSwEQUHgj8EdASGVYgxh?= =?us-ascii?q?l0GHII5jFKMI4RWkxaSc4FpgXozGoNgTxgNk06JGEGPOAEB?= X-Spam-Status: Yes X-IronPort-AV: E=Sophos;i="5.70,485,1574118000"; d="scan'208";a="340413431" X-MGA-submission: =?us-ascii?q?MDHLNc2gIDeYLtUksPIW4XZpsPFTnRksWqV8c6?= =?us-ascii?q?eb2zSv+NKXxxxZ6n4fxTLXIoO3eeQ/8AnVEN1Y+FcAWNs7QgToquv4Mk?= =?us-ascii?q?UEXcIBrwlPaVbq0O9WqKpj/tvRPWGQcnmNrFLksLqsx5eSwSkZbyrUWE?= =?us-ascii?q?VMeU7defiz41uT2or+Z0/Usg=3D=3D?= Received: from mo29.mail-out.ovh.net ([178.32.228.29]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 25 Feb 2020 20:05:02 +0100 Received: from he22.mail.ovh.net (he22.mail.ovh.net [46.105.67.157]) by mo29.mail-out.ovh.net (Postfix) with ESMTP id B0D6051B15 for ; Tue, 25 Feb 2020 20:05:00 +0100 (CET) Received: from [192.168.0.40] (unknown [82.246.52.51]) by he22.mail.ovh.net (Postfix) with ESMTPSA id 76E0A3C5FF2 for ; Tue, 25 Feb 2020 20:05:00 +0100 (CET) To: caml-list@inria.fr From: Yann Salmon Message-ID: <9ab4107b-0dfe-26b6-6502-871b8fd26ce1@prepas.science> Date: Tue, 25 Feb 2020 20:05:00 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.4.1 MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 8bit X-Ovh-Tracer-Id: 8060317435554906399 X-VR-SPAMSTATE: OK X-VR-SPAMSCORE: 0 X-VR-SPAMCAUSE: gggruggvucftvghtrhhoucdtuddrgedugedrledvgdduudelucetufdoteggodetrfdotffvucfrrhhofhhilhgvmecuqfggjfdpvefjgfevmfevgfenuceurghilhhouhhtmecuhedttdenucenucfjughrpefvhffukffffgggtgfgsehtkeertddtfeejnecuhfhrohhmpegjrghnnhcuufgrlhhmohhnuceohigrnhhnrdhsrghlmhhonhesphhrvghprghsrdhstghivghntggvqeenucffohhmrghinhephigrnhhnshgrlhhmohhnrdhfrhenucfkpheptddrtddrtddrtddpkedvrddvgeeirdehvddrhedunecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehmohguvgepshhmthhpqdhouhhtpdhhvghlohephhgvvddvrdhmrghilhdrohhvhhdrnhgvthdpihhnvghtpedtrddtrddtrddtpdhmrghilhhfrhhomhephigrnhhnrdhsrghlmhhonhesphhrvghprghsrdhstghivghntggvpdhrtghpthhtoheptggrmhhlqdhlihhsthesihhnrhhirgdrfhhr Subject: [Caml-list] Time complexity of Queue.length Greetings, the OCaml standard library documents Stack.length to be O(1). This is not guaranteed by the documentation of Queue.length, although the current implementation is just reading the relevant field in the structure and is therefore O(1). I wonder what is the reason for this apparent discrepancy. Is it to allow for a radical change of Queue implementation in the future ? -- Cordialement, Yann Salmon Professeur agrégé Informatique en CPGE Lycée Descartes - Tours