Haskell中的符號簡化（使用遞歸？）

Question

如何給出包含以下所有表達式的一般規則？ 例如一個表達式，另一個表示子表達式，另一個表示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 

Answer 1

遞歸來當你需要處理嵌套表達的影響。例如，你怎麼簡單（Plus（Plus 2 3）（Plus 4 5））？

一種方法是將其分成兩個功能。將上面顯示的一級邏輯移動到它自己的函數中。主要簡化功能可能有類似於加上以下規則：

simplify (Plus x y) = simplify_one_level (Plus (simplify x) (simplify y)) 

Answer 2

首先是：我知道哈斯克爾相當小的，花了我的全部時間編程語言散佈在5年內不超過8小時儘管我已經閱讀了大量有關該語言的內容。因此，請原諒我毫無疑問的可怕風格。

我解決了這個問題，因爲它看起來像一個簡單的方法來進入一點Haskell編程。首先，我提出由樣本的啓發數據類型：

data Expr = Const Int | Mult Expr Expr | Plus Expr Expr | Var String 

我把它比原來稍微簡單，並留下了減，但除此之外，它是相同的。

我很快發現使用例如由於沒有適用的演出功能，因此「Const 4」不能打印上述內容。我做了Expr的顯示類型的類的實例，並提供了展示的一個簡單的定義，考慮運算符的優先考慮：

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) ++ ")" 

接下來是簡化任務本身。正如Glomek所暗示的那樣，在一個函數中嘗試使用模式匹配來評估所有內容時存在一個問題。

具體而言，對於任何給定的操作（示例中的所有操作都是二進制），您首先要簡化左樹，然後右樹，然後根據這些子樹計算的內容簡化當前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，我知道它是安全的，在一個表達式樹的頂層調用（即它不會無限遞歸），我可以從簡化稱之爲我已經簡化了子樹之後：

-- 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）等等。但是，它完成了基本的工作。