如何用F#实现表达式展开

【摘要】        数学软件Matlab或者Maple等软件可以对数学表达式进行展开操作，如Matlab软件中可以用 expand((x-2)*(x-4))对表达式(x-2)*(x-4)进行展开，即x^2 – 6*x + 8。那么这种抽象的数学表达式是如何实现的呢？本文就用F#语言来简单的讲解一下思路。实现expand(sin(3+x)-sin(3-x)) => 2*cos(3)*sin(x) 。

数学软件Matlab或者Maple等软件可以对数学表达式进行展开操作，如Matlab软件中可以用 expand((x-2)*(x-4))对表达式(x-2)*(x-4)进行展开，即x^2 – 6*x + 8。那么这种抽象的数学表达式是如何实现的呢？下面我们就用F#语言来简单的讲解一下思路。当然，如果要实现完备的表达式，内部还是有非常多的细节需要处理，这里只讲解一下思路，并不构建一个完备的表达式展开函数。

首先，我们需要将常见的数学上展开的公式进行罗列，这里处理如下表达式：

(a+x)*(b+x) => ab + a*x + b*x + x^2

sin(a+b)=sin(a)*cos(b)+cos(a)*sin(b)

sin(a-b)=sin(a)*cos(b)-cos(a)*sin(b)

cos(a+b)=cos(a)*cos(b)-sin(a)*sin(b)

cos(a+b)=cos(a)*cos(b)+sin(a)*sin(b)

有了这些表达式展开规则后，可以构建F# expand函数，对表达式进行展开处理。下面定义一个Expr类型：

type Expr = 
  | CstF of float
  | Var of string
  | Add of Expr * Expr  // +
  | Sub of Expr * Expr // -
  | Mul of Expr * Expr // *
  | Div of Expr * Expr // / 
  | Pow of Expr * Expr // ^ 
  | Sin of Expr  
  | Cos of Expr 
;;

下面定义一个expand 函数，它也是一个递归函数，用rec关键字来修饰expand函数：

let rec expand e =
    match e with
    | CstF f            -> CstF f
    | Var x             -> Var x 
    | Add(CstF a, CstF b) ->  CstF (a + b)  
    | Add(CstF 0., e2) -> expand e2  
    | Add(e1 , CstF 0.) -> expand e1
    | Add(e1 , e2) -> Add(expand (e1),expand (e2))
    | Sub(e1 , e2) -> Sub(expand (e1),expand (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) -> expand e2   
    | Mul(e1 , CstF 1.) -> expand e1
    | Mul(Add(e1,e2),Add(e3,e4)) -> Add(Add(expand (Mul(e1,e3)),expand (Mul(e2,e4))),Add(expand (Mul(e1,e4)),expand (Mul(e2,e3))))
    | Mul(Sub(e1,e2),Sub(e3,e4)) -> Sub(Add(expand (Mul(e1,e3)),expand (Mul(e1,e4))),Add(expand (Mul(e1,e4)),expand (Mul(e2,e3))))
    | Mul(Add(e1,e2),Sub(e3,e4)) -> Add(Add(expand (Mul(e1,e3)),expand (Mul(e2,e3))),Sub(expand (Mul(e1,e4)),expand (Mul(e2,e4))))
    | Mul(Sub(e1,e2),Add(e3,e4)) -> Sub(Add(expand (Mul(e1,e3)),expand (Mul(e1,e4))),Add(expand (Mul(e2,e3)),expand (Mul(e2,e4))))
    | Pow(e1,CstF 1.) -> expand e1
    | Pow(e1,CstF a) when a > 1. -> expand (Mul(e1,expand(Pow(e1,CstF (a - 1.)))))
    | Sin(Add(a,b)) -> expand (Add(Mul(Sin(a),Cos(b)),Mul(Cos(a),Sin(b)))) //sin(a+b)=sinacosb+cosasinb
    | Sin(Sub(a,b)) -> expand (Sub(Mul(Sin(a),Cos(b)),Mul(Cos(a),Sin(b)))) //sin(a-b)=sinacosb-sinbcosa
    | Cos(Add(a,b)) -> expand (Sub(Mul(Cos(a),Cos(b)),Mul(Sin(a),Sin(b))))
    | Cos(Sub(a,b)) -> expand (Add(Mul(Cos(a),Cos(b)),Mul(Sin(a),Sin(b))))
    | e          -> e;;

另外，可以定义一个表达式化简函数simplify，如下所示：

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(Mul(CstF a, e1) , Mul(e2,CstF b)) when e1 = e2 -> simplify (Mul(CstF (a + b), simplify e1))
    | Add(Mul(e1, CstF a) , Mul(e2,CstF b)) when e1 = e2 -> simplify (Mul(CstF (a + b), simplify e1))
    | Add(Mul(e1, CstF a) , Mul(CstF b, e2)) when e1 = e2 -> simplify (Mul(CstF (a + b), simplify e1))
    | Add(Mul(e1, e2) , Mul(e3, e4)) when e1 = e4 && e2 = e3 -> simplify (Mul(CstF 2., simplify (Mul(e1,e3))))  //add
    | 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)
    | Mul(Var x, Var y) when x = y -> Pow(Var x, CstF 2.)
    | Mul(Var x, Pow(Var y,CstF a)) when x = y -> Pow(Var x, CstF (a+1.))
    | Mul(Pow(Var x,CstF a), Pow(Var y,CstF b)) when x = y -> Pow(Var x, CstF (a+b))
    | Sub(CstF a, CstF b)  -> CstF (a - b) 
    | Sub(Add(e1, e2),Sub(e3, e4)) when e1 = e3 -> simplify (Add(e2,e4)) 
    | 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)
    | e          -> e;;

最后，需要一个将DSL数据类型翻译为字符串，打印到控制台，如下所示：

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

注意：这里有些规则并为经过严格测试，并不保证所有的规则都正确。

至此，一个简单的F#表达式展开函数就完成了。下面给出一个示例：

let e1 = Mul(Add(CstF 3., Var "x"),Add(CstF 2., Var "x")) ;;
let e2 = expand e1;;
printExpr (simplify e2);;

利用dotnet fsi进入交互模式，并执行：

即 expand((3+x)*(2+x)) => 6 + x^2 + 5*x

下面再给出一个示例：

let e1 = Pow(Add(CstF 3., Var "x"),CstF 2.) ;;
let e2 = expand e1;;
printExpr (simplify e2);;

即 expand((3+x)^2) => 9 + x^2 + 6*x

其次，再给出一个三角函数展开示例：

let e1 = Sin(Add(CstF 3., Var "x")) ;; //sin(3+x)
let e2 = expand e1;;
printExpr e2;;

即 expand(sin(3+x)) => sin(3)*cos(x)+cos(3)*sin(x)

最后，再给出一个复合三角函数展开示例：

let e1 = Sub(Sin(Add(CstF 3., Var "x")),Sin(Sub(CstF 3., Var "x"))) ;; //sin(3+x)-sin(3-x)
let e2 = expand e1;;
printExpr (simplify e2);;

即 expand(sin(3+x)-sin(3-x)) => 2*cos(3)*sin(x)