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

原子化你的有状态更新

所以，这绝对是使用Statemonad 的好时机。特别是，您正在寻找的原子转换是一种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

凉爽的！

一般折叠在表达式树上

现在我们真的应该编写一个精细的折叠设备，通过在每个-type 叶子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 回答