6

基本的な算術式を単純化するにはどうすればよいですか?

例えば

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

変数 (または変数と定数) が連結されるとは思わないでしょう: Var "st" は Var "s" とは異なる変数です。

私が達成したいのは、上記のような関数を使用するモジュールを作成することですsimplify :: Expr->Expr

4

4 に答える 4

11

さて、あなたは正しい一般的なモデルを持っています。より多くのルールが必要で、単純化プロセスを再帰的に適用するだけです。

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
于 2008-11-26T16:49:36.270 に答える
1

例を挙げると、あなたが与えた式を単純化する関数があります。等号の左側のパターンの 1 つが一致するまで、単純化の各定義が上から下に試行されるという考え方です。最後の定義の目的は、これ以上単純化する既知の方法がない場合に、再帰から抜け出すことです。

simplify :: Expr -> Expr
simplify (Plus l         (Const 0)) = simplify l
simplify (Plus (Const 0) r        ) = simplify r
simplify x                          = x
于 2009-08-21T23:19:29.070 に答える
1

私は何十年も前に AI クラスのプロジェクトとしてこのようなことをしました。このクラスは LISP を使用していたので、最初に行ったのは、式を中置表記から S 式に変換することでした。

次に、「ツリー」を再帰的にトラバースし、各ノードに一連のルールを適用します。たとえば、このノードにオペランドが両方とも定数である演算が含まれている場合、演算をすぐに実行し、ノードを結果で置き換えます。

基本的な機能が整ったら、新しい単純化ルールをシステムに追加するだけでした。

最後に、S-Expression は表示用に中置記法に変換されました。

于 2008-11-27T16:02:19.797 に答える
0

GMP の合理性と同様に、ここで合理性について話しているのでしょうか。もしそうなら、2 番目の引数をその逆数にしてから乗算することにより、除算を単純化できます。

それとは別に、乗算は複数回の足し算であり、除算は複数回の減算です。

ミッチがコメントで言ったように、あなたが単純化しようとしているものについて、もう少し情報を得ることができます.

于 2008-11-26T12:43:02.243 に答える