Solving an Equation by Search

We can perform algebraic operations by manipulating the list structure representation of an expression tree (taking apart the original tree and constructing a new tree). To solve an equation e for a desired variable v:

• Base cases:
  • If the lhs of e is v, return e.

  • If the rhs of e is v, rewrite e to switch the lhs and rhs of e, and return that.

  • If only an undesired variable or constant is on the right, ( rhs is not consp), fail by returning null.

• Recursive case: Rewrite e using an algebraic law, and try to solve that equation. Return the first result that is not null.

  Often, there are two possible ways to rewrite an equation; it is necessary to try both. Thus, the process will be a binary tree search analogous to the robot mouse searching for cheese.