Re: Faster remove-duplicates with sorted list.

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)