Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: "B. Pym" <No_spamming@noWhere_7073.org>
Newsgroups: comp.lang.lisp
Subject: Re: Faster remove-duplicates with sorted list.
Date: Wed, 19 Jun 2024 15:18:17 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 41
Message-ID: <v4usrm$21fur$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Injection-Date: Wed, 19 Jun 2024 17:18:17 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="a0e44262dbf0ff3ef7cd29835841a1f0";
	logging-data="2146267"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX187JILPxrr+urVaHBfGG2lg"
User-Agent: XanaNews/1.18.1.6
Cancel-Lock: sha1:I2OhEolrIaw7KEEMO9frKsulPaE=
Bytes: 1924

> > I believe that remove-duplicates has to assume that the list is not
> > sorted. Therefore it has to compare each element, element by element
> > ( ~N^2 ). Whereas a side by side goes like 2*N.
> >
> > The only problem I have is excessive consing which significantly slows
> > down the algorithm.
> 
> (defun uniquify-sorted-list (list &key (key #'identity) (test #'eql))
>   (loop for element in list
>         for element-key = (funcall key element)
>         for last-element-key = (load-time-value (gensym))
>         then element-key
>         unless (funcall test element-key last-element-key)
>         collect element))

Gauche Scheme

(use srfi-1)  ;; pair-fold

(pair-fold
  (lambda (xs accum)
    (if (and (pair? (cdr xs)) (apply equal? (take xs 2)))
      accum
      (cons (car xs) accum)))
  '()
  '(0 0 1 2 3 3 3 4 5 5))

  ===>
(5 4 3 2 1 0)


(pair-fold
  (lambda (xs accum)
    (if (and (pair? (cdr xs)) (apply equal? (take xs 2)))
      accum
      (cons (car xs) accum)))
  '()
  '(0 1 2 3 3 3 4 5))

  ===>
(5 4 3 2 1 0)