How to find the uncommon items in a list (mutually exclusive)

Question

I was tasked with writing a scheme function that can produce a new list containing the elements that only exist in one of two input lists. I managed to create a working solution:

(define remove
  (lambda (l item)
    (filter (lambda (x) (not (equal? x item))) l)))

(define uncommon_list
  (lambda (list1 list2)
    (cond 
      ((null? list2) list1)
      ((null? list1) list2)
      ((memv (car list1) list2)
       (uncommon_list (cdr list1) (remove list2 (car list1))))
      (else 
       (append (list (car list1)) (uncommon_list (cdr list1) list2))))))       

However I feel like i'm over complicating this, and the O complexity isn't great? Any pointers to make this better would be great! Thanks

Answer 1

For best big O, which is O(n), you need to make sets and in Scheme that means hash tables. The solution is to update the hash so that one knows if it was found in the first, the second, or both lists. A list is then made from the element that are not in both:

#!r6rs

(import (rnrs base)
        (srfi :69))

(define (uncommon-elements l1 l2)
  (define hash (make-hash-table eqv?))
  (define (update-elements proc default lst)
    (for-each
     (lambda (e)
       (hash-table-update! hash e proc (lambda () default)))
     lst))

  (update-elements values 1 l1)
  (update-elements (lambda (e) (if (= e 2) 2 3)) 2 l2)
  (hash-table-fold hash
                   (lambda (k v acc)
                     (if (= v 3)
                         acc
                         (cons k acc)))
                   '()))

(uncommon-elements '(1 2 3 4 5) '(3 4 5 6 7 8))
; ==> (1 2 6 7 8)

(uncommon-elements '(1 1 2 2 3 3 4 5) '(3 4 5 6 7 8))
; ==> (1 2 6 7 8)