4
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks, I like your (list 'uniq1) (or (box 'uniq1) in Racket) comment, which is useful for debugging. As regards your version, SRFI 1 has append-reverse (though if you didn't write your version to use SRFI 1, then implementing your own is understandable). Also, a fundamental difference between your version and mine is that mine uses a base list whose elements are being reused, and yours creates brand new lists for both xs and ys. Both are valid solutions; they solve different problems. :-) (And yeah, no reverse-based solutions work for cyclic lists.) \$\endgroup\$ – Chris Jester-Young Oct 25 '15 at 18:54
  • \$\begingroup\$ I had forgotten append-reverse was in srfi 1. \$\endgroup\$ – soegaard Oct 25 '15 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.