Haskell:从leafs到root的递归

Question

我有一个基本数学运算表达式的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))

它需要两个函数调用(simplify (simplify exampleExpr))来减少这个表达式Variable "redrum".使用自下而上的方法,它应该只花费一个函数调用.

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

Answer 1

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

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

你应该用右手边替换simplify 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, simplify y) of
        (Constant 0, _) -> Constant 0
        (_, Constant 0) -> Constant 0
        (Constant 1, e) -> e
        (e, 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自己的论证已经重写了它的子句transform,因此我们不需要详尽地匹配每个可能的模式或明确地通过该值进行递归.我们寻找我们关心的那些,并且不需要转换的节点落到了全包的f e = e情况.

像模块这样lens的通用编程库采用类似编程模式并使它们具有通用性.您(或编译器)编写少量代码来表征数据类型的形状,并且库实现递归的高阶函数,例如一劳永逸.Platedtransformtransform