Как я могу упростить основное арифметическое выражение?

Question

Как я могу упростить основное арифметическое выражение?

, например

module ExprOps where 

simplify :: Expr -> Expr
simplify (Plus(Var"x") (Const 0)) = Var "x"

Что мне делать?

---

module Expr where

-- Variables are named by strings, assumed to be identifiers.
type Variable = String

-- Representation of expressions.
data Expr = Const Integer
          | Var Variable
          | Plus Expr Expr
          | Minus Expr Expr
          | Mult Expr Expr
          deriving (Eq, Show)

Упрощения, которые я имею в виду:

0*e = e*0 = 0
1*e = e*1 = 0+e = e+0 = e-0 = e

и упрощение постоянных подвыражений, например, Плюс (Const 1) (Const 2) станет Const 3. Я бы не ожидал, что переменные (или переменные и константы) будут объединены: Var "st" является отличной переменной от Var "s".

Чего я хочу добиться, так это создать модуль, подобный приведенному выше, который использует функцию с именем simplify :: Expr->Expr

Answer 1

Ну, у вас есть правильная общая модель. Вам просто нужно больше правил и рекурсивно применить процесс упрощения.

simplify :: Expr -> Expr 
simplify (Mult (Const 0) x) = Const 0 
simplify (Mult x (Const 0)) = Const 0
simplify (Plus (Const 0) x) = simplify x
simplify (Plus x (Const 0)) = simplify x 
simplify (Mult (Const 1) x) = simplify x 
simplify (Mult x (Const 1)) = simplify x 
simplify (Minus x (Const 0)) = simpify x
simplify (Plus (Const x) (Const y)) = Const (x + y)
simplify (Minus (Const x) (Const y)) = Const (x - y)
simplify (Mult (Const x) (Const y)) = Const (x * y)
simplify x = x

Answer 2

Просто для примера приведу функцию, которая упростит приведенное вами выражение. Идея состоит в том, что каждое определение упрощения пробуется сверху вниз, пока не совпадет один из шаблонов в левой части знака равенства. Цель последнего определения - вырваться из рекурсии, если нет никакого известного способа еще больше упростить.

simplify :: Expr -> Expr
simplify (Plus l         (Const 0)) = simplify l
simplify (Plus (Const 0) r        ) = simplify r
simplify x                          = x

Answer 3

Я делал что-то подобное в качестве проекта для класса ИИ десятилетия назад. Класс использовал LISP, поэтому первым делом я преобразовал выражение из инфиксной нотации в S-выражение.

Тогда речь шла о рекурсивном обходе «дерева» и применении набора правил на каждом узле. например если этот узел содержит операцию, операнды которой являются константами, выполните операцию сейчас и замените узел результатом.

После того, как базовая функциональность была создана, нужно было добавить в систему новые правила упрощения.

Наконец, S-выражение было преобразовано обратно в инфиксную запись для отображения.

Answer 4

Мы говорим здесь о рациональных вещах, как о рациональных GMP? Если это так, то можно упростить деление, сделав второй аргумент обратным, а затем умножив его.

Кроме того, умножение является сложением, выполненным более одного раза, а деление - вычитанием, выполненным более одного раза.

Как сказал Митч в комментариях, мы могли бы получить больше информации о том, что вы пытаетесь упростить.