From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mp0.migadu.com ([2001:41d0:303:5f26::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by ms8.migadu.com with LMTPS id WPFGH4RsmGWNhQAAkFu2QA (envelope-from ) for ; Fri, 05 Jan 2024 21:54:28 +0100 Received: from aspmx1.migadu.com ([2001:41d0:303:e224::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by mp0.migadu.com with LMTPS id QLAlHIRsmGXH4gAAqHPOHw (envelope-from ) for ; Fri, 05 Jan 2024 21:54:28 +0100 X-Envelope-To: larch@yhetil.org Authentication-Results: aspmx1.migadu.com; dkim=none; spf=pass (aspmx1.migadu.com: domain of "guix-patches-bounces+larch=yhetil.org@gnu.org" designates 209.51.188.17 as permitted sender) smtp.mailfrom="guix-patches-bounces+larch=yhetil.org@gnu.org"; dmarc=none ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=yhetil.org; s=key1; t=1704488068; h=from:from:sender:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: 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; bh=SfB6vmFQ/S2yv6ZLA7bfPXHbNrH52mdFxaCxAa/kpCY=; b=O3bFq/nNRzDO8ALoUbFQEWd15S/tO6CMs4fCEf27oPjezN7zC9KPZ69nse+4CrDnU397dp 1Ar2wmvu6GXAd9D6kwfv+4dxsUUkH9uXl+GkMRCjqr8emPX/UYgCW300TvCGX6RbiAJBsr NmwNCvELCsuVqg4OqT75J0BilV0zto77SxXIA/GCYjfu1fr444JJPBR/DWP/tgmnHAobfO 7G9K2j5dXi1ULJpfTj/QVfBKW/DaoHFnzn6ifPDZffIEPUOBNdGnE7D54NCAFsp4nPvGC6 8OoSLOo/arfn20tOkRkJVu8YCHzhZ3v9yy5dxmJrwUASrf32J1oRaJ7ZTPOa1g== ARC-Seal: i=1; s=key1; d=yhetil.org; t=1704488068; a=rsa-sha256; cv=none; b=VIs1UiaEU0k+/AxdiGbGWFmt5lOEvfbVsxUlqUZ7x8Q3Lh4cleHYQlnP/Bj6OTltb5FR4Z pyQvufYqEhwJjbG5++7upee5nChMQqgwt+Xulb3Av2SuJpeJOcOyPcBaGzO3gvg+cP9le3 fLl380+YuNpiihhLOVnLU//+1zFdlm4c/x8AdQZ8S14cezVDleYnIzeRys5KKKT2iYf5is yuDFwQhQ5kBxC+MFOuAfhHQrmBka63bWxCykBx221CzVhNoDpR2+9QeprZopkDgTlkMUPB cplH42dj3VvBy6w+RjaXMc3i3aeD+5tgI3dlewhq3ixWJw98xCc2ClyUBF0MSg== ARC-Authentication-Results: i=1; aspmx1.migadu.com; dkim=none; spf=pass (aspmx1.migadu.com: domain of "guix-patches-bounces+larch=yhetil.org@gnu.org" designates 209.51.188.17 as permitted sender) smtp.mailfrom="guix-patches-bounces+larch=yhetil.org@gnu.org"; dmarc=none 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 5CDD216D2D for ; Fri, 5 Jan 2024 21:54:28 +0100 (CET) Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1rLrCc-0005wa-R7; Fri, 05 Jan 2024 15:54:02 -0500 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1rLrCa-0005w4-JX for guix-patches@gnu.org; Fri, 05 Jan 2024 15:54:00 -0500 Received: from debbugs.gnu.org ([2001:470:142:5::43]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1rLrCZ-0007W5-KU; Fri, 05 Jan 2024 15:53:59 -0500 Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1rLrCb-00046d-V1; Fri, 05 Jan 2024 15:54:01 -0500 X-Loop: help-debbugs@gnu.org Subject: [bug#68271] [PATCH 1/3] guix: utils: Add delete-duplicates/sort. References: <87h6jrqzc7.fsf@cbaines.net> In-Reply-To: <87h6jrqzc7.fsf@cbaines.net> Resent-From: Christopher Baines Original-Sender: "Debbugs-submit" Resent-CC: guix@cbaines.net, dev@jpoiret.xyz, ludo@gnu.org, othacehe@gnu.org, rekado@elephly.net, zimon.toutoune@gmail.com, me@tobias.gr, guix-patches@gnu.org Resent-Date: Fri, 05 Jan 2024 20:54:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 68271 X-GNU-PR-Package: guix-patches X-GNU-PR-Keywords: patch To: 68271@debbugs.gnu.org Cc: Christopher Baines , Josselin Poiret , Ludovic =?UTF-8?Q?Court=C3=A8s?= , Mathieu Othacehe , Ricardo Wurmus , Simon Tournier , Tobias Geerinckx-Rice X-Debbugs-Original-Xcc: Christopher Baines , Josselin Poiret , Ludovic =?UTF-8?Q?Court=C3=A8s?= , Mathieu Othacehe , Ricardo Wurmus , Simon Tournier , Tobias Geerinckx-Rice Received: via spool by 68271-submit@debbugs.gnu.org id=B68271.170448801115727 (code B ref 68271); Fri, 05 Jan 2024 20:54:01 +0000 Received: (at 68271) by debbugs.gnu.org; 5 Jan 2024 20:53:31 +0000 Received: from localhost ([127.0.0.1]:58036 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1rLrC7-00045b-Ep for submit@debbugs.gnu.org; Fri, 05 Jan 2024 15:53:31 -0500 Received: from mira.cbaines.net ([212.71.252.8]:43068) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1rLrC5-00045K-90 for 68271@debbugs.gnu.org; Fri, 05 Jan 2024 15:53:30 -0500 Received: from localhost (unknown [217.155.61.229]) by mira.cbaines.net (Postfix) with ESMTPSA id 94C4E27BBE2 for <68271@debbugs.gnu.org>; Fri, 5 Jan 2024 20:53:23 +0000 (GMT) Received: from localhost (localhost [local]) by localhost (OpenSMTPD) with ESMTPA id 3df7c8f0 for <68271@debbugs.gnu.org>; Fri, 5 Jan 2024 20:53:22 +0000 (UTC) From: Christopher Baines Date: Fri, 5 Jan 2024 20:53:20 +0000 Message-ID: X-Mailer: git-send-email 2.41.0 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit 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: , Errors-To: guix-patches-bounces+larch=yhetil.org@gnu.org Sender: guix-patches-bounces+larch=yhetil.org@gnu.org X-Migadu-Flow: FLOW_IN X-Migadu-Country: US X-Migadu-Spam-Score: -3.29 X-Spam-Score: -3.29 X-Migadu-Queue-Id: 5CDD216D2D X-Migadu-Scanner: mx12.migadu.com X-TUID: hJcCWtkjwivs Similar to delete-duplicates, but sorts the list first and then compares the pairs in the list. This is faster than delete-duplicates for larger lists. * guix/utils.scm (delete-duplicates): New procedure. Change-Id: Ibc2897cdb7c76be0d0e099bc47fee005a88bea2e --- guix/utils.scm | 28 ++++++++++++++++++++++++++++ 1 file changed, 28 insertions(+) diff --git a/guix/utils.scm b/guix/utils.scm index e4e9d922e7..c1c967ee6c 100644 --- a/guix/utils.scm +++ b/guix/utils.scm @@ -146,6 +146,8 @@ (define-module (guix utils) edit-expression delete-expression + delete-duplicates/sort + filtered-port decompressed-port call-with-decompressed-port @@ -502,6 +504,32 @@ (define (delete-expression source-properties) "Delete the expression specified by SOURCE-PROPERTIES." (edit-expression source-properties (const "") #:include-trailing-newline? #t)) + +;;; +;;; Lists. +;;; + +(define* (delete-duplicates/sort unsorted-lst less #:optional (equal? eq?)) + (if (null? unsorted-lst) + unsorted-lst + (let ((sorted-lst (sort unsorted-lst + ;; Sort in the reverse order + (lambda (a b) (eq? #f (less a b)))))) + (let loop ((lst (cdr sorted-lst)) + (last-element (car sorted-lst)) + (result (list (car sorted-lst)))) + (if (null? lst) + result + (let ((current-element (car lst))) + (if (equal? current-element last-element) + (loop (cdr lst) + last-element + result) + (loop (cdr lst) + current-element + (cons current-element + result))))))))) + ;;; ;;; Keyword arguments. base-commit: deeb7d1f53d7ddfa977b3eadd760312bbd0a2509 -- 2.41.0