Clojure中的習慣表達簡化

Question

受this啓發優秀的文章我想在Clojure中使用文章中使用的算法實現一個簡單的表達式簡化器。這篇文章給出了F＃，Scala，Haskell，C++和Julia中的示例實現，它們都顯得相當優雅。

我已經想出了兩個不同的實現（見下文），但我有一個嘮叨的感覺，他們都比慣用。

我的問題是：一個慣用的Clojure實現是什麼樣的？

先執行，主要依據協議：

(defprotocol Expr 
    (simplify1 [e]) 
    (simplify [e])) 

(defrecord Const [n] 
    Expr 
    (simplify1 [this] this) 
    (simplify [this] this)) 

(defrecord Variable [name] 
    Expr 
    (simplify1 [this] this) 
    (simplify [this] this)) 

(defrecord Add [l r] 
    Expr 
    (simplify1 [{:keys [l r] :as expr}] 
    (let [lclass (class l) 
      rclass (class r)] 
     (cond 
     (= lclass rclass Const) 
     (Const. (+ (:n l) (:n r))) 
     (and (= lclass Const) (= (:n l) 0)) 
     r 
     (and (= rclass Const) (= (:n r) 0)) 
     l 
     :else expr))) 
    (simplify [{:keys [l r]}] 
    (simplify1 (Add. (simplify l) (simplify r))))) 

(defrecord Mult [l r] 
    Expr 
    (simplify1 [{:keys [l r] :as expr}] 
    (let [lclass (class l) 
      rclass (class r)] 
     (cond 
     (= lclass rclass Const) 
     (Const. (* (:n l) (:n r))) 
     (and (= lclass Const) (= (:n l) 0)) 
     (Const. 0) 
     (and (= rclass Const) (= (:n r) 0)) 
     (Const. 0) 
     (and (= lclass Const) (= (:n l) 1)) 
     r 
     (and (= rclass Const) (= (:n r) 1)) 
     l 
     :else expr))) 
    (simplify [{:keys [l r]}] 
    (simplify1 (Mult. (simplify l) (simplify r))))) 

(defmulti print-expr class) 

(defmethod print-expr Const [e] 
    (print-str (.value e))) 

(defmethod print-expr ::expr [e] 
    (print-str "The expression cannot be simplified to a constant")) 

(let [e (Add. (Mult. (Add. (Const. 1) (Mult. (Const. 0) (Variable. "X"))) (Const. 3)) (Const. 12))] 
    (-> e 
     simplify 
     print-expr)) 

二實施，主要是基於多方法比第一個更詳細：

(defrecord Const [value]) 
(defrecord Variable [name]) 
(defrecord Add [l r]) 
(defrecord Mult [l r]) 

(derive Const ::expr) 
(derive Variable ::expr) 
(derive Add ::expr) 
(derive Mult ::expr) 

(defn sim-1-disp [{:keys [l r] :as e}] 
    (if (some #{(class e)} [Add Mult]) 
     [(class e) (class l) (class r)] 
     (class e))) 

(defmulti simplify class) 
(defmulti simplify1 sim-1-disp) 
(defmulti print-expr class) 

(defmethod simplify Add [{:keys [l r]}] 
    (simplify1 (Add. (simplify l) (simplify r)))) 

(defmethod simplify Mult [{:keys [l r]}] 
    (simplify1 (Mult. (simplify l) (simplify r)))) 

(defmethod simplify ::expr [e] 
    e) 

(defmethod simplify1 [Add Const Const] [{:keys [l r]}] 
    (Const. (+ (:value l) (:value r)))) 

(defmethod simplify1 [Add Const ::expr] [{:keys [l r] :as e}] 
    (if (= (:value l) 0) 
    r 
    e)) 

(defmethod simplify1 [Add ::expr Const] [{:keys [l r] :as e}] 
    (if (= (:value r) 0) 
    l 
    e)) 

(defmethod simplify1 [Mult Const Const] [{:keys [l r]}] 
    (Const. (* (.value l) (.value r)))) 

(defmethod simplify1 [Mult Const ::expr] [{:keys [l r] :as e}] 
    (cond (= (:value l) 0) 
     (Const. 0) 
     (= (:value l) 1) 
     r 
     :else e)) 

(defmethod simplify1 [Mult ::expr Const] [{:keys [l r] :as e}] 
    (cond (= (:value r) 0) 
     (Const. 0) 
     (= (:value r) 1) 
     l 
     :else e)) 

(defmethod simplify1 ::expr [e] 
    e) 

(defmethod print-expr Const [e] 
    (print-str (.value e))) 

(defmethod print-expr ::expr [e] 
    (print-str "The expression cannot be simplified to a constant")) 

(let [e (Add. (Mult. (Add. (Const. 1) (Mult. (Const. 0) (Variable. "X"))) (Const. 3)) (Const. 12))] 
    (-> e 
     simplify 
     print-expr)) 

Answer 1

不知道關於是的慣用的實施，但我認爲吉列爾莫·溫克勒提到core.match是一種非常自然的替代方法，尤其是with variants。正如你的鏈接文章所說，總和類型非常整齊。

(ns simplify 
    (:require [clojure.core.match :refer [match]])) 

(defn- simplify-1 [expr] 
    (match expr 
     [::add [::const 0] a]   a 
     [::add a [::const 0]]   a 
     [::add [::const a] [::const b]] [::const (+ a b)] 
     [::mult [::const 0] _]   [::const 0] 
     [::mult _ [::const 0]]   [::const 0] 
     [::mult a [::const 1]]   a 
     [::mult [::const 1] a]   a 
     [::mult [::const a] [::const b]] [::const (* a b)] 
     _        expr)) 

(defn simplify [expr] 
    (match expr 
     [::add a b ] (simplify-1 [::add (simplify a) (simplify b)]) 
     [::mult a b ] (simplify-1 [::mult (simplify a) (simplify b)]) 
     _       (simplify-1 expr))) 

例子：

(simplify [::add 
      [::mult 
      [::add [::const 1] [::mult [::const 0] [::var 'x]]] 
      [::const 3]] 
      [::const 12]]) 
;=> [:simplify/const 15] 

這可讓您充分利用模式的簡潔匹配和具有相似的優雅爲您的一些鏈接的例子。儘管如此，與您的協議/多方法方法相比，這是一項成本 - 這些是可擴展的總和類型，包括其他人的代碼，而不涉及您的源代碼。這是多麼有用取決於您的應用程序。

一些旁白：

• 您也可以與simplify-1作爲函數參數的clojure.walk/postwalk來定義simplify。由於simplify不再需要知道哪些expr變體是操作，並且可以簡化爲超出對其調用simplify-1，所以這可能更容易延長。
• 我試圖爲此定義一個core.typed類型，但是我的環境似乎今天加載了一些問題，所以我無法檢查它。

認爲這應該或多或少契合：

(defalias Expr 
    "A variant type for algebraic expressions." 
    (Rec [e] 
     (U [(Value ::const) Number] 
      [(Value ::add) e e] 
      [(Value ::mult) e e] 
      [(Value ::var) Symbol])))