clojure - Clojure 中的惯用表达简化

Question

灵感来自this优秀的帖子我想使用帖子中使用的算法在 Clojure 中实现一个简单的表达式简化器。这篇文章提供了 F#、Scala、Haskell、C++ 和 Julia 的示例实现，它们都显得相当优雅。

我提出了两种不同的实现(见下文)，但我有一种挥之不去的感觉，它们都不太惯用。

我的问题是:惯用的 Clojure 实现是什么样的？

第一次实现，主要基于协议(protocol):

(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)/多方法方法相比，这是有成本的 - 这些是可扩展的总和类型，包括通过其他人的代码而不触及您的源代码。这有多有用取决于您的应用程序。

一些旁白:

• 您还可以根据 clojure.walk/postwalk 定义 simplify，并将 simplify-1 作为函数参数。这可能更容易扩展，因为 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])))