This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[Caml-list] Symbolic expression sub?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2001-10-26 (22:17) From: Berke Durak Subject: Re: [Caml-list] 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 ``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

```