1

我怎样才能给出一个包含以下所有表达式的一般规则？例如，一个表达式，另一个用于 sub 和一个用于 mult。我需要使用递归，但我很困惑......

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”构造的值不能用上面的方法打印，因为没有适用的显示功能。我将 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) ++ ")"

接下来是简化任务本身。正如格洛梅克所暗示的那样，尝试在一个函数中使用模式匹配来评估所有内容存在问题。

具体来说，对于任何给定的操作（示例中的所有操作都是二元的），您希望首先简化左树，然后是右树，然后根据这些子树评估的内容简化当前 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，并且我知道在表达式树的顶层调用是安全的（即它不会无限递归），我可以在简化子树后从 simple 中调用它：

-- 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））？

一种方法是将其分解为两个功能。将一层逻辑（您在上面显示）移动到它自己的函数中。主要的简化函数可能有一个类似于以下 Plus 的规则：

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