Merging list tails in Scheme In my last post, I wrote a long, non-general tail-merging† facility for insertion sort. I thought I should instead write a general-purpose tail-merging function, that works even when the two lists are of different lengths. So here it is (requires SRFI 1):

;;; Returns a list that has the same content as `lst`, sharing tail with `base`.
;;; Element comparisons use `eqv?`.
(define (merge-tail lst base)
  ;; `uniq1` and `uniq2` are guaranteed not to be `eqv?` to anything else.
  ;; This ensures that `breakpoint` always has a value, without any hacks.
  (define uniq1 (list 'uniq1))
  (define uniq2 (list 'uniq2))
  (define breakpoint (list-index (lambda (x y) (not (eqv? x y)))
                                 (reverse (cons uniq1 base))
                                 (reverse (cons uniq2 lst))))
  (append (drop-right lst breakpoint) (take-right base breakpoint)))


(In Racket, you can replace (list 'uniq1) with (box 'uniq1) (and similarly for uniq2), and (lambda (x y) (not (eqv? x y))) with (negate eqv?).)

Is there a more stylish or performant way to write this code? (Note, I'm trying to not mutate either list. If the lst list is linear-update, then of course you can use append! and drop-right!.)

† The process of merging tails is to ensure that two lists share the longest tail possible. This is especially useful for immutable lists.
A minor detail: In output it can be hard to tell the difference between (cons #f #f) and (cons #f #f) i.e. between uniq1 and uniq2. An alternative is to write (list 'uniq1) in order to get a unique value.

For comparison here is a version of merge-tail written using named let rather than using indices. Here the common tail between xs and ys are found, and two new lists using the shared tail is returned.

(define (reverse-append rxs ys)
  (if (null? rxs)
      ys
      (reverse-append (cdr rxs) (cons (car rxs) ys))))

(define (merge-tail xs ys)
  (let loop ([tail '()]
             [rxs  (reverse xs)]
             [rys  (reverse ys)])
    (cond
      [(eqv? (car rxs) (car rys))
       (loop (cons (car rxs) tail)
             (cdr rxs)
             (cdr rys))]
      [else
       ;; tail is now equal to the common tail of xs and ys
       (values (reverse-append rxs tail)
               (reverse-append rys tail))])))


This solution will fail if xs and ys are cyclic lists with equal elements.
So in the terminology of srfi 1, the solution only works for proper lists.