s c h e m a t i c s : c o o k b o o k

This Web

Other Webs

Schematics

RSS

Scheme Links

Extracting Unique Elements from a List

Problem

You want to eliminate duplicate values from a list.

Solution

There are several possible solutions for this problem. Here are some of these:

Using SRFI 1

SRFI 1 includes a procedure delete-duplicates.

Using a hash table

The usual delete-duplicates, such as the one shipped with SRFI 1, are standard recursive procedures, that in the worst case have to go twice over the whole list. It is standard thus to use a hash table to recall the values we have already seen, or the values we have already added to the result, and in one single pass over the list construct the result without duplicates.

This first attempt, has a loop procedure (see ProcedureRecipeRecursive? to learn how to use named let) that traverses the list, adding each unseen element to the hash, and it also adds this new element to the result lists, ans.

(define remove-duplicates
  (lambda (l)
    (let ((h (make-hash-table 'equal)))
      (let loop ((l l) (ans '()))
        (cond ((null? l) ans)
              ((hash-table-get h (car l) (lambda () #f)) 
               (loop (cdr l) ans))
              (else 
               (hash-table-put! h (car l) #t)
               (loop (cdr l) (append ans (list (car l))))))))))

We can do better than that by noticing two things:

• Both libraries: list.ss from Mzlib, and SRFI 1 provide a procedure named filter, similar to map except that it only collects the results that pass a given test.
• When a value is not found in a hash table, a failure thunk is executed, so we can customize this thunk to do what we want, as in:

(require (lib "1.ss" "srfi")) ;; for filter

(define remove-duplicates
  (lambda (l)
    (let ((h (make-hash-table 'equal)))
      (filter (lambda (elem)
                (hash-table-get h
                                elem
                                (lambda () 
                                  (hash-table-put! h elem #f)
                                  #t)))
              l))))

Comments about this recipe

Contributors

-- FranciscoSolsona - 19 May 2004