11

私のHaskellプロジェクトには式評価器が含まれています。これは、この質問の目的のために次のように簡略化できます。

data Expression a where
    I :: Int -> Expression Int
    B :: Bool -> Expression Bool
    Add :: Expression Int  -> Expression Int  -> Expression Int
    Mul :: Expression Int  -> Expression Int  -> Expression Int
    Eq  :: Expression Int  -> Expression Int  -> Expression Bool
    And :: Expression Bool -> Expression Bool -> Expression Bool
    Or  :: Expression Bool -> Expression Bool -> Expression Bool
    If  :: Expression Bool -> Expression a    -> Expression a -> Expression a

-- Reduces an Expression down to the simplest representation.
reduce :: Expression a -> Expression a
-- ... implementation ...

これを実装する簡単な方法は、次のcaseように、再帰的に評価してパターン マッチする式を記述することです。

reduce (Add x y) = case (reduce x, reduce y) of
                    (I x', I y') -> I $ x' + y'
                    (x', y')     -> Add x' y'
reduce (Mul x y) = case (reduce x, reduce y) of
                    (I x', I y') -> I $ x' * y'
                    (x', y')     -> Mul x' y'
reduce (And x y) = case (reduce x, reduce y) of
                    (B x', B y') -> B $ x' && y'
                    (x', y')     -> And x' y'
-- ... and similarly for other cases.

私には、その定義はややぎこちないように見えるので、次のようにパターン ガードを使用して定義を書き直しました。

reduce (Add x y) | I x' <- reduce x
                 , I y' <- reduce y
                 = I $ x' + y'

この定義は、式に比べてきれいに見えると思いますcaseが、異なるコンストラクターに対して複数のパターンを定義すると、パターンが複数回繰り返されます。

reduce (Add x y) | I x' <- reduce x
                 , I y' <- reduce y
                 = I $ x' + y'
reduce (Mul x y) | I x' <- reduce x
                 , I y' <- reduce y
                 = I $ x' * y'

これらの繰り返されるパターンに注目して、パターン マッチングの繰り返しを削減できる構文または構造があることを期待していました。これらの定義を単純化する一般的に受け入れられている方法はありますか?

編集:パターン ガードを確認した後、ここでドロップインの代わりとして機能しないことに気付きました。とを に縮小できる場合は同じ結果にxなりますが、パターン ガードが一致しない場合は値を縮小しません。et al.の部分式を単純化したいと思います。yI _reduceAdd

4

2 に答える 2

8

私が同様の状況で使用した部分的な解決策の 1 つは、通常の Haskell 操作を取り、それを言語の値に適用する「リフティング」関数にロジックを抽出することです。これは、ラップ/アンラップとその結果のエラー処理を抽象化します。

アイデアは、適切なエラー処理を使用して、カスタム型に出入りするための 2 つの型クラスを作成することです。次に、これらを使用して、次のliftOpような関数を作成できます。

liftOp :: (Extract a, Extract b, Pack c) => (a -> b -> c) -> 
            (Expression a -> Expression b -> Expression c)
liftOp err op a b = case res of
  Nothing  -> err a' b'
  Just res -> pack res
  where res = do a' <- extract $ reduce' a
                 b' <- extract $ reduce' b
                 return $ a' `op` b'

次に、特定のケースごとに次のようになります。

Mul x y -> liftOp Mul (*) x y

それほど悪くはありません。過度に冗長ではありません。これには重要な情報が含まれます: Mulgets にマップされ*、エラーの場合はMul再度適用します。

パッキングとアンパッキングのインスタンスも必要ですが、とにかく便利です。巧妙なトリックの 1 つは、フォームのインスタンスを使用して、DSL に関数を自動的に埋め込むこともできることです(Extract a, Pack b) => Pack (a -> b)。

これがあなたの例で正確に機能するかどうかはわかりませんが、良い出発点になることを願っています. pack全体を通して追加のエラー処理を配線したいかもしれませんが、良いニュースは、そのほとんどが、 、unpackおよびの定義に組み込まれているliftOpため、まだかなり集中化されていることです。

関連する（ただし多少異なる）問題に対して同様の解決策を書きました。これは、Haskell のネイティブ値とインタープリターの間を行き来する方法でもありますが、インタープリターの構造は異なります。ただし、同じアイデアのいくつかはまだ適用されるはずです!

于 2014-08-14T18:08:29.483 に答える
2

この回答は、次の機能を示唆するRampion のフォローアップの質問に触発されています。

step :: Expression a -> Expression a
step x = case x of
  Add (I x) (I y) -> I $ x + y
  Mul (I x) (I y) -> I $ x * y
  Eq  (I x) (I y) -> B $ x == y
  And (B x) (B y) -> B $ x && y
  Or  (B x) (B y) -> B $ x || y
  If  (B b) x y   -> if b then x else y
  z               -> z

step単一の用語を見て、それを削減するために必要なすべてが存在する場合、それを削減します。を装備するとstep、式ツリーのあらゆる場所で用語を置き換える方法だけが必要になります。すべての用語内で関数を適用する方法を定義することから始めることができます。

{-# LANGUAGE RankNTypes #-}

emap :: (forall a. Expression a -> Expression a) -> Expression x -> Expression x
emap f x = case x of
    I a -> I a
    B a -> B a
    Add x y   -> Add (f x) (f y)
    Mul x y   -> Mul (f x) (f y)
    Eq  x y   -> Eq  (f x) (f y)
    And x y   -> And (f x) (f y)
    Or  x y   -> Or  (f x) (f y)
    If  x y z -> If  (f x) (f y) (f z)

ここで、用語と用語内のすべての場所の両方に関数を適用する必要があります。2 つの基本的な可能性があります。関数を用語に適用してから内部で適用するか、後で関数を適用することができます。

premap :: (forall a. Expression a -> Expression a) -> Expression x -> Expression x
premap f = emap (premap f) . f

postmap :: (forall a. Expression a -> Expression a) -> Expression x -> Expression x
postmap f = f . emap (postmap f)

これにより、 の使用方法に 2 つの可能性が与えられます。これをおよびstepと呼びます。shortenreduce

shorten = premap step
reduce = postmap step

これらの動作は少し異なります。shorten最も内側のレベルの用語を削除し、それらをリテラルに置き換えて、式ツリーの高さを 1 つ短くします。reduce式ツリーを完全にリテラルに評価します。これは、同じ入力でこれらのそれぞれを反復した結果です

"shorten"
If (And (B True) (Or (B False) (B True))) (Add (I 1) (Mul (I 2) (I 3))) (I 0)
If (And (B True) (B True)) (Add (I 1) (I 6)) (I 0)
If (B True) (I 7) (I 0)
I 7
"reduce"
If (And (B True) (Or (B False) (B True))) (Add (I 1) (Mul (I 2) (I 3))) (I 0)
I 7

一部縮小

あなたの質問は、式を完全に削減できないことを時々期待していることを意味します。変数を追加して、このケースを示すために何かを含めるように例を拡張しますVar。

data Expression a where
    Var :: Expression Int
    ...

Vartoのサポートを追加する必要がありますemap。

emap f x = case x of
   Var -> Var
   ...

bind変数を置き換え、evaluateFor完全な評価を実行し、式を 1 回だけトラバースします。

bind :: Int -> Expression a -> Expression a
bind a x = case x of
    Var -> I a
    z   -> z

evaluateFor :: Int -> Expression a -> Expression a
evaluateFor a = postmap (step . bind a)

reduce変数を含む例を反復すると、次の出力が生成されます

"reduce"
If (And (B True) (Or (B False) (B True))) (Add (I 1) (Mul Var (I 3))) (I 0)
Add (I 1) (Mul Var (I 3))

リダクションからの出力式が の特定の値に対して評価される場合、Var式をリテラルにまで縮約できます。

"evaluateFor 5"
Add (I 1) (Mul Var (I 3))
I 16

応用的

emapの代わりに で記述できApplicative Functor、postmap式以外のデータ型に適した一般的なコード片にすることができます。その方法については、rampion のフォローアップの質問に対するこの回答で説明されています。

于 2014-08-18T19:13:08.967 に答える