Clojureの

Question

スキームにおけるパターンマッチングのためのドット付き対アナログ（及びCL）はconsた細胞の両方の要素が明示的に指定されて点在対（例えば(1 . 2)）はなく、暗黙的により（例えば(1 2)(1 . (2 . nil))として読み出されます）。

私は例えば、点線のペアが一致しているオブジェクトにリストの最後尾をキャプチャするためにパターンマッチングに使用されている。このpuzzle出くわし：

(pmatch '(foo . (? pvar)) '(foo bar baz)) 
;;  => ((pvar bar baz)) 

ここ'(foo . (? pvar))がパターンであると'(foo bar baz)がオブジェクトでありますパターンと一致する。パターン内のfooはリテラルですが、(? pvar)は(bar baz)に一致するパターン変数であり、その一致にシンボルpvarをバインドします。 pmatch関数は、パターン変数とバインドされた一致の関連リストを返します。

パターンが'(foo (? pvar))の場合、bazはパターン内の何も一致しないため、一致は失敗します。

私はClojureでパズルを実装しました。JRMのテストケースのすべてをドットペアのものから分離しています。私はおそらくドットペアパターンもサポートする方法を理解しようとしています。

は、ここに私の現在のソリューションです：

(defn pattern-variable? [pv] 
    (when (seq? pv) 
    (let [[qmark var] pv] 
    (and (= (count pv) 2) 
      (= qmark '?) 
      (or (symbol? var) 
       (keyword? var))))) 

(defn pattern-variable [pv] 
    (second pv)) 

(defn pmatch 
    ([pat obj] (pmatch pat obj {})) 
    ([pat obj binds] 
    (cond (not (coll? pat)) 
      (when (= pat obj) binds) 
      (pattern-variable? pat) 
      (assoc binds (pattern-variable pat) obj) 
      (seq? pat) (let [[pat-f & pat-r] pat] 
         (when (seq? obj) 
         (when-let [binds (pmatch pat-f (first obj) binds)] 
          (pmatch pat-r (next obj) binds)))) 
      :else nil))) 

それでは、どのように私は、ドット付きペアなしのClojureでのオブジェクトの残りの部分に一致するパターンをサポートすることができますか？

Answer 1

（編集：若干長く追加されたが、有意に明確マッチャーIMPL +デモ水平ルール以下元のままである）

一つの解決策は、変数を示すために、異なる表記を導入することであろうseqの末尾、または「ドットの後の変数」と照合してください。もう1つは、特別なシンボルとして&を予約することです。これは、seqでなければならない式/オブジェクトの残りと照合される単一のパターン変数の後に続くことができるという要件があります。私は以下の最初のアプローチを探求します。

ここでは、が変数fooの通常の出現であり、~@fooがテールの出現であるように、表記法を変更する自由を取った。 （可能であれば残りのパターンとパターンマッチすることができるように、シーケンスの最小の初期フラグメントと一致する可能性があるサブシーケンスに対して~@マッチングを行うことができます;これはこの答えの範囲外ですしかし、

~ - 出現およびバインディングから生じるバインディングの区別がないため、これらは実際には同じ変数の異なる出現であることに注意してください~@から発生します。

リンクされた投稿の例では、以前にバインドされた変数を再バインドしようとしていません（元の構文で(pmatch '(~x ~x) '(foo bar))、(pmatch '((? x) (? x)) '(foo bar))など）。このような場合は、他の理由で一致が失敗した場合と同様に、以下のコードはnilを返します。

まず、デモ：

user> (pmatch '(foo ~pvar1 ~pvar2 bar) '(foo 33 (xyzzy false) bar)) 
{pvar2 (xyzzy false), pvar1 33} 
user> (pmatch '(~av ~@sv) '(foo bar baz)) 
{sv (bar baz), av foo} 
user> (pmatch '(foo ~pvar1 ~pvar2 bar) '(foo 33 false bar)) 
{pvar2 false, pvar1 33} 
user> (pmatch '(foo ~pvar bar) '(quux 33 bar)) 
nil 
user> (pmatch '(a ~var1 (nested (c ~var2))) '(a b (nested (c d)))) 
{var2 d, var1 b} 
user> (pmatch '(a b c) '(a b c)) 
{} 
user> (pmatch '(foo ~pvar1 ~pvar2 bar) '(foo 33 (xyzzy false) bar)) 
{pvar2 (xyzzy false), pvar1 33} 
user> (pmatch '(foo ~@pvar) '(foo bar baz)) 
{pvar (bar baz)} 
user> (pmatch '(~? quux) '(foo quux)) 
{? foo} 
user> (pmatch '~? '(foo quux)) 
{? (foo quux)} 
user> (pmatch '(? ? ?) '(foo quux)) 
nil 

はここに正規表現エンジンの：

(defn var-type [pat] 
    (when (seq? pat) 
    (condp = (first pat) 
     'clojure.core/unquote :atomic 
     'clojure.core/unquote-splicing :sequential 
     nil))) 

(defn var-name [v] 
    (when (var-type v) 
    (second v))) 

(defmulti pmatch* 
    (fn [pat expr bs] 
    (cond 
     (= :atomic (var-type pat))  :atom 
     (= :sequential (var-type pat)) nil 
     (and (seq? pat) (seq? expr))  :walk 
     (not (or (seq? pat) (seq? expr))) :exact 
     :else        nil))) 

(defmethod pmatch* :exact [pat expr bs] 
    (when (= pat expr) bs)) 

(defmethod pmatch* :atom [v expr bs] 
    (if-let [[_ x] (find bs (var-name v))] 
    (when (= x expr) bs) 
    (assoc bs (var-name v) expr))) 

(defmethod pmatch* :walk [pat expr bs] 
    (if-let [[p] pat] 
    (if (= :sequential (var-type p)) 
     (when (and (seq? expr) (not (next pat))) 
     (if-let [[_ xs] (find bs (var-name p))] 
      (when (= xs expr) bs) 
      (assoc bs (var-name p) expr))) 
     (when-let [[x] expr] 
     (when-let [m (pmatch* p x bs)] 
      (pmatch* (next pat) (next expr) m)))))) 

(defmethod pmatch* nil [& _] nil) 

(defn pmatch 
    ([pat expr] (pmatch pat expr {})) 
    ([pat expr bs] (pmatch* pat expr bs))) 

---

そしてここで、元のモノリシック・バージョンです：

(defn pmatch 
    ([pat expr] (pmatch pat expr {})) 
    ([pat expr bs] 
    (letfn [(atom-var? [pat] 
       (and (seq? pat) (= 'clojure.core/unquote (first pat)))) 
      (seq-var? [pat] 
       (and (seq? pat) (= 'clojure.core/unquote-splicing 
            (first pat)))) 
      (v [var] (second var)) 
      (matcha [a e bs] 
       (if-let [[_ x] (find bs (v a))] 
       (and (or (= x e) nil) bs) 
       (assoc bs (v a) e))) 
      (matchs [s e bs] 
       (when (seq? e) 
       (if-let [[_ xs] (find bs (v s))] 
        (or (= xs e) nil) 
        (assoc bs (v s) e))))] 
     (when bs 
     (cond 
      (atom-var? pat) 
      (matcha pat expr bs) 

      (seq-var? pat) 
      (matchs pat expr bs) 

      (and (seq? pat) (seq? expr)) 
      (if-let [[p] pat] 
      (if (seq-var? p) 
       (matchs p expr bs) 
       (when-let [[x] expr] 
       (when-let [m (pmatch p x bs)] 
        (recur (next pat) (next expr) m)))) 
      (when-not (first expr) 
       bs)) 

      (not (or (seq? pat) (seq? expr))) 
      (when (= pat expr) 
      bs) 

      :else nil)))))