• #### Faster remove-duplicates with sorted list.

From Robert L.@21:1/5 to All on Fri Feb 11 16:55:32 2022
(defun uniquify-sorted-list (list &key (key #'identity) (test #'eql))
(loop for element in list
for element-key = (funcall key element)
then element-key
unless (funcall test element-key last-element-key)
collect element))

Gauche Scheme:

(define (destutter seq :optional (test equal?) (key values))
(if (or (null? seq) (null? (cdr seq)))
seq
(let ((ab (take seq 2)))
(if (apply test (map key ab))
(destutter (cdr seq) test key)
(cons (car ab) (destutter (cdr seq) test key))))))

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

(destutter '(0 0 2 3 5 7 6 8) eq? odd?)
===>
(2 7 8)

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From B. Pym@21:1/5 to All on Wed Jun 19 15:18:17 2024
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)
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)

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From B. Pym@21:1/5 to Pierre R. Mai on Wed Jun 19 18:47:31 2024
"Pierre R. Mai" wrote:

(defun uniquify-sorted-list (list &key (key #'identity) (test #'eql))
(loop for element in list
for element-key = (funcall key element)
then element-key
unless (funcall test element-key last-element-key)
collect element))

Testing under SBCL:

(defun uniquify-sorted-list (list &key (key #'identity) (test #'eql))
(loop for element in list
for element-key = (funcall key element)
then element-key
unless (funcall test element-key last-element-key)
collect element))

(uniquify-sorted-list '(a b b c d d e f f f g))
===>
(A)

(uniquify-sorted-list '(2 2 3 4 4 4 5 5 6 7))
===>
(2)

(uniquify-sorted-list '(2 2 3 4 4 4 5 5 6 7) :test #'=)
===>
debugger invoked on a SIMPLE-TYPE-ERROR in thread
Argument Y is not a NUMBER: #:G5

It seems that except in the first pass through the loop
"last-element-key" is always equal to "element-key".

Again we have proof of the unusability of Common Lisp and, in
particular, Loop.

Again we have proof of the mindless arrogance of fans of
Common Lisp. That complex chunk of code was not tested even
once by its author.

Paul Graham:

I consider Loop one of the worst flaws in CL, and an example
to be borne in mind by both macro writers and language designers.

[In "ANSI Common Lisp", Graham makes the following comments:]

The loop macro was originally designed to help inexperienced
Lisp users write iterative code. Instead of writing Lisp code,
you express your program in a form meant to resemble English,
and this is then translated into Lisp. Unfortunately, loop is
more like English than its designers ever intended: you can
use it in simple cases without quite understanding how it
works, but to understand it in the abstract is almost
impossible.
....
the ANSI standard does not really give a formal specification
of its behavior.
....
The first thing one notices about the loop macro is that it
has syntax. A loop expression contains not subexpressions but
clauses. The clauses are not delimited by parentheses;
instead, each kind has a distinct syntax. In that, loop
resembles traditional Algol-like languages. But the other
distinctive feature of loop, which makes it as unlike Algol as
Lisp, is that the order in which things happen is only
loosely related to the order in which the clauses occur.
....
For such reasons, the use of loop cannot be recommended.

Dan Weinreb, one of the designers of Common Lisp:

... the problem with LOOP was that it turned out to be hard to
predict what it would do, when you started using a lot of
different facets of LOOP all together. This is a serious problem
since the whole idea of LOOP was to let you use many facets
together; if you're not doing that, LOOP is overkill.

Barry Margolin:

My recommendation is based on seeing many question in the past
of the form "What happens if you use both XXX and YYY in the
same LOOP?" The unfortunate fact is that when we were writing
the standard we didn't have time to nail down all the possible
interactions between different LOOP features, so many of these
are not well specified. And even if we did get it right in
the standard, it's likely to be difficult to find them and I
wouldn't trust that all implementors got it right (many of
those questions were probably from implementors, trying to
figure out what they were supposed to do). And even if they
all got it right, someone reading your code may not be able to
figure it out.

So, with all those potential problems, my feeling is that if
you have to ask, it's probably better to use something other
than LOOP.

John Foderaro:

I'm not trying to join a debate on loop. I just wanted to present
the other side of [the issue so that] the intelligent people can
then weigh the arguments on both sides.

I'm not suggesting that loop can be fixed either by adding
parenthesis or coming up with ways of indenting it to make it
understandable. It's a lost cause.

...

Another great example from kmp:

=== from kmp

For example, you might think
(loop with i = (random 100) for x from 1 to 10 do (print (list i x)))
and
(loop for i = (random 100) for x from 1 to 10 do (print (list i x)))
meant the same in English, [but they don't do the same thing in loop]

=== end kmp

loop lulls you into thinking that you understand the program since
you understand English. Make no mistake about it, loop is its
own language. If you use it you condem everyone who reads the
code to also learn the loop language.

Gauche Scheme

(use gauche.collection) ;; fold2

(define (uniquify-sorted-list lst :key (key identity) (test equal?))
(define (cons-non-dup x accum old-x-key)
(let ((x-key (key x)))
(values
(if (or (null? accum) (not (test x-key old-x-key)))
(cons x accum)
accum)
x-key)))
(reverse
(fold2
cons-non-dup
'() #f
lst)))

(uniquify-sorted-list '(a b b c d d e f f f g))
===>
(a b c d e f g)

(uniquify-sorted-list '(#f a b b c d d e f f f g #f))
===>
(#f a b c d e f g #f)

(uniquify-sorted-list '(2 2 3 4 4 4 5 5 6 7))
===>
(2 3 4 5 6 7)

(uniquify-sorted-list '(2 2 3 4 4 4 5 5 6 7) :test =)
===>
(2 3 4 5 6 7)

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Joerg Mertens@21:1/5 to B. Pym on Fri Jun 21 12:22:31 2024
B. Pym <No_spamming@nowhere_7073.org> wrote:
"Pierre R. Mai" wrote:

(defun uniquify-sorted-list (list &key (key #'identity) (test #'eql))
(loop for element in list
for element-key = (funcall key element)
then element-key
unless (funcall test element-key last-element-key)
collect element))

Testing under SBCL:

(defun uniquify-sorted-list (list &key (key #'identity) (test #'eql))
(loop for element in list
for element-key = (funcall key element)
then element-key
unless (funcall test element-key last-element-key)
collect element))

(uniquify-sorted-list '(a b b c d d e f f f g))
===>
(A)

(uniquify-sorted-list '(2 2 3 4 4 4 5 5 6 7))
===>
(2)

(uniquify-sorted-list '(2 2 3 4 4 4 5 5 6 7) :test #'=)
===>
debugger invoked on a SIMPLE-TYPE-ERROR in thread
Argument Y is not a NUMBER: #:G5

(defun uniquify-sorted-list (list &key (key #'identity) (test #'eql))
(loop for element in list
for last-element-key = nil then element-key
for element-key = (funcall key element)
for result = nil then (funcall test element-key last-element-key)
unless result collect element))

Tested with GNU Clisp:

(uniquify-sorted-list '(a b b c d d e f f f g))
(A B C D E F G)
(uniquify-sorted-list '(2 2 3 4 4 4 5 5 6 7))
(2 3 4 5 6 7)
(uniquify-sorted-list '(2 2 3 4 4 4 5 5 6 7) :test #'=)
(2 3 4 5 6 7)

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Joerg Mertens@21:1/5 to Joerg Mertens on Fri Jun 21 21:42:07 2024
Joerg Mertens <joerg-mertens@t-online.de> wrote:

(loop for element in list
for last-element-key = nil then element-key
for element-key = (funcall key element)
for result = nil then (funcall test element-key last-element-key)
unless result collect element))

This is clearer:

(defun uniquify-sorted-list (list &key (key #'identity) (test #'eql))
(loop for element in list
for element-key = (funcall key element)
and last-element-key = nil then element-key
for result = nil then (funcall test element-key last-element-key)
unless result collect element))

I forgot that the loop way to step two clauses in parallel is to
combine them with an `andÂ´.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)