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は、基本的にCommonLisp関数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)

3番目の関数はもっと複雑です：

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

あなたが「他の言語」について言及しているので、Haskellは一種のLispy言語であり、あなたが求めているものに対して慣用的なアプローチを持っています。

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

zip2つの引数リストの要素を組み合わせて、takeWhile自己記述的です。

2番目のバリアントではreverse、引数と結果に使用します。3番目はもう少し複雑です：

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 xsiterate 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 に答える
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 に答える