1. 什么是Pattern Matching
2. core.match
3. lambda 解释器
4. 参考

什么是Pattern Matching

Pattern Matching（模式匹配），在FP语言中均有支持, 基本上会被当成FP语言的一个特性. 匹配的对象可以是序列，树，或者是map结构。 可以类比的是字符串的正则表达式. 也可以认为是Destruction的一个升级.

最初接触是Erlang和Haskell, 后来主流语言C#, Swift，Rust都有很好的支持. Clojure作为一门lisp语言，一向是通过库来扩展语言，这次的库是core.match。 主要解决的问题：

1. 复杂的条件分支判断
2. 复合数据结构的解析

模式匹配会返回第一条匹配的值.

core.match

 (require '[cljs.core.match :refer-macros [match]])

字面匹配

(let [x true
      y true
      z true]
  (match [x y z]
         [_ false true] 1
         [false true _ ] 2
         [_ _ false] 3
         [_ _ true] 4
         :else 5))

和函数参数中的占位符_ 一样，表示你不关心的部分。

(let [x true]
  (match x
         true 1
         false 2
         :else 5))

动态结构

这个是core.match官方的一个例子

(doseq [n (range 1 11)]
    (println
    (match [(mod n 3) (mod n 5)]
    [0 0] "FizzBuzz"
    [0 _] "Fizz"
    [_ 0] "Buzz"
    :else n)))

sequential匹配

处理list, 列表方式，从头开始遍历，需要指明使用:seq

(let [x [1 2 nil nil nil]]
  (match [x]
         [([1] :seq)] :a0
         [([1 2] :seq)] :a1
         [([1 2 nil nil nil] :seq)] :a2
         :else nil))

vector 对于vector，可以做random access, core.match会做一些加速. 比如下面的例子，它会从第三列开始进行

(let [x [1 2 3]]
  (match [x]
         [[_ _ 2]] :a0
         [[1 1 3]] :a1
         [[1 2 3]] :a2
         :else :a3))

rest对于sequential和vector

list:

(let [x '(1 2)]
  (match [x]
         [([1] :seq)] :a0
         [([1 & r] :seq)] [:a1 r]
         :else nil))

vector:

(let [x [1 2]]
  (match [x]
         [[1]] :a0
         [[1 & r]] [:a1 r]
         :else nil))

map的匹配

(let [x {:a 1 :b 1}]
  (match [x]
         [{:a _ :b 2}] :a0
         [{:a 1 :b 1}] :a1
         [{:c 3 :d _ :e 4}] :a2
         :else nil))

可以只关注map是否有某个key：

(let [x {:a 1 :b 1}]
  (match [x]
         [{:c _}] :a0
         :else :no-match))

可以只关注部分key

(let [x {:a 1 :b 2}]
  (match [x]
         [({:a _ :b 2} :only [:a :b])] :a0
         [{:a 1 :c _}] :a1
         [{:c 3 :d _ :e 4}] :a2
         :else nil))

(let [x {:a 1 :b 2 :c 3}]
  (match [x]
         [({:a _ :b 2} :only [:a :b])] :a0
         [{:a 1 :c _}] :a1
         [{:c 3 :d _ :e 4}] :a2
         :else nil))

or模式

用于表示或者关系, 避免了写6个分支判断

(let [x 4 y 6 z 9]
  (match [x y z]
         [(:or 1 2 3) _ _] :a0
         [4 (:or 5 6 7) _] :a1
         :else nil))

guard

使用谓词函数判断匹配关系

(match [1 2]
       [(_ :guard odd?)) (_ :guard odd?)] :a1
       [(_ :guard odd?)) _] :a2
       :else :a4)

嵌套结构

(match [{:a {:b :c}}]
       [{:a {:b nested-arg}}] nested-arg)

根据函数的返回值匹配

(let [n 0]
  (match [n]
         [(1 :<< inc)] :one
         [(2 :<< dec)] :two
         :else :no-match))

lambda 解释器

下面这段代码实现了一个图灵完备的解释器

• 高阶函数
• lexical scope
• 闭包实现环境变量查找
• 用一个阶乘进行了验证

读懂了这段代码，就洞悉了Lisp的一切奥秘.

用core.match完全是因为能够更简洁的表达, 用if/case实现也是一样的。

(defn interpereter [expr env]
  (if (list? expr)
    (let [[p1 p2 p3 p4] expr]
      (match [p1 p2 p3 p4]

             ['if pred true-branch false-branch ]
             (if (interpereter pred env)
               (interpereter true-branch env)
               (interpereter false-branch env))

             ['* arg1 arg2 nil]
             (* (interpereter arg1 env) (interpereter arg2 env))

             ['dec arg nil nil]
             (dec (interpereter arg env) )

             ['zero? param nil nil]
             (zero? (interpereter param env))

             [func params nil nil]
             ((interpereter func env) (interpereter params env))

             ['fn [x] body nil]
             (fn [arg]
               (interpereter body (fn [y]
                                    (if (= x y)
                                      arg
                                      (env y)))))

             :else (assert false (str "未能捕获list:" expr))))
    (match [expr]
           [(n :guard symbol?)] (env n)
           [(n :guard number?)] n
           :else (assert false (str "未能捕获元素:" expr)))))

(interpereter '(((fn [!]
                (fn [n]
                  ((! !) n)))
              (fn [!]
                (fn [n]
                  (if (zero? n)
                    1
                    (* n ((! !) (dec n)))))))
             5)
           (fn [e] (assert false (str "no such element.." e) )))

参考

1. core.match参照本论文的实现
2. core.match 的github地址