Skip to content

Instantly share code, notes, and snippets.

@adilakhter
Created October 13, 2020 10:00
Embed
What would you like to do?
InvertTree.sc
sealed trait Tree[+A]
case object EmptyTree extends Tree[Nothing] {
override def toString = "nil"
}
case class Node[A] (l: Tree[A], v: A, r: Tree[A]) extends Tree[A]
object Tree {
def empty[A]: Tree[A] = EmptyTree
def node[A](value: A, left: Tree[A] = empty, right: Tree[A] = empty): Tree[A]
= Node(left, value, right)
}
import Tree._
val t1 = node(4,
node(2
, node(1)
, node(3)
) ,
node(7
, node(6)
, node(9)
)
)
pprint.log(t1)
pprint.pprintln(t1)
def treeFold[A, B](t: Tree[A], z: B) (f: (B, A, B) => B) : B = {
// alias
def treeFoldAux(t: Tree[A])= treeFold(t, z)(f)
t match {
case EmptyTree => z
case Node(l, a, r) => f (treeFoldAux(l), a, treeFoldAux(r))
}
}
def size[T] (tree: Tree[T]) =
treeFold(tree, 0: Int){(l,x,r) => l + r + 1}
pprint.log(size(t1))
val t1String =
treeFold(t1, Tree.empty[String]) { (l, a, r)
=> Tree.node(a.toString, l, r)
}
pprint.log(t1String)
// map
def map[A, B] (tree: Tree[A]) (f: A => B) : Tree[B] =
treeFold(tree, Tree.empty[B]) { (l , a, r ) => Tree.node(f(a), l, r) }
pprint.log(map(t1) ((a: Int) => a * 1000) )
def invertTree[A](tree: Tree[A]): Tree[A] =
treeFold(tree, Tree.empty[A]) {(left, a, right) => Tree.node(a, right, left)}
pprint.log(invertTree(t1))
pprint.log(invertTree(t1))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment