Treehugger.scala inspired by treehugger.js

1 Tree.scala (first shot)

package net.danieldietrich.scala.treehugger

sealed abstract class Tree

case class Node(id: Symbol)(children: Tree*) extends Tree

case class Leaf(id: Symbol)(value: String) extends Tree

object Example {

  // 2 + 3 * 1

  def syntax() = {

    Node('Add)(
      Leaf('Num)("2"),
      Node('Mul)(
        Leaf('Num)("3"),
        Leaf('Num)("1")
      )
    )

  }

  def niceSyntax() = {

    val Add = Node('Add)_
    val Mul = Node('Mul)_
    val Num = Leaf('Num)_

    Add(Num("2"), Mul(Num("3"), Num("1")))

  }

  def openIssues() = {

    // compilation error: value children is not a member of net.danieldietrich.scala.treehugger.Node
    Node('Test)().children

    // compilation error: value value is not a member of net.danieldietrich.scala.treehugger.Leaf
    Leaf('Test)("test").value

  }

}

2 Tree.scala (member access)

package net.danieldietrich.scala.treehugger

// 1) removed curried constructors of case classes
// 2) added curried apply methods to companion objects
// 3) compilation workaround: changed case class constructors by adding implicit dummy args

sealed abstract class Tree

case class Node(id: Symbol, children: Seq[Tree])(implicit dummy: Manifest[Node]) extends Tree

object Node {
  def apply(id: Symbol)(children: Tree*) = new Node(id, children.toSeq)
}

case class Leaf(id: Symbol, value: String)(implicit dummy: Manifest[Leaf]) extends Tree

object Leaf {
  def apply(id: Symbol)(value: String) = new Leaf(id, value)
}

3 Tree.scala (pretty printable)

package net.danieldietrich.scala.treehugger

/*
 * Added custom toString() implementation.
 *
 * Example:
 *
 *     val Add = Node('Add)_
 *     val Mul = Node('Mul)_
 *     val Num = Leaf('Num)_
 *
 *     // 2 + 3 * 1
 *     val ast = Add(Num("2"), Mul(Num("3"), Num("1")))
 *
 *     println(ast)
 *
 * Output:
 *
 *     Add(
 *       Num(2),
 *       Mul(
 *         Num(3),
 *         Num(1)
 *       )
 *     )
 *
 */
sealed abstract class Tree {
  protected val INDENT = "  "
  override def toString() = toString(0)
  private[treehugger] def toString(depth: Int): String
}

case class Node(id: Symbol, children: Seq[Tree])(implicit dummy: Manifest[Node]) extends Tree {
  private[treehugger] def toString(depth: Int) = {
    val indent = INDENT * depth
    indent + id.name +"(\n"+ children.map(_.toString(depth + 1)).reduce(_ +",\n"+ _ +"\n") + indent +")"
  }
}

object Node {
  def apply(id: Symbol)(children: Tree*) = new Node(id, children.toSeq)
}

case class Leaf(id: Symbol, value: String)(implicit dummy: Manifest[Leaf]) extends Tree {
  private[treehugger] def toString(depth: Int) = {
    val indent = INDENT * depth
    indent + id.name +"("+ value +")"
  }
}

object Leaf {
  def apply(id: Symbol)(value: String) = new Leaf(id, value)
}

4 Traverse.scala (simple demo)

package net.danieldietrich.scala.treehugger

object Traverse {

  // TODO(@@dd): implement collectTopDown, traverseTopDown, ...
  
  // simple demo
  def traverse(tree: Tree)(f: Tree => Unit) {
    tree match {
      case node: Node => f(node); node.children.foreach(traverse(_)(f))
      case leaf: Leaf => f(leaf)
    }
  }

  // example
  def main(args: Array[String]) = {

    val Add = Node('Add)_
    val Mul = Node('Mul)_
    val Num = Leaf('Num)_

    // 2 + 3 * 1
    val ast = Add(Num("2"), Mul(Num("3"), Num("1")))

    val t = traverse(ast)_

    t(_ match {
      case Node(id, _) => println("Node("+ id.name +")")
      case Leaf(id, value) => println("Leaf("+ id.name +") = "+ value)
    })

  }

}

5 Constructing Trees with automatic parent relation

package net.danieldietrich.scala.example.tree

import scala.collection.mutable.ListBuffer

sealed abstract class Tree

case class Node(id: Symbol, parent: Option[Node], children: ListBuffer[Tree] = ListBuffer()) extends Tree

case class Leaf(id: Symbol, parent: Option[Node], value: String) extends Tree

/*
 * Constructing Trees with 'automatic' parent relation
 */
object Tree {

  def Node(id: Symbol, initializer: (Node) => Unit)(implicit parent: Node = null) = {
    val node = new Node(id, if (parent == null) None else Some(parent))
    if (parent != null) parent.children += node
    initializer.apply(node)
    node
  }

  def Leaf(id: Symbol, value: String)(implicit parent: Node = null) = {
    val leaf = new Leaf(id, (if (parent == null) None else Some(parent)), value)
    if (parent != null) parent.children += leaf
    leaf
  }

  // Example
  def main(args: Array[String]) = {

    // 2 + 3 * 1
    val ast = Node('Add, implicit p => {
      Leaf('Num, "1")
      Node('Mul, implicit p => {
        Leaf('Num, "3")
        Leaf('Num, "2")
      })
    })

    println(ast)
    
  }

}

6 Mutable Trees with parent relation

package net.danieldietrich.scala.mutable.treehugger

import scala.collection.mutable.ListBuffer

sealed abstract case class Tree(var parent: Option[Node]) {
  def isLeaf() : Boolean
  def isRoot() = parent match {
    case Some(_) => false
    case None => true
  }
  def root() : Tree = parent match {
    case Some(p) => p.root()
    case None => this
  }
  protected val INDENT = "  "
  override def toString() = toString(0)
  private[treehugger] def toString(depth: Int): String
}

case class Node(id: Symbol, children: ListBuffer[Tree] = ListBuffer()) extends Tree(None) {
  def isLeaf() = false
  def add(child: Tree) = {
    children += child
    child.parent = Some(this)
    this
  }
  private[treehugger] def toString(depth: Int) = {
    val indent = INDENT * depth
    indent + id.name +"(\n"+ children.map(_.toString(depth + 1)).reduce(_ +",\n"+ _ +"\n") + indent +")"
  }
}

object Node {
  def apply(id: Symbol)(children: Tree*) = {
    val node = new Node(id)
    children.foreach(node.add(_))
    node
  }
}

case class Leaf(id: Symbol, value: String)(implicit dummy: Manifest[Leaf]) extends Tree(None) {
  def isLeaf() = true
  private[treehugger] def toString(depth: Int) = {
    val indent = INDENT * depth
    indent + id.name +"("+ value +")"
  }
}

object Leaf {
  def apply(id: Symbol)(value: String) = new Leaf(id, value)
}

/*
 * Mutable Trees with parent relation
 */
object Tree {
  
  def main(args: Array[String]) = {

    val Add = Node('Add)_
    val Mul = Node('Mul)_
    val Num = Leaf('Num)_

    // 2 + 3 * 1
    val ast = Add(Num("2"), Mul(Num("3"), Num("1")))

    println(ast)
    
    ast.add(Num("4"))
    
    println(ast)

  }
  
}