Diff in elisp
A simple & lispy Myers difference algorithm

Doing some org-mode interface hacking recently, I needed to know what changes happend between two versions of a list. This called for a diff algorithm.

With the help of some websearching I found that I actually wanted to find the longest common subsequence (lcs @ wikipedia) between the two lists. The lcs is what stayed the same between both lists and can be massaged into their diff. I then found the lcs and diff implemented in common lisp and also a rosetta code page. Translating these findings to elisp yields:

(defun greater (a b)
  (if (> (length a) (length b)) a b))

(defun lcs (a b)
  (when (and a b)
    (if (eq (car a) (car b))
        (cons (car a) (lcs (cdr a) (cdr b)))
      (greater (lcs a (cdr b))
               (lcs (cdr a) b)))))

(lcs '(1 2 3)
     '(1 2 3 4))
;; => (1 2 3)

(lcs '(1 2 22 21 3)
     '(2 3 3 3 4 5))
;; => (2 3)

This finds the lcs using recursion (what the wikipedia page calls dynamic programming). To get the diff from this our reference (and wikipedia) recommend walking the lcs and the two lists again to imperatively construct their diff. Since our algorithm already walked all combinations of the two lists, let us construct their diff at the same time. Also throw in memoization with the newish with-memoization macro. This makes for a rather huge runtime difference of around four magnitudes.

(let ((memory (make-hash-table :test 'equal)))
  (defun list-diff (a b)
    "Diff A and B.
Recursivly computes the longest common subsequence and while
doing so assembles the returned diff."
    ;; f:first r:rest
    (with-memoization (gethash (cons a b) memory)
      (cl-labels
          ((choose (a b)
             ;; choose diff with longer lcs
             (let ((la (seq-count #'atom a))
                   (lb (seq-count #'atom b)))
               (if (> la lb) a b)))
           (merge (x)
             ;; merge consecutive add or rem
             (pcase x
               (`((,op ,f) (,op . ,r) . ,d)
                `((,op ,f . ,r) . ,d))
               (d d))))
        (cond
         ((and a b)
          (pcase-let ((`(,af . ,ar) a)
                      (`(,bf . ,br) b))
            (if (eq af bf)
                ;; same
                (cons af (list-diff ar br))
              ;; different
              (merge (choose (cons (list '+ bf) (list-diff a br))
                             (cons (list '- af) (list-diff ar b)))))))
         ;; rest
         (a `((- . ,a)))
         (b `((+ . ,b))))))))

(list-diff '(1 2 3)
           '(1 2 3 4))
;; => (1 2 3 (+ 4))

(list-diff '(1 2 22 21 3)
           '(2 3 3 3 4 5))
;; => ((- 1) 2 (- 22 21) 3 (+ 3 3 4 5))

list-diff assumes lists of atoms which are comparable with equal. But it could be adapted to other types of data as well.

list-diff is a bit more complex than lcs at first glance. But it does more and integrates the previously seperate greater. Let's have a closer look:

with-memoization

uses a hashtable to remember previously computed results

choose

compares two diffs and returns the lcs - the list with more same items

merge

combines consecutive additions or removals

the body

is mostly similar to the previous lcs. It uses pcase-let to get rid of the cars and cdrs. It also has to account for possible rests of both lists that follow their lcs.

So long and merry hacking :)