2

受这篇优秀文章的启发，我想使用文章中使用的算法在 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))
4

1 回答 1

4

不确定是否是惯用的实现，但我认为正如 Guillermo Winkler 提到的那样，core.match这是一种非常自然的替代方法，尤其是对于 variables。正如您链接的文章所说，总和类型非常简洁。

(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]

这使您可以利用模式匹配来实现简洁，并具有与某些链接示例类似的优雅。不过，与您的协议/多方法方法相比，这是有成本的——这些是对扩展开放的总和类型，包括其他人的代码，而无需触及您的源代码。这有多有用取决于您的应用程序。

一些旁白：

  • 您还可以将with定义simplify为函数参数。这可能更容易扩展，因为不再需要知道哪些 expr 变体是操作，并且可以在调用它们之外进行简化。clojure.walk/postwalksimplify-1simplifysimplify-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])))
于 2015-08-09T21:06:39.383 回答