1

以下のすべての式を含む一般的な規則をどのように与えることができますか? たとえば、1 つの式、もう 1 つはサブ用、もう 1 つはマルチ用です。再帰を使用する必要がありますが、混乱しました...

simplify :: Expr->Expr

simplify (Mult (Const 0)(Var"x"))
 = Const 0 
simplify (Mult (Var "x") (Const 0))
 = Const 0
simplify (Plus (Const 0) (Var "x")) 
= Var "x"
simplify (Plus (Var "x") (Const 0))
 = Var "x" 
simplify (Mult (Const 1) (Var"x")) 
= Var "x"
simplify (Mult(Var"x") (Const 1))
 = Var "x" 
simplify (Minus (Var"x") (Const 0))
 = Var "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
4

2 に答える 2

7

まず第一に、私は Haskell についてほとんど知識がなく、この言語のプログラミングに費やした合計時間は 5 年ほどで 8 時間を超えていませんが、この言語については十分に読んでいます。したがって、私の間違いなく恐ろしいスタイルを許してください。

私がこの問題に取り組んだのは、Haskell プログラミングに少し慣れるための簡単な方法のように思えたからです。まず、サンプルに触発されたデータ型を作成しました。

data Expr = Const Int | Mult Expr Expr | Plus Expr Expr | Var String

オリジナルより少しシンプルにして、マイナスを省略しましたが、それ以外は同じです。

たとえば「Const 4」を使用して構築された値は、適用可能な show 関数がなかったため、上記では印刷できないことがすぐにわかりました。Expr を Show 型クラスのインスタンスにし、演算子の優先順位を考慮して単純な show の定義を提供しました。

instance Show Expr where
    show (Const n) = show n
    show (Var n) = show n
    show (Plus a b) = (show a) ++ "+" ++ (show b)
    show (Mult a b) = "(" ++ (show a) ++ ") * (" ++ (show b) ++ ")"

次は単純化タスクそのものです。Glomek が示唆しているように、1 つの関数でパターン マッチングを使用するだけですべてを評価しようとすると問題が発生します。

具体的には、特定の操作 (この例ではすべての操作がバイナリです) について、最初に左のツリーを単純化し、次に右のツリーを単純化し、次にそれらのサブツリーの評価結果に基づいて現在の Expr を単純化します。たとえば、両方が Const に単純化されている場合、サブツリー全体を評価された操作に置き換えることができます。ただし、パターン マッチングでは、単純化された後にサブツリーが返すものではなく、直下のノードの子に基づいて何を行うかを選択する必要があります。

したがって、現在のノードを定数部分式として評価するかどうかを決定する仕事をパターン マッチングで行うには、サブツリーを単純化し、単純化された全体に基づいてディスパッチすることが重要です。

これは、eval と呼ばれる別の関数を使用して行いました。この関数の目的は、サブツリーが既に縮小されていると仮定して、縮小できるものをパターン マッチングすることです。また、0 と 1 の乗算、および 0 の加算も処理します。

-- Tries to evaluate any constant expressions.
eval :: Expr -> Expr
eval (Mult (Const a) (Const b)) = Const (a * b)
eval (Mult (Const a) b)
    | a == 0 = Const 0
    | a == 1 = b
    | otherwise = (Mult (Const a) b)
eval (Mult a (Const b))
    | b == 0 = Const 0
    | b == 1 = a
    | otherwise = (Mult a (Const b))
eval (Plus (Const a) (Const b)) = Const (a + b)
eval (Plus (Const a) b)
    | a == 0 = b
    | otherwise = (Plus (Const a) b)
eval (Plus a (Const b))
    | b == 0 = a
    | otherwise = (Plus a (Const b))
eval e = e

これで eval ができ、式ツリーのトップ レベルで安全に呼び出すことができる (つまり、無限に再帰しない) ことがわかったので、サブツリーを単純化した後、simplify から呼び出すことができます。

-- Tries to match evaluation rules after simplifying subtrees.
simplify :: Expr -> Expr
simplify (Plus a b) = eval (Plus (simplify a) (simplify b))
simplify (Mult a b) = eval (Mult (simplify a) (simplify b))
simplify e = e

このバージョンの単純化には多くの制限があります。非 Const サブツリーに乗算を分散せず、式を並べ替えて定数式をまとめることもありません (したがって、1+a+2 に相当するものは次のように単純化されません)。 a+3) など。ただし、基本的な作業は完了します。

于 2008-11-27T20:03:19.623 に答える
0

再帰は、ネストされた式を処理する必要がある場合に使用されます。たとえば、どうすれば簡単に (プラス (プラス 2 3) (プラス 4 5)) になりますか?

1 つのアプローチは、2 つの機能に分割することです。1 レベルのロジック (上に示したもの) を独自の関数に移動します。メインの単純化関数には、Plus の次のようなルールが含まれる場合があります。

simplify (Plus x y) = simplify_one_level (Plus (simplify x) (simplify y))
于 2008-11-27T17:52:55.003 に答える