cross-posted from: https://lemmy.ml/post/4591838

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)

Version 2

(defun seq-intersect-p (first second & sequences)
  "Determine if FIRST, SECOND and any of the sequences in SEQUENCES have
an intersection."
  (if (seq-empty-p sequences)
      (seq-intersection first second)
    (or (seq-intersection first second)
        (apply #'seq-intersect-p
               first
               (seq-first sequences)
               `,@(seq-rest sequences))
        (apply #'seq-intersect-p
               second
               (seq-first sequences)
               `,@(seq-rest sequences))
        (apply #'seq-intersect-p
               (seq-first sequences)
               (seq-elt sequences 2)
               `,@(seq-rest (seq-rest sequences))))))
  • charjeEnglish
    1·
    9 months ago

    This version is definitely a bit harder to follow what is going on.

    • bahmanmOPEnglish
      1·
      9 months ago

      Oh!? And I was under the impression that the code reads more naturally than the initial version 😂

      Let me try putting it in words and see if it makes sense to you:

      Given sequences seq1 and seq2 and sequence of sequences sequences, seq-intersect-p should return non-nil if at least one pair of the input sequences have got an intersection.

      1. If seq1 and seq2 intersect return t
      2. Recursively check if seq1 intersects w/ any element in sequences. If it does, return t. Otherwise we know seq1 is safe to be ignored - no intersection whatsoever.
      3. Recursively check if seq2 intersects w/ any element in sequences. If they don’t, we know seq2 is safe to be ignored too.
      4. Recursively check if any elements of sequences intersect w/ each other.

      There’s no caching or optimisation in this version. So it’s always O(n2).