[Camllist] Symbolic expression sub?

Ping Hu
 Berke Durak
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20011026 (22:17) 
From:  Berke Durak <berke@a...> 
Subject:  Re: [Camllist] Symbolic expression sub? 
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 ``pigeonhole'' (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/camlbugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail camllistrequest@inria.fr Archives: http://caml.inria.fr