Suppose I need to find out if the intersection of an arbitrary number of lists or sequences is empty.

Instead of the obvious O(n2) approach I used a hash table to achieve an O(n) implementation.

Now, loop mini-language aside, is this idiomatic elisp code? Could it be improved w/o adding a lot of complexity?

You can view the same snippet w/ syntax highlighting on pastebin.

(defun seq-intersect-p (seq1 seq2 &rest sequences)
  "Determine if the intersection of SEQ1, SEQ2 and SEQUENCES is non-nil."
  (cl-do* ((sequences `(,seq1 ,seq2 ,@sequences) (cdr sequences))
           (seq (car sequences) (car sequences))
           (elements (make-hash-table :test #'equal))
           (intersect-p nil))
      ((or (seq-empty-p sequences)) intersect-p)
    (cl-do* ((seq seq (cdr seq))
             (element (car seq) (car seq)))
        ((or intersect-p (seq-empty-p seq)) intersect-p)
      (if (ht-get elements element)
          (setf intersect-p t)
        (ht-set elements element t)))))

(defun test-seq-intersect-p ()
  "Test cases."
  (cl-assert (null (seq-intersect-p '()
                                    '())))
  (cl-assert (null (seq-intersect-p '(1)
                                    '())))
  (cl-assert (null (seq-intersect-p '(1 2)
                                    '(3 4)
                                    '(5 6))))
  (cl-assert (seq-intersect-p '(1 2)
                              '(3 4)
                              '(5 6)
                              '(1)))
  t)

(test-seq-intersect-p)
  • bahmanm@lemmy.mlOP
    link
    fedilink
    English
    arrow-up
    2
    ·
    1 year ago

    Feedack from Emacs Matrix room:

    The code will fail if a sequence contains duplicates
    Also, seq-* implies that it is assuming to work on any sequence type, not just lists