How to compare two lists in Lisp

Question

I am still extremely raw in lisp and looking for a lisp way to solve a particular problem.

I have two lists :

Setq list-a '(2,3))
Setq list-b '(1,2,3))

I need to find out if elements of list a appear in list b i.e. 2 and 3 should appear in list b consecutively.

If I was to solve this problem in JS I will find the index of first element of a in b (i.e. index of 2 in list b) and then check consecutive locations.

Since my knowledge of lisp is very limited I was wondering if there are any inbuilt functions to use.

PS. All the elements of both the list are unique.

Answer 1

Here is an answer which does not depend on using CL's functions which do this for you. In real life this would be a silly thing to do: the language has functions which answer this for you just to avoid endless wheel-reinvention like this. However for educational purposes it is interesting to write functions like this to see how to convert algorithms into code.

The algorithm.

• To find out if A is a sublist of B:

  • if A is the empty list then it is;
  • if A is not empty and B is empty it is not;
  • if A is a leading sublist of B it is a sublist;
  • if A is a sublist of the tail of B it is a sublist of B.

• To find out if A is a leading sublist of B:

  • if A is the empty list, then it is;
  • if A is not empty and B is then it is not;
  • if the first element of A is equal to the first element of B, and the rest of A is a leading sublist of the rest of B then it is.

In fact we could simplify this slightly: we don't need to do all the checks for empty lists in both places. But I have not done this below as it's fairly easy to get wrong (a previous version of this answer did get it wrong!).

So, what we have to do is convert that description into Lisp.

Notes.

• This relies on a local auxiliary function, leading-sublist-p, to tell you if it's a leading sublist as above.
• This is not completely reliable CL because it assumes tail calls will be optimised: if they are not it will run out of stack for long lists. However it is prettier than the equivalent explicitly-iterative version I think.
• This makes no attempts at all to deal with possible circularity and thus will have termination problems in the presence of circular lists (if either list is circular it will not terminate).
• You can specify the element-comparison function with a test keyword argument in the usual CL way, with the default being eql.
• In fact the main loop is a local function as well, any-sublist-p, which exists solely to avoid having to pass the keyword argument through the iteration (I originally failed to pass it down at all, then decided, nerdily, that I didn't want to have to think about any possible overhead of keyword-argument parsing in the loop).

Here it is:

(defun sublistp (a b &key (test #'eql))
  ;; is A a sublist of B, comparing elements with TEST.
  ;;
  ;; Return two values: either NIL and NIL if it is not a leading
  ;; sublist or T and the tail of B at which it matched.
  ;;
  ;; This works by asking whether A is a leading sublist of successive
  ;; tails of B
  ;;
  (labels ((leading-sublist-p (x y)
             ;; is X a leading sublist of Y?
             (cond ((null x)
                    ;; the empty list is a leading sublist of any list
                    t)
                   ((null y)
                    ;; a non-empty list is not the leading sublist of
                    ;; the empty list
                    nil)
                   ((funcall test (first x) (first y))
                    ;; otherwise X is a leading sublist of Y if the
                    ;; first two elements compare the same and the
                    ;; tail of X is a leading sublist of the tail of Y
                    (leading-sublist-p (rest x) (rest y)))))
           (any-sublist-p (x y)
             ;; this does the work: it's here merely to avoid having
             ;; to pass the TEST argument down in the recursion.
             (cond ((null x)
                    ;; the empty list is a sublist of any list
                    (values t y))
                   ((null y)
                    ;; a non-empty list is not a sublist of an empty
                    ;; list
                    (values nil nil))
                   ((leading-sublist-p x y)
                    ;; if X is a leading sublist of Y it's a sublist
                    (values t y))
                   (t
                    ;; otherwise X is a sublist of Y if it is a
                    ;; sublist of the tail of Y
                    (any-sublist-p x (rest y))))))
    (any-sublist-p a b)))

---

For added value, here is a version which detects some, but not all, circularities, by comparing successive tails with the original arguments. This is cheap (two extra eq tests per loop), but does not find all circularities: to do that you need a fully-fledged occurs check which is expensive.

(defun sublistp (a b &key (test #'eql))
  ;; is A a sublist of B, comparing elements with TEST.
  ;;
  ;; Return two values: either NIL and NIL if it is not a leading
  ;; sublist or T and the tail of B at which it matched.
  ;;
  ;; This works by asking whether A is a leading sublist of successive
  ;; tails of B
  ;;
  (labels ((leading-sublist-p (x y)
             ;; is X a leading sublist of Y?
             (cond ((null x)
                    ;; the empty list is a leading sublist of any list
                    t)
                   ((null y)
                    ;; a non-empty list is not the leading sublist of
                    ;; the empty list
                    nil)
                   ((funcall test (first x) (first y))
                    ;; otherwise X is a leading sublist of Y if the
                    ;; first two elements compare the same and the
                    ;; tail of X is a leading sublist of the tail of Y.
                    (let ((rx (rest x))
                          (ry (rest y)))
                      ;; If the tail of X is A then A is circular at
                      ;; this point and we should give up & similarly
                      ;; for Y.  Note this does not find all
                      ;; circularities, but finding some is perhaps
                      ;; better than not finding any.
                      (when (eq rx a)
                        (error "A is trivially circular"))
                      (when (eq ry b)
                        (error "B is trivially circular"))
                      (leading-sublist-p rx ry)))))
           (any-sublist-p (x y)
             ;; this does the work: it's here merely to avoid having
             ;; to pass the TEST argument down in the recursion.
             (cond ((null x)
                    ;; the empty list is a sublist of any list
                    (values t y))
                   ((null y)
                    ;; a non-empty list is not a sublist of an empty
                    ;; list
                    (values nil nil))
                   ((leading-sublist-p x y)
                    ;; if X is a leading sublist of Y it's a sublist
                    (values t y))
                   (t
                    ;; otherwise X is a sublist of Y if it is a
                    ;; sublist of the tail of Y
                    (any-sublist-p x (rest y))))))
    (any-sublist-p a b)))

Here is this version detecting a trivially-circular argument:

> (sublistp (let ((a (list 1)))
                          (setf (cdr a) a)
                          a)
                       '(1 2 3 4))

Error: A is trivially circular
  1 (abort) Return to top loop level 0.

---

For hack value, here is an explicitly iterative version: I find this harder to understand.

(defun sublistp (a b &key (test #'eql))
  ;; is A a sublist of B, comparing elements with TEST.
  ;;
  ;; Return two values: either NIL and NIL if it is not a leading
  ;; sublist or T and the tail of B at which it matched.
  ;;
  ;; This works by asking whether A is a leading sublist of successive
  ;; tails of B
  ;;
  (flet ((leading-sublist-p (x y)
           ;; is X a leading sublist of Y?
           (loop for first-cycle = t then nil
                 for xt = x then (rest xt)
                 for yt = y then (rest yt)
                 unless first-cycle     ;circularity only after 1st cycle
                 do (cond
                     ;; If the tail of X is A then A is circular at
                     ;; this point and we should give up & similarly
                     ;; for Y.  Note this does not find all
                     ;; circularities, but finding some is perhaps
                     ;; better than not finding any.
                     ((eq xt a)
                      (error "A is trivially circular"))
                     ((eq yt b)
                      (error "B is trivially circular")))
                 do (cond
                     ((null xt)
                      ;; the empty list is a leading sublist of any
                      ;; list
                      (return-from leading-sublist-p t))
                     ((null yt)
                      ;; a non-empty list is not the leading
                      ;; sublist of the empty list
                      (return-from leading-sublist-p nil))
                     ((not (funcall test (first xt) (first yt)))
                      ;; leading elements differ: fail
                      (return-from leading-sublist-p nil))))))
    (cond ((null a)
           ;; the empty list is the sublist of any list
           (values t b))
          ((null b)
           ;; no non-empty list is the sublist of any list
           (values nil nil))
          (t
           (loop for bt = b then (rest b)
                 do (cond 
                     ((null bt)
                      (return-from sublistp (values nil nil)))
                     ((leading-sublist-p a bt)
                      (return-from sublistp (values t bt)))))))))

Answer 2

In ANSI Common Lisp, the search function will determine whether a subsequence of a longer sequence is equivalent to a shorter sequence:

[1]> (search '(2 3) '(1 2 3))
1

For instance, here, search has found (2 3) at position 1 of (1 2 3).

search works with other kinds of sequences like vectors and strings:

[2]> (search "ef" "abcdef")
4

If the search fails, search returns nil.