Mathematica Algebraic Data Types

I have been doing lots of Mathematica lately, but because of my statically structured inflexible mind, I needed ADTs and static typing even in Mathematica. To check if this is possible, let’s test a very simple algorithm implementation. The problem is to list all paths of a rooted tree starting at the root and ending with the leafs. This can be solved with a basic depth first traversal implementation, so I started by modeling the solution in Haskell.

Our three basic ADTs are:

  • Vertex, to model the graph nodes
  • Forest to model leafs and branches
  • Graph to model the graph itself

Here is the Haskell implementation, straight forward as always:

data Vertex a = Vertex a
data Forest a = Leaf (Vertex a) | Branch (Vertex a) [Forest a]
data Graph a = Graph [ ( Vertex a, [Vertex a] ) ]

On the Mathematica side, a Vertex can be modeled as:

VertexT will hold as the Vertex Haskell equivalent, but will never get defined in Mathematica terms, this is basically a hack to define an ADT with the name VertexT, but it turns out to be very useful. For the definition of the Graph type in Mathematica, VertexT can be used in the constructor definition as:

So that defines a list of tuples, with the first element being a vertex and the second is a list of vertices.

Both Leaf and Branch can be implemented the same way:

The Leaf:

And the Branch:

The Haskell branch function is:

branch :: Vertex a -> [Forest a] -> Forest a
branch v [] = Leaf v
branch v fs = Branch v fs

Yes, Haskell shines so far, but let’s go on with our implementation. We need a function to identify the successor of a vertex, as in Haskell:

scc :: Eq a => Graph a -> Vertex a -> [Vertex a]
scc (Graph rep) v =
  case ( map(snd) . filter ((v==) . fst)  $ rep ) of
    []     -> []
    (x:_) -> x

While in Mathematica:

Not too bad, our hack is starting to pay off, it’s time to walk the tree:

dft :: Eq a => Graph a -> Vertex a -> Forest a
dft g v = branch v . map (dft g) $ scc g v

And in Mathematica, it is strikingly similar:

We will need a concatMap version for Mathematica later on, let’s implement one:

We can know build the tree chains or paths:

chains :: Forest a -> [[Vertex a]]
chains (Leaf v) = [[v]]
chains (Branch v fs) = concatMap (map (v:) . chains $) fs 

With a similar Mathematica implementation:

Testing the Haskell code with a simple example:

*Main> let g = Graph [ (Vertex 'r', [Vertex 'a', Vertex 'b', Vertex 'c']) ]
*Main> let b = dft g (Vertex 'r')
*Main> chains b
[[Vertex 'r',Vertex 'a'],[Vertex 'r',Vertex 'b'],[Vertex 'r',Vertex 'c']]

Before we can work with the Mathematica code, we need a few functions to convert our graph model to Mathematica’s own model:

And a nice rendering function:

So, let’s create an instance of our graph model:

And plot it:

Let’s see if the whole thing works:

How about a nice plot of the chains:

Now we have at least basic ADT support in Mathematica. 🙂

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s