Haskell：从leafs到root的递归

发布时间：2020-12-14 00:01:47 所属栏目：Linux 来源：网络整理

导读：我有一个基本数学运算表达式的AST： data Expr = Constant Int | Variable String | Add Expr Expr | Multiply Expr Expr deriving (Show) 我还有一个非常简单的函数,简化了给定的表达式： simplify :: Expr - Exprsimplify (Add (Constant 0) e) = simplify

我有一个基本数学运算表达式的AST：

data Expr = Constant Int
          | Variable String
          | Add Expr Expr
          | Multiply Expr Expr
          deriving (Show)

我还有一个非常简单的函数,简化了给定的表达式：

simplify :: Expr -> Expr
simplify (Add (Constant 0) e) = simplify e
simplify (Add e (Constant 0)) = simplify e
simplify (Add (Constant a) (Constant b)) = Constant (a + b)
simplify (Add e1 e2) = Add (simplify e1) (simplify e2)
simplify (Multiply (Constant 0) _) = Constant 0
simplify (Multiply _ (Constant 0)) = Constant 0
simplify (Multiply (Constant 1) e) = e
simplify (Multiply e (Constant 1)) = e
simplify (Multiply (Constant a) (Constant b)) = Constant (a * b)
simplify (Multiply e1 e2) = Multiply (simplify e1) (simplify e2)
simplify e = e

不幸的是,这个函数不是很有效,因为它简化了从根到叶子的表达式(从上到下).考虑这个表达式：

exampleExpr :: Expr
exampleExpr = Add
                (Multiply (Constant 1) (Variable "redrum"))
                (Multiply (Constant 0) (Constant 451))

它需要两个函数调用(简化(简化exampleExpr))以将此表达式减少为变量“redrum”.使用自下而上的方法,它应该只花费一个函数调用.

我还没有足够的经验能够有效地编写这段代码.所以我的问题是：如何重写这个函数来简化从leafs到root(从下到上)的给定表达式？

解决方法

首先,你错过了几个递归调用.在这些方面：

simplify (Multiply (Constant 1) e) = e
simplify (Multiply e (Constant 1)) = e

您应该用简化e替换右侧.

simplify (Multiply (Constant 1) e) = simplify e
simplify (Multiply e (Constant 1)) = simplify e

现在从下往上重写表达式.问题在于,您在等式的左侧寻找简化模式,即在简化子项之前.您需要先简化子项,然后查找模式.

simplify :: Expr -> Expr
simplify (Add x y) =
    case (simplify x,simplify y) of
        (Constant 0,e) -> e
        (e,Constant 0) -> e
        (Constant a,Constant b) -> Constant (a + b)
        (x1,y1) -> Add x1 y1
simplify (Multiply x y) =
    case (simplify x,_) -> Constant 0
        (_,Constant 0) -> Constant 0
        (Constant 1,Constant 1) -> e
        (Constant a,Constant b) -> Constant (a * b)
        (x1,y1) -> Multiply x1 y1
simplify e = e

在等式的左侧,我们找到当前节点的子节点.在右边,我们在简化的孩子中寻找模式.改进此代码的一种方法是分离查找和替换子项以及匹配简化模式的两个职责.这是递归替换Expr的每个子树的一般函数：

transform :: (Expr -> Expr) -> Expr -> Expr
transform f (Add x y) = f $Add (transform f x) (transform f y)
transform f (Multiply x y) = f $Multiply (transform f x) (transform f y)
transform f e = f e

transform采用(非递归)转换函数,该函数计算单节点模式的替换,并以自下而上的方式递归地将其应用于树中的每个节点.要编写转换函数,只需查找有趣的模式,忘记递归重写子项.

simplify = transform f
    where
        f (Add (Constant 0) e) = e
        f (Add e (Constant 0)) = e
        f (Add (Constant a) (Constant b)) = Constant (a + b)
        f (Multiply (Constant 0) _) = Constant 0
        f (Multiply _ (Constant 0)) = Constant 0
        f (Multiply (Constant 1) e) = e
        f (Multiply e (Constant 1)) = e
        f (Multiply (Constant a) (Constant b)) = Constant (a * b)
        f e = e

由于f的参数已经通过变换重写了它的子句,因此我们不需要穷尽地匹配每个可能的模式或明确地通过该值进行递归.我们寻找我们关心的那些,并且不需要转换的节点落入到全包的情况下.

像lens的Plated module这样的通用编程库采用了像transform这样的编程模式,并使它们具有通用性.您(或编译器)编写少量代码来表征数据类型的形状,并且库实现递归的高阶函数,例如转换一次和所有.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!