Mathematica is an expensive commercial application sold as software for "interactive technical computing". In particular, the product centers around the Mathematica programming language which is a very powerful and dynamic language based upon term rewriting with excellent graphical capabilities and a wealth of useful functionality in its standard library. However, Microsoft's new F# programming language not only provides most of the useful functionality found in Mathematica but has many other benefits, not least that it is completely free!

We have previously compared F# and Mathematica in the context of 2D vector graphics. This post is the first in a series comparing these languages. Specifically, this post compares data structures. The F# programming language is designed for efficient compilation to native code whereas the Mathematica language is generally evaluated via term rewriting which is, essentially, a very inefficient form of interpretation. Consequently, F# code is typically 10-1,000× faster than Mathematica code unless computational burden can be shifted onto functions written in other languages (usually those in the vast standard library).

The latest Mathematica-related book, Mathematica Cookbook by Sal Mangano, contains many examples including a translation of Chris Okasaki's immutable red-black trees from Haskell to Mathematica augmented with a function to remove an element from a tree. Unfortunately, the new function written by Sal Mangano is incorrect and silently corrupts the shape of the tree. Thus, we shall focus on the subset of the code presented in Sal's book that is correct. This code may be written as follows in F#:

type color = Red | Black
type 'a t = Node of color * 'a * 'a t * 'a t | Leaf
let balance = function
| Black, z, Node (Red, y, Node (Red, x, a, b), c), d
| Black, z, Node (Red, x, a, Node (Red, y, b, c)), d
| Black, x, a, Node (Red, z, Node (Red, y, b, c), d)
| Black, x, a, Node (Red, y, b, Node (Red, z, c, d)) ->
Node (Red, y, Node (Black, x, a, b), Node (Black, z, c, d))
| x -> Node x
let insert x s =
let rec ins = function
| Leaf -> Node (Red, x, Leaf, Leaf)
| Node (color, y, a, b) as s ->
if x < y then balance (color, y, ins a, b)
elif x > y then balance (color, y, a, ins b) else s
match ins s with
| Node (Red, y, a, b) -> Node (Black, y, a, b)
| t -> t

The Mathematica code is significantly more complicated (714 vs 1514 bytes) for two main reasons:

- Mathematica has no types so it cannot express a type with an ordering, so a new rbTree data structure is created with an ordering and that must then be boxed and unboxed by hand.
- Mathematica prohibits top-level or-patterns so the same pattern is repeated four times in the balance function.

The simpler F# solution is also 20× faster at inserting 100k elements and 100× faster at computing the range of depths in the resulting tree.

In the next post, we'll start to compare the graphical capabilities of the two languages.