From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mp1 ([2001:41d0:2:4a6f::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by ms0.migadu.com with LMTPS id WOwgIh/GVWEVWQAAgWs5BA (envelope-from ) for ; Thu, 30 Sep 2021 16:13:51 +0200 Received: from aspmx1.migadu.com ([2001:41d0:2:4a6f::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by mp1 with LMTPS id 2BmqHR/GVWGBWgAAbx9fmQ (envelope-from ) for ; Thu, 30 Sep 2021 14:13:51 +0000 Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by aspmx1.migadu.com (Postfix) with ESMTPS id 4B39BB829 for ; Thu, 30 Sep 2021 16:13:51 +0200 (CEST) Received: from localhost ([::1]:42598 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1mVwoo-0001Zd-C0 for larch@yhetil.org; Thu, 30 Sep 2021 10:13:50 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:46012) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1mVwo2-0000LA-Cp for guix-patches@gnu.org; Thu, 30 Sep 2021 10:13:02 -0400 Received: from debbugs.gnu.org ([209.51.188.43]:42036) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1mVwo2-0004tx-64 for guix-patches@gnu.org; Thu, 30 Sep 2021 10:13:02 -0400 Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1mVwo1-00015A-V6 for guix-patches@gnu.org; Thu, 30 Sep 2021 10:13:01 -0400 X-Loop: help-debbugs@gnu.org Subject: [bug#50878] [PATCH] union: Resolve collisions by stable-sort'ing them. Resent-From: Attila Lendvai Original-Sender: "Debbugs-submit" Resent-CC: guix-patches@gnu.org Resent-Date: Thu, 30 Sep 2021 14:13:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 50878 X-GNU-PR-Package: guix-patches X-GNU-PR-Keywords: patch To: Maxime Devos Cc: Liliana Marie Prikler , 50878@debbugs.gnu.org Received: via spool by 50878-submit@debbugs.gnu.org id=B50878.16330111644130 (code B ref 50878); Thu, 30 Sep 2021 14:13:01 +0000 Received: (at 50878) by debbugs.gnu.org; 30 Sep 2021 14:12:44 +0000 Received: from localhost ([127.0.0.1]:53582 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mVwnj-00014X-Lg for submit@debbugs.gnu.org; Thu, 30 Sep 2021 10:12:43 -0400 Received: from mail1.protonmail.ch ([185.70.40.18]:21316) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mVwnf-00014A-8O for 50878@debbugs.gnu.org; Thu, 30 Sep 2021 10:12:42 -0400 Date: Thu, 30 Sep 2021 14:12:31 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=lendvai.name; s=protonmail2; t=1633011152; bh=Duif9VAc48Siy2q8Q+EzT/v0Rg0DydqD0AKXWosJQLQ=; h=Date:To:From:Cc:Reply-To:Subject:In-Reply-To:References:From; b=Apm/84eFU7jyg7BNXgX19qs5Gok9V5s3reHnHZxxPyToA8TO51gXW1tkpjhGy7T+Y Ji6k0Nqjit9yQHogafxwRtrn10SESpZf43fkb35JnsfgEVScL0Eyqr8KiQwRJ1r9Wf 57iFcetccNFvBiCGGaSOk6xTAqigIsLkkzNYUtIsKnRqxzKTX78k4vhBo7Wt8D2Spo aGCoiIorYQxno6mArF/VipJlEthanioBDvHpXJDQ754zGP2TnIhO3jI/SqeDzgUMna qcpgjQbbar8zEYgzxapQzcF/nT3bo3qNqr/GAaWK91Ez30HZ89lJu72S3sJpPUMZcF iGSdk23ZE3nbA== From: Attila Lendvai Message-ID: In-Reply-To: <9ab183637e8cd645267a37ba0f05319f8b3c72ff.camel@telenet.be> References: <20210928214044.437-1-attila@lendvai.name> <57f1435fd83da8c0e0acaef64d5f08e4ca7b3404.camel@gmail.com> <9ab183637e8cd645267a37ba0f05319f8b3c72ff.camel@telenet.be> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: guix-patches@gnu.org List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: Attila Lendvai Errors-To: guix-patches-bounces+larch=yhetil.org@gnu.org Sender: "Guix-patches" X-Migadu-Flow: FLOW_IN ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=yhetil.org; s=key1; t=1633011231; h=from:from:sender:sender:reply-to:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding:resent-cc: resent-from:resent-sender:resent-message-id:in-reply-to:in-reply-to: references:references:list-id:list-help:list-unsubscribe: list-subscribe:list-post:dkim-signature; bh=Duif9VAc48Siy2q8Q+EzT/v0Rg0DydqD0AKXWosJQLQ=; b=R45Ph/lnSsJHIf0HdAJTeKtNVuC/3ixk4CsBWk9Z2tkU9Qsnzq0qPFHWlbzlSsKEZZeqc8 3Sb+/1R1VtWvDM/tsvD1yfD5ndjHh288nIjKOs2LXCI8wecp1fT80e8x/tXLaPSBrg+ptO GjklcG/elDZCl8tHFgbQPjrPMw85lyS785wMkr8x3WfKzgDS6ks0898zi0fv7EwAs6+5In td4bW5h7sMRD9ZT/hNULWaD4R52Js178JNan6qz+Lu2x5Elrve92XSocxHC5xBbVSnS0p/ jVMU399i8OdtEYbACDFMS2cqzGXCePeSvsOkRFKHl8yAVhUlOfeeeFM8mTRsYg== ARC-Seal: i=1; s=key1; d=yhetil.org; t=1633011231; a=rsa-sha256; cv=none; b=Cd+CcPZ/dRKkweQ2R1vDT1GcNMLkLMaRohxAbd1zpNKADX+1PxIIHbuyMDm9uHxq4iajik 9H2w571v1dgLOh4ApmnM2O6aFZoJvQYY3nTQqE5NWP26cWms7edVulJu9ZFYSk5sZwbUtL COLoTg6qSMmUfYkVBAZkJCtsU2hqVpP7wTRzlY4x6cwxhDl+uuTPUd4Zjk/aQluVEktiNC 9qv+Xl5lNRNzcKV6eB4hkMWsoJl1/aUhMGceAMIAPdibf68uN7DhZbjvVoH0v/+BPeoPvy /5PcX/CUg6i38t83+gowUZmOTPJdH1s7Tphx8wwjOuJFfOKOoYh11M9Lq65m4Q== ARC-Authentication-Results: i=1; aspmx1.migadu.com; dkim=fail ("headers rsa verify failed") header.d=lendvai.name header.s=protonmail2 header.b="Apm/84eF"; dmarc=none; spf=pass (aspmx1.migadu.com: domain of guix-patches-bounces@gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=guix-patches-bounces@gnu.org X-Migadu-Spam-Score: -1.40 Authentication-Results: aspmx1.migadu.com; dkim=fail ("headers rsa verify failed") header.d=lendvai.name header.s=protonmail2 header.b="Apm/84eF"; dmarc=none; spf=pass (aspmx1.migadu.com: domain of guix-patches-bounces@gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=guix-patches-bounces@gnu.org X-Migadu-Queue-Id: 4B39BB829 X-Spam-Score: -1.40 X-Migadu-Scanner: scn0.migadu.com X-TUID: r573c6U/RS50 > > the hash also needs to be dropped from the path for sorting to be > > useful, but the return value must be the full path, hence the > > complexity with sorting the indices, pointing both to the full paths > > and the cut parts. > > You can replace the 'less' argument of 'stable-sort'. > Example sorting by the second character of a string: > > (sort '("za" "yb" "xc") (lambda (x y) > (char>? (string-ref x 1) > (string-ref y 1))))) i don't know about the expected size of the collision list here, but that would cons much more, because that would cons up two substrings at each comparison, i.e. O(n^2) vs O(n) at least in GC load, probably in time also. i think it's not worth it, but let me know, and then i can simplify the code somewhat at the cost of more consing. sorting lists is probably also much slower than sorting vectors, but there may be some tricks i don't know about. random note: civodul said on IRC that there's a certain reluctancy to update the opaque binary blobs, and the bootstrap guile will be replaced by mes anyway. so, if we want to have this merged, then we will need to give up on testing it until mes becomes the bootstrap scheme (and assuming it will have srfi vectors). in the lights of the above, i think i'll stop pursuing this patch, but i'd be happy to implement something if you can give me highlevel guidance. with the above pointed out, are you still happy with the list sorting? i'd love to have idris packaged so that it has bin/idris symlinked to bin/idris-1.2.3, and installing multiple versions of it would pick the newest one for bin/idris. -- =E2=80=A2 attila lendvai =E2=80=A2 PGP: 963F 5D5F 45C7 DFCD 0A39 -- =E2=80=9CHave the courage to take your own thoughts seriously, for they wil= l shape you.=E2=80=9D =09=E2=80=94 Albert Einstein (1879=E2=80=931955)