Tree Structures

Data Structure: formula trees

Any evolutionary algorithm evolves a set of individuals, in the case of Genetic Programming we evolve a set of formulas. One of the most common approaches is to represent a formula as a tree, with the leafs representing mathematical constants or variables from external data, and nodes to represent binary operations between these leafs. Here is a visual example:

Scala has simple and flexible means for creating this type of data structure:

abstract class Tree

case class Node(left: Tree, right: Tree, op: (Double, Double) => Double) extends Tree

case class Leaf(x: Double, feature: String) extends Tree

This works in a very similar way to overloading a class in Java with multiple constructors. Scala can also define functions in terms of multiple cases for a single datatype:

def printFunction(t: Tree): String = t match {

case Node(l, r, op) => printFunction(l) + opToString(op) + printFunction(r)

case Leaf(x, f) => x.toString + ":" + f.toString }

This syntax makes writing recursive functions easier with very concise looking results.