From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: David Kastrup Newsgroups: gmane.emacs.devel Subject: Re: `remove-duplicates' Date: Sun, 10 Jul 2011 18:06:14 +0200 Organization: Organization?!? Message-ID: <877h7q6ryh.fsf@fencepost.gnu.org> References: NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Trace: dough.gmane.org 1310314417 15630 80.91.229.12 (10 Jul 2011 16:13:37 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Sun, 10 Jul 2011 16:13:37 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Jul 10 18:13:33 2011 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([140.186.70.17]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1QfwdN-0006J8-9l for ged-emacs-devel@m.gmane.org; Sun, 10 Jul 2011 18:13:29 +0200 Original-Received: from localhost ([::1]:34750 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QfwdL-00088p-He for ged-emacs-devel@m.gmane.org; Sun, 10 Jul 2011 12:13:27 -0400 Original-Received: from eggs.gnu.org ([140.186.70.92]:36141) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QfwWd-0006SG-O7 for emacs-devel@gnu.org; Sun, 10 Jul 2011 12:06:32 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1QfwWa-00007A-1Y for emacs-devel@gnu.org; Sun, 10 Jul 2011 12:06:31 -0400 Original-Received: from lo.gmane.org ([80.91.229.12]:47442) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QfwWZ-000074-Ie for emacs-devel@gnu.org; Sun, 10 Jul 2011 12:06:27 -0400 Original-Received: from list by lo.gmane.org with local (Exim 4.69) (envelope-from ) id 1QfwWY-0002vm-6C for emacs-devel@gnu.org; Sun, 10 Jul 2011 18:06:26 +0200 Original-Received: from p508eb251.dip.t-dialin.net ([80.142.178.81]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Sun, 10 Jul 2011 18:06:26 +0200 Original-Received: from dak by p508eb251.dip.t-dialin.net with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Sun, 10 Jul 2011 18:06:26 +0200 X-Injected-Via-Gmane: http://gmane.org/ Original-Lines: 49 Original-X-Complaints-To: usenet@dough.gmane.org X-Gmane-NNTP-Posting-Host: p508eb251.dip.t-dialin.net X-Face: 2FEFf>]>q>2iw=B6, xrUubRI>pR&Ml9=ao@P@i)L:\urd*t9M~y1^:+Y]'C0~{mAl`oQuAl \!3KEIp?*w`|bL5qr,H)LFO6Q=qx~iH4DN; i"; /yuIsqbLLCh/!U#X[S~(5eZ41to5f%E@'ELIi$t^ Vc\LWP@J5p^rst0+('>Er0=^1{]M9!p?&:\z]|;&=NP3AhB!B_bi^]Pfkw User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.0.50 (gnu/linux) Cancel-Lock: sha1:8fSThv4FcRrPkDQ9PTsHVCL9/OI= X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-Received-From: 80.91.229.12 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:141911 Archived-At: Juanma Barranquero writes: > On Sun, Jul 10, 2011 at 17:05, Lars Magne Ingebrigtsen wrote: > >> Would anybody mind if I add a simple version of `remove-duplicates' to >> subr.el?  I'm tired of rewriting the same loop... > > I think there are also quite a few cases in the sources of destructive > deleting of *consecutive* duplicates. I once proposed this: > > (defun uniqify (list) > "Destructively remove consecutive `equal' duplicates from LIST. > Store the result in LIST and return it. LIST must be a proper list." > (let ((l list)) > (while (cdr l) > (if (equal (car l) (cadr l)) > (setcdr l (cddr l)) > (setq l (cdr l)))) > list)) I have something like this here: (defun uniquify (list predicate) (let* ((p list) lst (x1 (make-symbol "x1")) (x2 (make-symbol "x2"))) (while p (push p lst) (setq p (cdr p))) ;;; (princ lst)(princ "\n") (setq lst (sort lst `(lambda(,x1 ,x2) (funcall ',predicate (car ,x1) (car ,x2))))) ;;; lst now contains all sorted sublists, with equal cars being ;;; sorted in order of increasing length (from end of list to start). ;; (while (cdr lst) (unless (funcall predicate (car (car lst)) (car (cadr lst))) (setcar (car lst) x1)) (setq lst (cdr lst))) (delq x1 list))) One could turn the predicate into an optional argument. The idea is that with an order relation (in this case "less"), the behavior can be turned from O(n^2) to O(n log n). Another possibility would be to remove duplicates by using hashes. -- David Kastrup