Упрощение идиоматических выражений в Clojure

Question

Вдохновленный этим прекрасным постом, я хотел реализовать простой упрощающий выражения в 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 это довольно естественный альтернативный подход, особенно с вариантами. Как говорится в вашей статье, типы сумм довольно аккуратны.

(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 с точки зрения clojure.walk/postwalk с 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])))