* Re: [Caml-list] Symbolic expression sub?
2001-10-22 15:36 [Caml-list] Symbolic expression sub? Ping Hu
@ 2001-10-26 22:11 ` Berke Durak
0 siblings, 0 replies; 2+ messages in thread
From: Berke Durak @ 2001-10-26 22:11 UTC (permalink / raw)
To: Ping Hu; +Cc: caml-list
On Mon, Oct 22, 2001 at 11:36:45AM -0400, Ping Hu wrote:
> Just wondering if someone has some smart enough approach in Caml (or
> C/C++) to compute the difference between two symbolic expressions
> described below,
>
> term: x, xy, 3x, 3xyz, 23, ...
> op: +, -
> expr: term | expr op expr
>
> how about (expr1 - expr2) ?
You can represent an arbitrary linear combination of terms
using a Map from monomials to scalars.
As monomials, you can take strings "x","xy" ("" for constant...).
However, you must be sure that the letters in the string are sorted
(assuming xy=yz), which can be done, for example, by ``pigeon-hole''
(aka histogram) sorting since you most likely will have a small,
bounded number of letters.
Converting an expression represented by a tree to such a monomial is
straightforward if you only have addition and substraction. Converting
the monomial back to a tree is also easy ; further, as a side effect
of the inner workings of the module Map, your terms will be nicely sorted.
If you take care to actually remove terms with null coefficients from the
map, you can use Map.equal to compare two terms.
Take
type monomial = string
and scalar = int
and assume the function
val canonize_monomial : monomial -> monomial
that ``sorts the letters of a string'' is given (i.e. "xzyt" becomes "xyzt").
Then the following code, although not optimal, seems to work :
(* *)
type monomial = string
and scalar = int
let canonize_monomial x = x (* dummy function *)
module P = Map.Make(struct type t = monomial let compare = compare end)
type expr = Zero
| Term of scalar * monomial
| Difference of expr * expr
| Sum of expr * expr
let expr_of_map m =
P.fold (fun x k e ->
if k = 0 then
e
else
match e with
Zero -> Term(k,x)
| _ -> Sum(Term(k,x),e)) m Zero
let rec map_of_expr =
let binop f e1 e2 =
let m1 = map_of_expr e1
and m2 = map_of_expr e2
in
P.fold
(fun x k m ->
P.add x (f (try P.find x m with Not_found -> 0) k) m)
m1
m2
in
function
Term(k,x) -> P.add (canonize_monomial x) k P.empty
| Zero -> P.empty
| Difference(e1,e2) -> binop (-) e1 e2
| Sum(e1,e2) -> binop (+) e1 e2
--
Berke
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
^ permalink raw reply [flat|nested] 2+ messages in thread