Proposal #9: Fast testing in PROGV

[Guy Steele <gls@Think.COM>]

    Date: Fri, 1 Aug 86 08:36 EDT
    From: David C. Plummer <DCP@QUABBIN.SCRC.Symbolics.COM>
			Putting a mark on a property list takes linear time
    (length of the property list to see if it is already there), and you
    have to do this for N variables.  So you are back to N^2 again, and you
    are likely consing, and misusing property lists, and...

Barf!  Who says you have to search the entire property list?  One of the
reasons we are having such an explosion of mail is that many people are
failing to think for more than three seconds before shooting from the hip.

(defun does-a-list-of-symbols-contain-duplicates-p (symbols)
  (let ((unique (list 'foo)))
    (unwind-protect
	(dolist (s symbols)
	  (when (eq (car (symbol-plist s)) unique)
	    (return-from does-a-list-of-symbols-contain-duplicates-p t))
	  (setf (symbol-plist s) (list* unique t (symbol-plist s))))
      (dolist (s symbols)
	(if (eq (car (symbol-plist s)) unique)
	    (setf (symbol-plist s) (cddr (symbol-plist s)))
	    (return))))
    nil))

Looks like linear time to me.  (Historical note: the implementation of
SUBLIS in MacLisp used to pull a similar trick.)

--Guy