This article is intended to give a quick overview to symbolic algebra in F#. I didn't come up with this stuff myself -- it's covered in SICP, Expert F#, and a lot of other places. However, I think it's such an important and useful topic that I wanted to post a quick overview and remark on why it matters.

It's easy to do arithmetic in most high-level programming languages, including F#. By that, I first mean you can readily use F# as a calculator. For instance, in F# interactive you can run:

```
> 7 * (2 + 13);;
val it : int = 105
```

A high-level programming language like F# is better than most calculators because you can also name and save intermediate values in a computation:

```
let x = 2
let y = 13
7 * (x + y) // also returns 105
```

and you can also define functions to make computations repeatable:

```
let f x y =
7 * (x + y)
f 2 13 // returns 7 * (2 + 13) = 105
f 1 1 // returns 7 * (1 + 1) = 14
```

You might think of some of this as algebra, rather than arithmetic, because symbols like `x`

and `y`

are getting involved, and being treated like numbers.
I still call this arithmetic, because all that's going on here is carrying out a computation -- the letters are just placeholders.

By contrast, here's an honest-to-goodness algebra problem. Suppose I have another F# function `g`

defined like this:

```
let g x y =
7 * x + 7 * y
```

The question is, are the functions `f`

and `g`

equivalent? That is, does `f x y = g x y`

for every possible pair of `x`

and `y`

you could pick? If so, their behavior as functions is indistinguishable and we say they are equal.

We can't check every single possible pair of integers `x`

and `y`

to verify that `f x y`

and `g x y`

produce identical outputs. The mathematical way to get around this is to look at the *structure* of `f`

and `g`

and see if they are equivalent. They are defined by the respective expressions $7(x+y)$ and $7x + 7y$, so we're really asking to confirm the fact:
$$7(x+y) = 7x + 7y.$$
That's the real algebraic question. It turns out this is true, by invocation of one algebraic rule called the "distributive property". Out of the box, F# is not equipped to answer this question; it can't handle a comparison of two functions like `f = g`

. (I don't blame F# -- it turns out the question of whether two expressions are equal is undecidable. That is, for algebraic expressions built out of just a few of the usual operations, there's no algorithm that can always detect equivalence.)

The good news is that F# makes it easy to encode a key algebraic idea, namely that expressions like $7(x+y)$ or $7x+7y$ are collections of symbols combined in particular structures. Once these structures are programmed into F#, they can be analyzed and manipulated.

The key concept at play here is that of an **algebraic expression**. An algebraic expression isn't a computation, rather its a collection of symbols combined by some allowable operations. For instance, when I write "$2 + x$" is an expression that represents combining the symbols "2" and "$x$" via the operation of addition. You know how to interpret this as a computation, but resist the temptation to do so for now.

To give an unfamiliar example, "$(u \wedge v) \otimes w$" could represent an algebraic expression which first combines the symbols "$u$" and "$v$" using the "$\wedge$" operation and then combines that whole expression with another symbol "$w$" using the "$\otimes$" operation. Whether or not this can be interpreted as a computation, you can still see it has a structure.

Let's work in a familiar algebraic world where the symbols we combine are either integers or letters, and the operations that can combine them are addition, subtraction, negation, and multiplication. In this world, individual symbols like "17" or "$x$" are valid expressions, as are any combinations of these using the allowed operations. For instance, "$17 + x$" is a valid combination of $17$ and $x$ using the addition operation. You can build a bigger expression like "$y\cdot(17+x)$" by combining it with the single-symbol expression "$y$" using the operation of multiplication.

Now the task is to translate this idea to F#. We want to think of an integer like `17`

and a string like `"x"`

on the same footing, as two distinct but fungible cases of algebraic expressions. To do that, we can make our `Expression`

type a discriminated union, having a case for numbers and variables.

```
type Expression =
| Number of int
| Variable of string
```

With this definition, we could write down F# values like `Number(17)`

or `Variable("x")`

, which have more meaning than the `int`

value `17`

or the string value `"x"`

alone. The values `Number(17)`

and `Variable("x")`

have type `Expression`

, indicating that we're thinking of them as algebraic expressions, not just as an `int`

and a `string`

.

Numbers and variables are the simplest cases, but we also want to be able to combine them with operations to represent more complex expressions. Any two values of the `Expression`

type should be combinable as a sum, difference, or product. While expressions like "$x+17$", "$x-17$", and "$x\cdot 17$" combine "$x$" and "17" in different ways, we want to think of all of them as the same kind of data. That suggests we should add them as extra cases to our discriminated union. (Likewise for negation, which makes e.g. $-x$ from $x$.)

```
type Expression =
| Number of int
| Variable of string
| Negation of Expression
| Sum of Expression * Expression
| Difference of Expression * Expression
| Product of Expression * Expression
```

Returning to the examples from above,

`Product (Number 7,Sum (Variable "x",Variable "y"))`

represents the expression $7(x+y)$ while

`Sum (Product (Number 7,Variable "x"),Product (Number 7,Variable "y"))`

represents the expression $7x + 7y$. You can see that the first one is a product of 7 with a sum, while the second one is the sum of two products.

The important accomplishment here is replacing a computation with a data structure that *models* the computation. When we thought of $7(x+y)$ as a computation, all we could do was plug in numbers for $x$ and $y$. Now that we're thinking of it more abstractly, as an expression, there are many more possibilities.

First I want to show you that an `Expression`

is at least as good as the corresponding F# function. Namely, you can take an `Expression`

object, plug in numbers for the variables, and get a number as a result.

To demonstrate this, I'll use a slightly simplified version of the `Expression`

type, where there's only one variable: $x$. That means I can replace the `Variable`

case with a case `X`

-- no need to let any string be a variable.

```
type Expression =
| Number of int
| X
| Negation of Expression
| Sum of Expression * Expression
| Difference of Expression * Expression
| Product of Expression * Expression
// for example...
Product (Number 3, Sum (X, Number 5)) // represents 3*(x+5)
```

What we'll do first is write a function that takes an `expression`

as well as a given `float`

value to "plug-in" for $x$, does the arithmetic, and returns the `float`

result. For instance, if our expression represents $3(x+5)$ and we plug in 2.0 for $x$, we should get 21.0 back. With only one variable, this function will have a simple signature:

`val evaluate : Expression -> float -> float`

Once you've built a recursive data structure with an F# discriminated union, the rest of the work feels like magic. This is because you can reduce an infinite set of data (like every possible `Expression`

you could think of) to a handful of cases, some of which are dead simple.

For instance, if you plug any number in to the expression `X`

, you'll get that number back. That is, `evalute X 5.0`

should return 5.0. The other simple case is if your expression is just a number, like `Number(17)`

. It doesn't matter what value $x$ has, this expression always evaluates to 17. The only work to do for us is interpreting this 17 as a `float`

, since that's the return type for our function.

That handles two of our six cases for the ```
evaluate function:
```

```
let evaluate (exp:Expression) (input:float) =
match exp with
| X -> input // return the "plugged-in" value
| Number i -> float i // return number as a float
| ... // to be determined
```

The other cases are combinations of existing expressions. For each of these, we have to evaluate the underlying expressions and then put the resulting `float`

values together using the right operation. For instance
$$(3+x)\cdot(2+2)$$
is the product of two expressions. If we're evaluating this product with $x=7$, the first step is to evaluate both expressions in the product. The first one, $3+x$, evaluates to 10.0 and the second one, with no appearance of $x$, evaluates to 4.0. Assuming we know both of these results, the answer is `10.0 * 4.0`

or `40.0`

. That's just ordinary `float`

multiplication in F#.

In short, we handle the rest of the union cases by evaluating (recursively!) the expressions that make them up and then doing the appropriate `float`

arithmetic on the results.

```
let rec evaluate (exp:Expression) (input:float) =
match exp with
| X -> input
| Number i -> float i
| Negation e -> - evaluate e input
| Sum (e1, e2) -> (evaluate e1 input) + (evaluate e2 input)
| Difference (e1, e2) -> (evaluate e1 input) - (evaluate e2 input)
| Product (e1, e2) -> (evaluate e1 input) * (evaluate e2 input)
```

One line per case, that's all there is to it! This program treats the `Expression`

as a set of instructions and executes them.

I'll cover more things you can do with the `Expression`

type shortly. First, let me show you some syntactic sugar that makes it much nicer to work with symbolic expressions in F#.

As you may know, F# allows operator overloading, which allows you to use arithmetic operators on types you define. That's great for symbolic programming, because it will let us write something like `- X * (X + X)`

in place of the longer and harder to read `Negative(Product(X,Sum(X,X)))`

.

For each operator we want to use with the `Expression`

type, we need to add a static member function to the class. The implementations match the operators to the corresponding union cases.

```
type Expression =
| X
| Number of int
| Negation of Expression
| Sum of Expression * Expression
| Difference of Expression * Expression
| Product of Expression * Expression
static member (+) (e1,e2) = Sum(e1,e2)
static member (*) (e1,e2) = Product(e1,e2)
static member (-) (e1,e2) = Difference(e1,e2)
static member (~-) (e) = Negation e
let inline (~&) (i:int) = Number(i)
```

It's a matter of personal preference, but I also included a unary operator "`&`

" at the global level to package integers as `Number`

objects. That allows me to write `&3 + X`

rather than `Number(3) + X`

. I chose the ampersand because its an operator I'm not likely to miss, and it outranks all of the arithmetic operators in F#'s order of operations. That means integers get interpreted as `Number`

objects first in a line of code.

Operator overloading may not seem like a big deal, since it doesn't give us any functionality we didn't already have. However, it makes a big difference for productivity if you're working on an ambitious symbolic programming project. When you're debating between F# or Mathematica, it's nice that syntax doesn't have to be the deciding factor.

If you know a bit about programming languages, you may recognize the `Expression`

objects as **abstract syntax trees** for algebraic expressions. They are trees because an expression can be a combination of two sub-expressions, which can each in turn contain sub-expressions, and so on. If you draw out the nested structure of an expression, you see the characteristic branching. Here's $3\cdot(x+2)$ drawn as a tree:

Once you've got an abstract syntax tree, it's relatively easy to generate code in another programming language. For instance, you can generate a string of F# code corresponding to an expression. The way to do this is to traverse the tree, generate code for each sub-expression, and then concatenate the code snippets together.

```
let rec fsharp (exp:Expression) =
match exp with
| X -> "x"
| Number i -> string i
| Negation e -> sprintf "-(%s)" (fsharp e)
| Sum (e1, e2) -> sprintf "(%s)+(%s)" (fsharp e1) (fsharp e2)
| Difference (e1, e2) -> sprintf "(%s)-(%s)" (fsharp e1) (fsharp e2)
| Product (e1, e2) -> sprintf "(%s)*(%s)" (fsharp e1) (fsharp e2)
```

For an expression like `&3 * (X + &2)`

, the `fsharp`

function produces the string `"(3)*((x)+(2))"`

. There are some superfluous parentheses, but otherwise this looks good. It represents the analogous computation in F#.

As a more practical example, you can generate LaTeX code from an `Expression`

object. If you're not familiar with LaTeX, it's a markup language for typesetting math (among other things). You can look at my source code and see the implementation of a `latex`

function that generates LaTeX code. The result of `latex <| &3 * (X + &2)`

is the LaTeX code string:

`" 3 \cdot \left( x + 2 \right)"`

Which renders like this:
$$ 3 \cdot \left( x + 2 \right)$$
If you look at the source code, you'll see I added some logic to avoid unnecessary parentheses. This example doesn't do LaTeX justice, but if you expand the Expression type (Greek letter variables, quotients, named functions, roots, powers) you can get some spectacular results. In this file you can see an enhanced `Expression`

type and `latex`

function that turns this F# code

```
let a,b,c = Variable "a", Variable "b", Variable "c"
(-b + sqrt(b**2 - &4*a*c)) / (&2 * a)
|> latex
```

into LaTeX producing the following: $$\frac{ - b + \sqrt{ b ^{ 2 } - 4 \cdot a \cdot c }}{ 2 \cdot a }.$$

Arguably the most important use of `Expression`

objects is transforming them to create new expressions. As I argued before, this is really how you know you're "doing algebra" in F#.

This code, for instance, traverses an `Expression`

and applies the distributive property wherever possible. That is, it replaces any expressions of the form $a(b+c)$ with $ab + ac$ and any of the form $(a+b)c$ with $ac + bc$.

```
let rec distribute (exp:Expression) =
match exp with
// two cases where distributive property applies
| Product (Sum(e1,e2), e3) -> // case (a+b)c
Sum (distribute (Product (e1,e3)), distribute (Product (e2,e3)))
| Product (e1, Sum(e2,e3)) -> // case a(b+c)
Sum (distribute (Product(e1,e2)), distribute (Product (e1,e3)))
// if distributive property doesn't apply, keep looking recursively
| Product (e1,e2) -> Product (distribute e1, distribute e2)
| Negation e -> Negation (distribute e)
| Sum (e1,e2) -> Sum (distribute e1, distribute e2)
| Difference (e1,e2) -> Difference (distribute e1, distribute e2)
| _ -> exp
```

Thanks to F#'s powerful pattern matching, it's easy to recognize the product of a sum and see that the distributive property applies.

Another algebraic manipulation you can do is plugging one expression into another to get a new expression. By that I mean looking for every instance of a variable, $x$, in one expression and putting another expression in its place. For instance, if you start with $x^2 + 3$ and plug $x+2$ in for $x$, you get $(x+2)*(x+2) + 3$. This is the equivalent of composing the functions $f(x) = x+2$ and $g(x) = x^2+3$ to get a new function $g(f(x))$.

Here's a `compose`

function that plugs a first expression into a second expression at every occurence of $x$:

```
let rec compose (inner:Expression) (outer:Expression) =
match outer with
| X -> inner
| Number i -> Number i
| Negation e -> Negation(compose inner e)
| Sum(e1,e2) -> Sum(compose inner e1, compose inner e2)
| Difference(e1,e2) -> Difference(compose inner e1, compose inner e2)
| Product(e1,e2) -> Product(compose inner e1, compose inner e2)
```

It works a lot like `evaluate`

except that instead of plugging in a `float`

value at every occurence of $x$, you plug-in another expression. Putting `distribute`

and `compose`

together, you can do the following:

```
compose (X + &2) (X * X + &3)
|> distribute
|> latex;;
```

which gets you the correct, expanded result: $ x \cdot x + x \cdot 2 + 2 \cdot x + 2 \cdot 2 + 3 .$ If you want a challenge, try writing a function that simplifies expressions by "combining like terms". You could simplify $2\cdot 2 + 3$ to $7$ and $x\cdot 2 + 2 \cdot x$ to $4\cdot x$.

A final important example of manipulating symbolic expressions comes from calculus. The **derivative** of a function $f(x)$ is another function which, roughly speaking, tells us the instantaneous rate of change in $f$ with respect to $x$ at any point $x$. The derivative of $f(x)$ with respect to $x$ is written $f'(x)$, $\frac{df}{dx}$, or $\frac{d}{dx}f$. The latter notation is nice because it shows that the "derivative with respect to $x$" is a machine, written $\frac{d}{dx}$, that acts on a function producing a new function.

Much of the work of taking derivatives is applying rules to transform the expression for $f(x)$ into another expression for $f'(x)$. The simplest derivative rule is that if $f(x) = c$, where $c$ is any number, then the derivative is $f'(x) = 0$ (constant functions have zero rate of change). Another simple rule is that if $f(x) = x$ then $f'(x) = 1$.

The rest of the rules tell you how to take derivatives of more complicated expressions, for example if $f(x)$ is a sum of two expressions $g(x) + h(x)$ with known derivatives, then $f'(x) = g'(x) + h'(x)$. If $f(x)$ is a product, like $f(x) = g(x)h(x)$, there's also a formula, but its a bit more complicated: $f'(x) = g'(x)h(x) + h'(x)g(x)$.

The point is, as you probably expected, these rules can be encoded in F# for the `Expression`

type. The following `derivative`

function takes an expression and returns an expression for its derivative with respect to $x$.

```
let rec derivative (exp:Expression) =
match exp with
| X -> Number 1
| Number _ -> Number 0
| Negation e -> Negation (derivative e)
| Sum (e1,e2) -> Sum (derivative e1, derivative e2)
| Difference (e1,e2) -> Difference (derivative e1, derivative e2)
| Product (e1,e2) ->
Sum (Product (e1,derivative e2), Product (e2, derivative e1))
```

For instance, `derivative (X*X)`

returns

`Sum (Product (X,Number 1),Product (X,Number 1))`

or $ x \cdot 1 + x \cdot 1 $. If your calculus skills are fresh, you'll recognize that $2x$ is the correct answer and that this result is equivalent.

There are countless other ways to extend and use the `Expression`

type, and I can't mention them all here. The point is that, in F#, you can accomplish some sophisticated algebraic tasks with only a few lines of code. I'll concede that Wolfram Alpha is a free and more powerful alternative to what we've built here, but it can't do everything. If you're working in a specialized mathematical domain, it is useful to know how to build a small, fit-for-purpose symbolic algebra library. I think the examples above make a good template for such a project.