2

我在 LISP 和列表处理方面没有经验，但我有一组 C++ STL 向量（或字符串），我需要在这些向量上执行以下操作：

IdenticalHead (v1, v2)：返回 v1 和 v2 都以它开头的最大序列。

IdenticalTail (v1, v2)：返回 v1 和 v2 都以它结尾的最大序列。

IdenticalTailHead(v1, v2)：返回v1以它结尾和v2以它开头的最大序列。

例如：

如果 v1 = (a,b,c,e,f)，v2 = (a,b,d,e,f)，则：

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

如果 v1 = (a,b,c), v2 = (b,c,g)，则：

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

我的问题是这些标准操作是 LISP 还是任何其他语言？他们有像 CDR 和 CAR 这样的标准名称吗？

4

3 回答 3

3

IdenticalHead 和 IdenticalTail 基本上由 Common Lisp 函数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)

第三个功能更复杂：

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)
于 2012-07-13T18:44:41.293 回答
1

不，这些没有标准运算符。但是identical-head不难写：

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

identical-tail除了反转输入列表，调用identical-head，然后反转结果之外，我不知道更简单的编写方法，因为列表只允许向前遍历，而不是向后遍历。

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

这是我的写作方式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)))))

这不是一种非常有效的方法，因为它是 O(n²)，但是（再次）考虑到列表是仅向前遍历的，我还没有想出更好的方法。

于 2012-07-13T18:32:57.827 回答
1

既然你提到“其他语言”，Haskell 是一种 Lispy 语言，它确实有你所问的惯用方法。

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

zip将其两个参数列表的元素配对，并且takeWhile是自描述的。

对于第二个变体，您只需reverse在参数和结果上使用。第三个涉及更多：

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相当于iterate tail xs即列表[xs, tail xs, tail (tail xs), ...]；tail是 的同义词cdr和head- 的同义词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"
""
于 2012-07-28T08:12:24.810 回答