summaryrefslogtreecommitdiff
path: root/module/srfi/srfi-1.scm
diff options
context:
space:
mode:
Diffstat (limited to 'module/srfi/srfi-1.scm')
-rw-r--r--module/srfi/srfi-1.scm46
1 files changed, 46 insertions, 0 deletions
diff --git a/module/srfi/srfi-1.scm b/module/srfi/srfi-1.scm
index 146912e29..2e083c8aa 100644
--- a/module/srfi/srfi-1.scm
+++ b/module/srfi/srfi-1.scm
@@ -1170,6 +1170,52 @@ be deleted with @code{(delete 5 lst <)}.
@var{lst} may be modified to construct the returned list."
(remove! (lambda (elem) (pred x elem)) lst))
+(define* (delete-duplicates lst #:optional (= equal?))
+ "Return a list containing the elements of @var{lst} but without
+duplicates.
+
+When elements are equal, only the first in @var{lst} is retained. Equal
+elements can be anywhere in @var{lst}, they don't have to be adjacent.
+The returned list will have the retained elements in the same order as
+they were in @var{lst}.
+
+Equality is determined by @var{pred}, or @code{equal?} if not given.
+Calls @code{(pred x y)} are made with element @var{x} being before
+@var{y} in @var{lst}. A call is made at most once for each combination,
+but the sequence of the calls across the elements is unspecified.
+
+@var{lst} is not modified, but the return might share a common tail with
+@var{lst}.
+
+In the worst case, this is an @math{O(N^2)} algorithm because it must
+check each element against all those preceding it. For long lists it is
+more efficient to sort and then compare only adjacent elements."
+ ;; Same implementation as remove (see comments there), except that the
+ ;; predicate checks for duplicates in both last-seen and the pending
+ ;; result.
+ (if (null? lst)
+ lst
+ (let ((result (list #f)))
+ (let lp ((lst lst)
+ (last-kept lst)
+ (tail result))
+ (if (null? lst)
+ (begin
+ (set-cdr! tail last-kept)
+ (cdr result))
+ (let ((item (car lst)))
+ (if (or (member item (cdr result) (lambda (x y) (= y x)))
+ (member-before item last-kept lst =))
+ (if (eq? last-kept lst)
+ (lp (cdr lst) (cdr lst) tail)
+ (call-with-values
+ (lambda () (list-prefix-and-tail last-kept lst))
+ (lambda (prefix new-tail)
+ (set-cdr! tail prefix)
+ (lp (cdr lst) (cdr lst) new-tail))))
+ ;; unique, keep
+ (lp (cdr lst) last-kept tail))))))))
+
(define* (delete-duplicates! lst #:optional (= equal?))
"Return a list containing the elements of @var{lst} but without
duplicates.