如何用F#化简表达式 ( a + x )+( a – x ) => 2 * a

【摘要】     如果使用过Matlab或者Maple等软件，应该知道这类数学软件的符号计算引擎非常强大，可以进行数学公式的推导，比如可以对数学公式进行化简。当然，实现一个功能完备的化简引擎还是不容易的。这里用F# 实现一个简单的化简函数: ( a + x )+( a – x ) => 2 * a

如果使用过Matlab或者Maple等软件，应该知道这类数学软件的符号计算引擎非常强大，可以进行数学公式的推导，比如可以对数学公式进行化简。当然，实现一个功能完备的化简引擎还是不容易的。这里用F# 实现一个简单的化简函数。

首先定义一个表达式数据类型：

type Expr = 
  | CstF of float
  | Var of string
  | Add of Expr * Expr  // +
  | Sub of Expr * Expr // -
  | Mul of Expr * Expr // *
  | Div of Expr * Expr // / 

其次定义一个化简函数，它是化简规则的具体实现：

(* 化简 *)
let rec simplify e =
    match e with
    | CstF f            -> CstF f
    | Var x             -> Var x 
    | Add(CstF a, CstF b) ->  CstF (a + b)  
    | Add(CstF 0., e2) -> simplify e2  
    | Add(e1 , CstF 0.) -> simplify e1
    | Add(e1 , e2) when e1 = e2 -> simplify (Mul(CstF 2., simplify e1))
    | Add(Mul(CstF a, e1) , Mul(CstF b, e2)) when e1 = e2 -> simplify (Mul(CstF (a + b), simplify e1))
    | Add(e1,Sub(a,e2))  when e1 = e2 -> simplify a
    | Add(Add(a, x1),Sub(b, x2)) when x1 = x2 -> simplify(Add(simplify a,simplify b))
    | Add(e1, e2) ->  Add(simplify e1,simplify e2)
    | Mul(CstF a, CstF b) -> CstF (a * b)   
    | Mul(CstF 0., e2) -> CstF 0.   
    | Mul(e1 , CstF 0.) -> CstF 0. 
    | Mul(CstF 1., e2) -> simplify e2   
    | Mul(e1 , CstF 1.) -> simplify e1
    | Mul(e1, e2) -> Mul(simplify e1,simplify e2)
    | Sub(CstF a, CstF b)  -> CstF (a - b) 
    | Sub(Add(e1,e2),e3) when e1 = e3 ->  simplify e2 
    | Sub(Add(e1,e2),e3) when e2 = e3 ->  simplify e1
    | Sub(e1, e2) when e1 = e2 -> CstF 0. 
    | Sub(e1, e2) -> Sub(simplify e1,simplify e2)
    | Div(CstF a, CstF b)  -> CstF (a / b) 
    | Div(CstF 0., e2) -> CstF 0. 
    | Div(e1, e2) when e1 = e2 -> CstF 1. 
    | Div(e1, e2) -> Div(simplify e1,simplify e2)
    | _          -> failwith "unknown operation"

这个化简函数，返回一个是一个自定义DSL的表达式结构，如Sub(Var “a”, Var “x”) ，下面再定义一个可以化简和打印出字符串的函数：

let rec simp e =
    let res = simplify e
    match res with
    | CstF f            -> string f
    | Var x             ->  x 
    | Add(e1 , e2) ->  "(" + (simp e1) + "+" + (simp e2) + ")"
    | Sub(e1 , e2) ->  "(" + (simp e1) + "-" + (simp e2) + ")"
    | Mul(e1 , e2) ->  "(" + (simp e1) + "*" + (simp e2) + ")"
    | Div(e1 , e2) ->  "(" + (simp e1) + "/" + (simp e2) + ")"
    | _          -> failwith "unknown operation";;

最后，再定义一个打印DSL表达式的函数：

let rec printExpr e =
    match e with
    | CstF f            -> string f
    | Var x             ->  x 
    | Add(e1 , e2) ->  "(" + (printExpr e1) + "+" + (printExpr e2) + ")"
    | Sub(e1 , e2) ->  "(" + (printExpr e1) + "-" + (printExpr e2) + ")"
    | Mul(e1 , e2) ->  "(" + (printExpr e1) + "*" + (printExpr e2) + ")"
    | Div(e1 , e2) ->  "(" + (printExpr e1) + "/" + (printExpr e2) + ")"
    | _          -> failwith "unknown operation";;

至此，可以测试一下，如何化简数学表达式

//( a + x ) + ( a - x )
let e1 = Add(Add(Var "a", Var "x"),Sub(Var "a", Var "x")) 
printExpr e1 + " => " + simp e1 ;;