CodePlexProject Hosting for Open Source Software

Let's say we're programming a binary search tree data structure. We represent binary search trees using values of the following discriminated union type:

Our union has three cases. Internal is used to represent nodes that have children. Its fields, in order, are its left child, its right child, and the value it contains. ValLeaf is used to represent nodes that do not have children, i.e. leaves. Finally, NilLeaf is a placeholder; if an internal node only has one child, NilLeaf is used as the value for its other child.

We construct binary search trees using the following insert function:

Let's say we want to generate an image of one of our binary search trees that displays the structure of our tree, as well as the values it contains and the depth of each node. To do this we must first define a diffInfo function, which provides some extra information about our BST type.

A diffInfo function has two parameters. The first is a value belonging to the inductively-defined datatype that we wish to view an image of.

The second is a context value. Context, which is passed to a node from its parent, is used to store information that can't be synthesized from the subtree that node is the root of. Context contains information regarding parents, ancestors, siblings, etc.

In our case, we're using the depth of a node as its context. A node's depth certainly can not be deduced by examining the subtree it is the root of, so depth is an appropriate choice for a context field.

A diffInfo function returns a value belonging to the DiffInfo<'Diffable, 'Context> record type, which contains the following fields:

nodeLabel:

The label that we want to give the current node in our diagram.

children:

A list of triples of the form (child, context, edgeLabel), where child is a 'Diffable value representing a node that current node has an outgoing edge to, context is the context we wish to pass to child, and edgeLabel is the label that we want to give the outgoing edge from the current node to child.

compFields:

Used to define equality between two 'Diffable values. Diffable considers two values equal if they belong to the same union case, have children lists of equal length, have compFields lists of equal length, and their corresponding elements of compFields are equal with respect to the = operator.

To use the above diffInfo function to generate graphs for BST values, we call the Diffable.diffBundle function.

The first argument to diffBundle is the diffInfo function we have defined, while the second argument is the value we wish to use as an empty context (i.e. the context to use for a node with no parents).

Now we are ready to generate some DOT graphs.

The above code will bind treeDOTGraph to DOT code for the tree resulting from inserting the values 3,4,-4, and 2 into an empty tree. listDOTGraph, on the other hand, will be bound to DOT code for a sequence of trees containing every intermediate tree during the insertion of the values.

It is the user's responsibility to convert the DOT code that Diffable generates into images. I recommend compiling the DOT code to SVG files using Graphviz, and then viewing the SVG files using Squiggle.

If both of the above tools are in your path, you can use the following function to automatically carry out the above process.

Here is the image that graphviz would generate from treeDOTGraph:

Here is the image that graphviz would generate from listDOTGraph:

Notice that certain nodes have been highlighted red in the above graph. These are nodes that either were not present in the previous tree in the list, or are somehow different from the corresponding node in the previous tree.

type BST = | Internal of BST*BST*int | ValLeaf of int | NilLeaf

Our union has three cases. Internal is used to represent nodes that have children. Its fields, in order, are its left child, its right child, and the value it contains. ValLeaf is used to represent nodes that do not have children, i.e. leaves. Finally, NilLeaf is a placeholder; if an internal node only has one child, NilLeaf is used as the value for its other child.

We construct binary search trees using the following insert function:

let rec insert (bst : BST) (n : int) = match bst with | Internal(leftChild,rightChild,value) -> if n <= value then Internal(insert leftChild n, rightChild, value) else Internal(leftChild, insert rightChild n, value) | ValLeaf(value) -> if n <= value then Internal(ValLeaf(n), NilLeaf, value) else Internal(NilLeaf, ValLeaf(n), value) | NilLeaf -> ValLeaf(n)

Let's say we want to generate an image of one of our binary search trees that displays the structure of our tree, as well as the values it contains and the depth of each node. To do this we must first define a diffInfo function, which provides some extra information about our BST type.

let diffInfo (bst : BST) (depth : int) = match bst with | Internal(leftChild, rightChild, value) -> { nodeLabel = value.ToString() + " (" + depth.ToString() + ")" children = [(leftChild, depth+1, "<="); (rightChild, depth+1, ">")] compFields = [value] } | ValLeaf(value) -> { nodeLabel = value.ToString() + " (" + depth.ToString() + ")" children = [] compFields = [value] } | NilLeaf -> { nodeLabel = "*" children = [] compFields = [] }

A diffInfo function has two parameters. The first is a value belonging to the inductively-defined datatype that we wish to view an image of.

The second is a context value. Context, which is passed to a node from its parent, is used to store information that can't be synthesized from the subtree that node is the root of. Context contains information regarding parents, ancestors, siblings, etc.

In our case, we're using the depth of a node as its context. A node's depth certainly can not be deduced by examining the subtree it is the root of, so depth is an appropriate choice for a context field.

A diffInfo function returns a value belonging to the DiffInfo<'Diffable, 'Context> record type, which contains the following fields:

nodeLabel:

The label that we want to give the current node in our diagram.

children:

A list of triples of the form (child, context, edgeLabel), where child is a 'Diffable value representing a node that current node has an outgoing edge to, context is the context we wish to pass to child, and edgeLabel is the label that we want to give the outgoing edge from the current node to child.

compFields:

Used to define equality between two 'Diffable values. Diffable considers two values equal if they belong to the same union case, have children lists of equal length, have compFields lists of equal length, and their corresponding elements of compFields are equal with respect to the = operator.

To use the above diffInfo function to generate graphs for BST values, we call the Diffable.diffBundle function.

let diffHelpers = Diffable.diffBundle diffInfo 0

The first argument to diffBundle is the diffInfo function we have defined, while the second argument is the value we wish to use as an empty context (i.e. the context to use for a node with no parents).

Now we are ready to generate some DOT graphs.

let EmptyBST = NilLeaf let values = [3;4;-4;2] let tree = List.fold insert EmptyBST values let treeDOTGraph (diffHelpers.treeDOTCode tree) let treeList = List.scan insert EmptyBST values let listDOTGraph (diffHelpers.treeListDOTCode treeList)

The above code will bind treeDOTGraph to DOT code for the tree resulting from inserting the values 3,4,-4, and 2 into an empty tree. listDOTGraph, on the other hand, will be bound to DOT code for a sequence of trees containing every intermediate tree during the insertion of the values.

It is the user's responsibility to convert the DOT code that Diffable generates into images. I recommend compiling the DOT code to SVG files using Graphviz, and then viewing the SVG files using Squiggle.

If both of the above tools are in your path, you can use the following function to automatically carry out the above process.

let viewDOTGraph (string : string) = let outStream = new StreamWriter("temp.dot") outStream.Write string outStream.Close() //Create a new process to build an svg based on the graphviz //file we have just written. let graphvizProc = System.Diagnostics.Process.Start( "dot", "-Tsvg -o \"temp.svg\" -Kdot \"temp.dot\"" ) graphvizProc.WaitForExit() //Display the svg in a viewer. let squiggleProc = System.Diagnostics.Process.Start( "batik-squiggle.jar", "temp.svg" ) ()

Here is the image that graphviz would generate from treeDOTGraph:

Here is the image that graphviz would generate from listDOTGraph:

Notice that certain nodes have been highlighted red in the above graph. These are nodes that either were not present in the previous tree in the list, or are somehow different from the corresponding node in the previous tree.

Last edited Jun 2, 2011 at 7:47 PM by kevinclancy, version 12