CODEWITHSUNDEEP
stringvectorlispcommon-lisp
Ari
Ari

Reputation: 7556

identical head and tail operations on lists or vectors

I am not experienced in LISP and list processing, but I have a set of C++ STL vectors (or strings) on which I need to perform the following operations:

IdenticalHead (v1, v2): Return the biggest sequence that both v1 and v2 start with it.

IdenticalTail (v1, v2): Return the biggest sequence that both v1 and v2 end with it.

IdenticalTailHead (v1, v2): Return the biggest sequence that v1 ends with it and v2 starts with it.

For example:

if v1 = (a,b,c,e,f), v2 = (a,b,d,e,f), then:

IdenticalHead (v1, v2) = (a,b)
IdenticalTail (v1, v2) = (e,f)

if v1 = (a,b,c), v2 = (b,c,g), then:

IdenticalTailHead (v1, v2) = (b,c)

My question is that are these standard operations in LISP or any other language? Do they have standard names like CDR and CAR?

Upvotes: 2

Views: 232

Answers (3)

Will Ness
Will Ness

Reputation: 71065

Since you mention "other language", Haskell is a kind-of Lispy language, and it does have idiomatic approach to what you're asking about.

longestPrefix xs ys = map fst (takeWhile (\(x,y) -> x == y) (zip xs ys))

zip pairs up the elements of its two argument lists, and takeWhile is self-descriptive.

For the second variant you'd just use reverse on arguments and on the result. The third is a bit more involved:

longestPrefixEnding xs ys =   -- '(a e d b c d) '(b c d a f)
  head [t  |  t <- tails xs, let p=longestPrefix t ys, p==t]

tails xs is equivalent to iterate tail xs i.e. the list [xs, tail xs, tail (tail xs), ...] ; tail is a synonym of cdr, and head - synonym of car:

Prelude Data.List> longestPrefix "abcef" "abdef"
"ab"
Prelude Data.List> longestPrefixEnding "aedbc" "bcdaf"
"bc"
Prelude Data.List> longestPrefixEnding "aebcabcd" "bcdaf"
"bcd"
Prelude Data.List> longestPrefixEnding "aebcabcdx" "bcdaf"
""

Upvotes: 1

Rainer Joswig
Rainer Joswig

Reputation: 139261

IdenticalHead and IdenticalTail are basically provided by the Common Lisp function MISMATCH.

CL-USER 81 > (mismatch '(a b c e f) '(a b d e f))
2

CL-USER 82 > (mismatch '(a b c e f) '(a b d e f) :from-end t)
3

CL-USER 83 > (defun identical-head (s1 s2)
               (let ((m (mismatch s1 s2)))
                 (if (numberp m)
                     (subseq s1 0 m)
                   s1)))
IDENTICAL-HEAD

CL-USER 84 > (identical-head '(a b c e f) '(a b d e f))
(A B)

CL-USER 85 > (defun identical-tail (s1 s2)
               (let ((m (mismatch s1 s2)))
                 (if (numberp m)
                   (subseq s1 (1+ m))
                   s1)))
IDENTICAL-TAIL

CL-USER 86 > (identical-tail '(a b c e f) '(a b d e f))
(E F)

The third function is more complicated:

CL-USER 87 > (defun identical-tail-head (s1 s2 &aux (l1 (length s1)))
               (loop for i from 0 below l1
                     for m = (mismatch s2 s1 :start2 i)
                     when (and m (= (+ i m) l1))
                     do (return (subseq s1 i))))

CL-USER 88 > (identical-tail-head '(a e d b c d) '(b c d a f))
(B C D)

Upvotes: 3

C. K. Young
C. K. Young

Reputation: 223023

No, there are no standard operators for these. But identical-head is not hard to write:

(defun identical-head (l1 l2)
  (and l1 l2 (equal (car l1) (car l2))
       (cons (car l1) (identical-head (cdr l1) (cdr l2)))))

I don't know of an easier way to write identical-tail except reversing the input lists, calling identical-head, and then reversing the result, since lists only allow forward traversal, not backward.

(defun identical-tail (l1 l2)
  (reverse (identical-head (reverse l1) (reverse l2))))

Here's how I'd write identical-tail-head:

(defun identical-tail-head (l1 l2)
  (labels ((starts-with-p (list prefix)
             (cond ((null prefix) t)
                   ((null list) nil)
                   ((equal (car list) (car prefix))
                    (starts-with-p (cdr list) (cdr prefix))))))
    (cond ((null l1) nil)
          ((starts-with-p l2 l1) l1)
          (t (identical-tail-head (cdr l1) l2)))))

It's not a very efficient way to do it, since it's O(n²), but (again) given that lists are forward-traversal-only, I haven't come up with a better way.

Upvotes: 1

Related Questions