From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by c5ff346549e7 (Postfix) with ESMTPS id 3627D5D4 for ; Tue, 25 Feb 2020 19:05:08 +0000 (UTC) X-IronPort-AV: E=Sophos;i="5.70,485,1574118000"; d="scan'208";a="437637050" Received: from sympa.inria.fr ([193.51.193.213]) by mail2-relais-roc.national.inria.fr with ESMTP; 25 Feb 2020 20:05:07 +0100 Received: by sympa.inria.fr (Postfix, from userid 20132) id 3C4A87F42C; Tue, 25 Feb 2020 20:05:07 +0100 (CET) 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 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-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 Reply-To: Yann Salmon X-Loop: caml-list@inria.fr X-Sequence: 18016 Errors-to: caml-list-owner@inria.fr Precedence: list Precedence: bulk Sender: caml-list-request@inria.fr X-no-archive: yes List-Id: List-Archive: List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: 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