Haskell：算术表达式AST的从叶到根递归简化技术问询

Great question! Let's walk through how to refine your expression simplifier using a leaf-to-root recursive approach—this ensures we catch every possible simplification by handling the deepest nodes first before moving up to their parent expressions.

First, Recap Your AST & Base Logic #

You’ve got a solid starting point with your Expr type:

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

Your existing simplify rules target basic identity cases (like adding 0) and constant folding, but we can strengthen this by doubling down on the leaf-to-root pattern: always simplify child nodes first, then apply simplification rules to the already-simplified children.

Full Leaf-to-Root Simplifier Implementation #

Here’s a polished version that follows this pattern, with expanded rules to cover more common simplifications:

simplify :: Expr -> Expr
-- Leaf nodes: no simplification needed, return as-is
simplify (Constant n) = Constant n
simplify (Variable x) = Variable x

-- Handle addition: first simplify children, then apply rules
simplify (Add e1 e2) =
  let s1 = simplify e1
      s2 = simplify e2
  in case (s1, s2) of
       -- Identity: adding 0 does nothing
       (Constant 0, _) -> s2
       (_, Constant 0) -> s1
       -- Constant folding: combine two constants into one
       (Constant a, Constant b) -> Constant (a + b)
       -- Combine identical variables (e.g., x + x → 2*x)
       (Variable x, Variable y) | x == y -> Multiply (Constant 2) (Variable x)
       -- Group constant terms in nested additions (e.g., 3 + (5 + x) → 8 + x)
       (Constant a, Add (Constant b) e) -> simplify (Constant (a + b) `Add` e)
       (Add (Constant a) e, Constant b) -> simplify (Constant (a + b) `Add` e)
       -- Fallback: if no simplifications apply, return the simplified children wrapped in Add
       _ -> Add s1 s2

-- Handle multiplication: same leaf-to-root pattern
simplify (Multiply e1 e2) =
  let s1 = simplify e1
      s2 = simplify e2
  in case (s1, s2) of
       -- Annihilator: multiplying by 0 gives 0
       (Constant 0, _) -> Constant 0
       (_, Constant 0) -> Constant 0
       -- Identity: multiplying by 1 does nothing
       (Constant 1, _) -> s2
       (_, Constant 1) -> s1
       -- Constant folding: combine two constants into one
       (Constant a, Constant b) -> Constant (a * b)
       -- Distributive property: a*(b + c) → a*b + a*c (then simplify the result)
       (Constant a, Add s1' s2') -> simplify (Add (Multiply (Constant a) s1') (Multiply (Constant a) s2'))
       (Add s1' s2', Constant a) -> simplify (Add (Multiply s1' (Constant a)) (Multiply s2' (Constant a)))
       -- Fallback: return simplified children wrapped in Multiply
       _ -> Multiply s1 s2

Key Details Explained #

Let’s break down why this works so well for leaf-to-root simplification:

1. Leaf Node Handling: Constants and variables are the base cases—they can’t be simplified further, so we return them immediately.
2. Recurse First, Then Simplify: For every Add or Multiply, we first run simplify on both child expressions. This ensures we’ve already handled all nested simplifications (like Add (Constant 0) (Variable x) becoming Variable x) before we look at the parent node.
3. Pattern Matching on Simplified Children: By using a case statement on the simplified s1 and s2, we can check for all possible simplification scenarios in order of specificity (e.g., constant folding before general cases).
4. Re-Simplify After Transformations: When we apply rules like the distributive property (which creates new Add expressions), we call simplify again on the result to catch any new simplifications that might arise (like constant folding in the new terms).

Example Usage #

Let’s test this with a nested expression to see the leaf-to-root flow:

-- Input: Add (Multiply (Constant 0) (Variable "x")) (Add (Constant 3) (Constant 5))
simplify it → Constant 8

Here’s how it processes:

• First, simplify the inner Multiply (Constant 0) (Variable "x") → Constant 0
• Then simplify the inner Add (Constant 3) (Constant 5) → Constant 8
• Finally, simplify the top-level Add (Constant 0) (Constant 8) → Constant 8

内容的提问来源于stack exchange，提问作者user1518183