F# Symbolic Math, Part 1

Introduction

Back in 2009 I attended a weekend course on F# put on by a local user group, and though I was intrigued by certain powerful features of the language, I was never able to put any of it to good use. Every time I tried to code anything in F#, even the most trivial ideas, I would quickly become frustrated with what seemed like flaws in the language and eventually lost interest.

Why can't the type inference system actually infer my types, I would think? Why can't numeric values implicitly convert like in all other languages? Why don't .NET methods support partial application and piping like native F# functions? And what's the deal with these "discriminated unions" -- isn't that just a fancy name for a type hierarchy that I can't extend? It all felt kind of half-baked to me.

Recently I decided to try solving some of the Project Euler problems, and having had my interest in the language rekindled by the Try F# site, I decided I would try to use it for this. After three relatively sleepless nights, I have found solving problems using functional techniques to be extremely fun and addicting, and in some ways it feels more "natural" than procedural methods. The more I learn about F# (and functional programming in general) the more I realize that the "flaws" in the language were not actually flaws - they're the way things have to work in order to support its powerful features!

So a few days ago I decided that I wanted to try and leverage the power of F# to write a little library for processing mathematical expressions. Discriminated unions would make it easy to represent my expression trees, and pattern matching would (hopefully) allow straight-forward implementations of things like pretty-printing, simplification, taking derivatives, etc. Happily, the language has exceeded all my expectations in this regard, and it was exceedingly easy (and fun!) to implement what I've implemented so far. In this post I'll share some of what I've been able to achieve.

Expressions

The first thing I did was define a discriminated union to represent my expression nodes, which looks like the following:

type Expr =  
    | Con of int
    | Var of string
    | Add of Expr * Expr
    | Sub of Expr * Expr
    | Mult of Expr * Expr
    | Div of Expr * Expr
    | Power of Expr * Expr
    | Neg of Expr

Now to construct the expression x * 3 + 4, I can type Add(Mult (Var "x", Con 3), Con 4). Fairly straightforward, but somewhat verbose. As Shenia Twain would say, that don't impress me much. I wanted to see if I could clean things up a bit to make these expressions easier to write.

So the next thing I did was modify my Expr type to overload the arithmetic operators:

type Expr with  
    static member (+) (x, y) = Add (x, y)
    static member (-) (x, y)  = Sub (x, y)
    static member (*) (x, y)  = Mult (x, y)
    static member (/) (x, y)  = Div (x, y)
    static member Pow (x, y) = Power (x, y)
    static member (~-) x = Neg x
    static member (~+) x = x

Notice I had to add a member Pow in order to overload the ** operator. For some reason, including a ** member directly on the type does not work for overloading that operator (it's also the reason I named my union case Power rather than Pow as I wanted - to avoid a naming conflict). Also notice that I have prefixed the unary operators with a ~ to indicate to the compiler that I am overloading the unary as oppose to the binary forms of the operators.

This allows me to do the following (if you're unfamiliar with F# Interactive, > is the prompt and ;; is what causes it to evaluate the expression. The subsequent line shows the result of the evaluation along with its type):

> Var "x" * Con 3 + Con 4;;
val it : Expr = Add (Mult (Var "x",Con 3),Con 4)  

That's somewhat of an improvement, but what if I wanted to be able to just say x * 3 + 4 and have it automatically convert to the corresponding expression tree? In order for this to work, I first had to define additional operators dealing with expressions and integers, as follows:

type Expr with  
    static member (+) (x, y) = Add (x, Con y)
    static member (+) (x, y) = Add (Con x, y)
    static member (-) (x, y) = Sub (x, Con y)
    static member (-) (x, y) = Sub (Con x, y)
    static member (*) (x, y) = Mult (x, Con y)
    static member (*) (x, y) = Mult (Con x, y)
    static member (/) (x, y) = Div (x, Con y)
    static member (/) (x, y) = Div (Con x, y)
    static member Pow (x, y) = Exp (x, Con y)
    static member Pow (x, y) = Exp (Con x, y)

Note how I still don't need to place any type annotations on the x and y parameters -- the compiler can infer their types from how they are used within the case constructors.

Another thing I needed to do was create a few bindings for my variable names:

let x = Var "x"  
let y = Var "y"  
let z = Var "z"  

This now allows me to enter the expression using its natural representation:

> x * 3 + 4;;
val it : Expr = Add (Mult (Var "x",Con 3),Con 4)  

Application

So now that I have these wonderful self-parsing expression trees, what can I do with them? In the introduction I mentioned some possibilities, such as taking derivatives. As a quick example, I implemented the following recursive function that uses pattern matching to implement basic differentiation rules (notice there's no "visitor pattern" weirdness!):

let rec deriv var expr =  
    let d = deriv var
    match expr with
    | Var var -> Con 1                             // Identity Rule
    | Con x -> Con 0                               // Constant Rule
    | Mult (Con x, y) | Mult (y, Con x) -> Con x   // Constant Factor Rule
    | Add (x, y) -> d x + d y                      // Sum Rule
    | Sub (x, y) -> d x - d y                      // Difference Rule
    | Mult (x, y) -> d x * y + x * d y             // Product Rule
    | Div (x, y) -> (d x * y - x * d y) / y ** 2   // Quotient Rule
    | Power (var, Con x) -> x * var ** (x - 1)     // Elementary Power Rule
    | _ -> failwith "Sorry, don't know how to differentiate that!"

The ability to nest patterns, as exemplified by the "constant factor" and "power" rules above, is one thing that makes F# pattern matching extremely powerful. Note how I'm matching the general case of multiplication (product rule) and the case of multiplication by a constant (constant factor rule) separately. Although this is not necessary to get a correct result, it does result in a simplified expression for the constant factor case. That is another nice feature of pattern matching - you can handle certain cases specially while falling through to a more general rule.

Now let's verify that the derivative of x3 + x is 3x2 + 1:

> deriv x (x ** 3 + x);;
val it : Expr = Add (Mult (Con 3,Power (Var "x",Con 2)),Con 1)  

The output is not easy to read, since I haven't added pretty-printing yet, but the result is correct.

There are many more possibilities, but I wanted to get this post up before it expands to any longer than it already is, so I'll save those for future posts. In the mean time, I've posted the source for this post to the Try F# site so that you can test it out interactively and also created a Github repository in which I plan to develop this idea further.

Part 2

Luke Sandell

Read more posts by this author.

comments powered by Disqus