4

私はHaskellにかなり慣れていないので、ブール式のマニピュレーターとエバリュエーターを含む評価を行っています。

式のタイプは次のとおりです。

type Variable = String
data Expr = T | Var Variable | And Expr Expr | Not Expr

私は多くの質問に取り組みましたが、次の関数にアプローチする方法に行き詰まっています。式内のすべての変数の出現回数をカウントする必要があります

addCounter :: Expr -> Expr
addCounter = undefined

prop_addCounter1 = addCounter (And (Var "y") (And (Var "x") (Var "y"))) == 
                   And (Var "y1") (And (Var "x2") (Var "y1"))
prop_addCounter2 = addCounter (Not (And (Var "y") T)) == 
                   Not (And (Var "y1") T)

これは評価の質問であるため、正確にこれを行う方法についての答えを探しているわけではありませんが、これにどのようにアプローチするかについてのヒントが欲しいですか?

私の頭の中では、y1, のx2部分を取得できるようにカウンターをインクリメントすることを想像していますが、これは実際には Haskell で可能なことではありません (またはとにかく行うことはお勧めしません!)。変数に追加する数を知っていますか?

4

2 に答える 2

2

あなたが言うように、この場合非常に自然な共有カウンターを維持することはできません。代わりにできることは、すべてのExprに再帰的にアクセスするときに現在のカウンター値をツリーに渡し、呼び出されている関数から増分されたカウンター値を受け取ることです。双方向通信である必要があります。現在の値を渡し、更新されたExprと新しいカウンター値を受け取ります。

それぞれの一意の変数名に同じカウンター値を持たせたい場合は、割り当てられたカウンター値への変数名のマッピングを維持する必要があります。現在のカウンター値と同じように、それを渡す必要があります。

お役に立てば幸いです。

于 2013-02-26T22:44:09.730 に答える
1

ステートフルな更新を霧化する

Stateしたがって、これは間違いなくモナドを使用する絶好の機会です。特に、探しているアトミック変換は、String -> String文字列ごとに一意の ID で文字列を列挙する方法です。呼びましょうenumerate

import Control.Monad.State

-- | This is the only function which is going to touch our 'Variable's
enumerate :: Variable -> State OurState Variable

これを行うには、Strings をカウント ( Ints)にマップする状態を追跡する必要があります。

import qualified Data.Map as M
type OurState = Map String Int

runOurState :: State OurState a -> a
runOurState = flip evalState M.empty

runOurState $ mapM enumerate ["x", "y", "z", "x" ,"x", "x", "y"]
-- ["x1", "y1", "z1", "x2", "x3", "x4", "y2"]

そのため、enumerate をかなり直接的にステートフル アクションとして実装できます。

enumerate :: Variable -> State OurState Variable
enumerate var = do m <- get
                 let n = 1 + M.findWithDefault 0 var m
                 put $ M.insert var n m
                 return $ var ++ show n

涼しい！

一般的な式ツリーの折りたたみ

ここで、各タイプの葉Expr -> State OurState Exprに enumerate を適用してマッピングする精巧な折り畳み装置を実際に作成する必要があります。Var

enumerateExpr :: Expr -> State OurState Expr
enumerateExpr T = return T
enumerateExpr (Var s) = fmap Var (enumerate s)
enumerateExpr (And e1 e2) = do em1 <- addCounter e1
                            em2 <- addCounter e2
                            return (Add em1 em2)
enumerateExpr (Not expr) = fmap Not (addCounter expr)

しかし、これはかなり面倒なので、Uniplateライブラリを使用してドライに保ちます。

{-# LANGUAGE DeriveDataTypeable #-}
import Data.Data
import Data.Generics.Uniplate.Data

data Expr = T | Var Variable | And Expr Expr | Not Expr 
  deriving (Show,Eq,Ord,Data)

onVarStringM :: (Variable -> State OurState Variable) -> Expr -> State OurState Expr
onVarStringM action = transformM go
  where go :: Expr -> State OurState Expr
        go (Var s) = fmap Var (action s)
        go x       = return x

このtransformM演算子は、まさに私たちが望むことを行います — ジェネリック ツリー (私たちのExpr) のすべての部分にモナド変換を適用します。

これで、State作成するフル アクションを展開するだけです。addCounter

addCounter :: Expr -> Expr
addCounter = runOurState . onVarStringM enumerate

あっ、待って！

気づいたのですが、これは実際には正しい動作をしていません。変数を正しく列挙していません (prop_addCounter1失敗するがprop_addCounter2成功する)。残念ながら、それがどのように行われるべきかはよくわかりません... しかし、ここで説明されているこの懸念の分離を考えると、適切なenumerate Stateful アクションを記述し、それを同じ一般的なExpr変換機構に適用するのは非常に簡単です。

于 2013-02-27T00:45:07.480 に答える