Haskell递归

Question

我一直在努力为给定表达式中的变量添加一个计数器,并具有以下测试用例:

prop_add1 = add (And (Var "a") (And (Var "b") (Var "a"))) ==
And (Var "a1") (And (Var "b2") (Var "a1"))

我一直在使用Pattern Matching和Recursion来尝试找到解决方案.虽然我有点陷入困境,但我尝试将原始变量添加到列表中,然后使用列表确定要输出的变量名称,但我无法弄清楚如何正确实现它并且我的输出只添加1到所有变量的结尾.

我想知道有更好/更容易的解决方案吗？

到目前为止我的尝试:

add :: Expr -> Expr
add T = T
add (Var x) = Var (x ++ show (check2(check x)))
add (And e1 e2) = And (add e1) (add e2)
add (Not e1) = Not (add e1)

check :: Variable -> [Variable]
check p = [p]

check2 :: [Variable] -> Int
check2 p = length (union p p)

Answer 1

您需要保持将变量名称映射到数字的环境.就像是

add :: Expr -> Expr
add expr = fst $ addWithEnv emptyEnv expr
  where
    emptyEnv = []
    addWithEnv env (And e1 e2)
        = case addWithEnv env e1 of
            (e1', env') ->
              case addWithEnv env' e2 of
                (e2', env'') -> (And e1' e2', env'')
    addWithEnv env (Var name)
        = case lookup name env of
            Just k -> -- stopping here,it's homework

我希望我已经足够让你填写.

更新:

在您的尝试中,您不会跟踪您已经看到的变量,因此每个变量似乎都是第一个,并且每次附加"1".编号项是有状态计算,您必须记录到目前为止已经看到哪些变量,以便为先前看到的变量分配旧数,并知道分配下一个尚未看到的变量的数字.所以你必须在工人身边传播这个记录.如果你已经知道了这个Monad类以及如何使用它,你可以使用Statemonad 隐式携带它,否则你必须明确地携带它.然后add成为一个包装器,调用最初为空状态的worker(在编号/重命名开始之前,还没有看到变量).然后,worker查看给定表达式的子表达式(如果有)并重命名变量并在遇到新变量时更新状态.

所以在上面的草图中,我们有

addWithEnv :: [(String,Int)] -> Expr -> (Expr, [(String,Int)])

因为我们不能改变状态,所以我们必须将新状态与重命名的表达式一起返回.现在你必须定义每种表达式的结果,

addWithEnv env T = ??
addWithEnv env (Var name) = ??
addWithEnv env (Add e1 e2) = ??
addWithEnv env (Not e) = ??

T当然,这种情况不会重命名,也不会更新环境.Var之前已经看过A ,在这种情况下环境保持不变,在这种情况下,它被添加到环境中.甲Not e对环境为相同的影响e,和一个And e1 e2具有第一的组合效果e1然后e2对环境.