Clojure 中的惯用表达式简化

Question

受到 this 优秀 post 的启发，我想使用 post 中使用的算法在 Clojure 中实现一个简单的表达式简化器。 post 给出了 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

不确定惯用的实现方式，但我认为正如 Guillermo Winkler 提到的那样 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]

这使您可以利用模式匹配来实现简洁，并具有与您的一些链接示例相似的优雅。与您的 protocol/multimethod 方法相比，这是有代价的——这些是对扩展开放的求和类型，包括在不触及您的源代码的情况下通过其他人的代码。这有多大用处取决于您的应用程序。

一些旁白：

您还可以根据 clojure.walk/postwalk 和 simplify-1 作为函数参数来定义 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])))

Clojure 中的惯用表达式简化

Idiomatic expression simplification in Clojure

polymorphism

protocols

clojure

multimethod