A while back, I answered this question on Stack Overflow that involved deserializing a binary tree breadth-first using functional programming (the question itself isn't relevant). I'd like to make sure that I'm following functional programming principles and whether or not this is stack-safe. I'd also like to know if I can make my code more performant, less bloated, clearer, etc. If it helps, the question provides this link to explain the algorithm.
I first defined this rather simple tree type. Every child is an instance of Node, and the absence of a left or right child is denoted with Empty.
sealed trait Tree[+T] case class Node[+T](data: T, left: Tree[T], right: Tree[T]) extends Tree[T] case object Empty extends Tree[Nothing] And this trait that represents a function that takes the current list of serialized items (every item is an Option, with None meaning there is no child). It consumes one or more of these items and returns the rest, along with an Either, where a Right contains a fully built tree, and a Left contains another RecFun that will later consume more items to finish building the current tree.
trait RecFun[T] extends (List[Option[T]] => (List[Option[T]], Either[RecFun[T], Tree[T]])) The entry point is makeTree. First, a RecFun is made using createRec below, and the recursive helper inside makeTree starts processing the tree from there.
def makeTree[T](list: List[Option[T]]): Tree[T] = { def helper(f: RecFun[T], l: List[Option[T]]): Tree[T] = f(l) match { case (_, Right(tree)) => tree case (next, Left(f)) => helper(f, next) } list match { case Some(x) :: tail => helper(createRec(x), tail) case _ => Empty } } createRec takes the value of the root node of a subtree, and makes a RecFun to continue building it.
def createRec[T](data: T): RecFun[T] = { //No more children, so return a Right with a node whose children are Emptys case None :: Nil | Nil => (Nil, Right(Node(data, Empty, Empty))) //There's a left child, but no right child to be had, so return here too case Some(l) :: Nil => (Nil, Right(Node(data, Node(l, Empty, Empty), Empty))) case lo :: ro :: rest => //Possible left child :: possible right child :: rest of the items //Return the rest, and an Either depending on what lo and ro are (rest, (lo, ro) match { case (Some(l), Some(r)) => //Both children exist, so wait for both of them before building the tree Left(waitForChildren(data, createRec(l), createRec(r))) case (Some(l), None) => //Need to wait only for left child Left(waitForChild(Node(data, _, Empty), createRec(l))) case (None, Some(r)) => //Need to wait only for right child Left(waitForChild(Node(data, Empty, _), createRec(r))) //Both children don't exist, so build tree and return right now case (None, None) => Right(Node(data, Empty, Empty)) }) } This helper simply combines functions that build a tree where the root's value is known, but the children are not.
//Here, both the children need to be deserialized and have their own RecFuns def waitForChildren[T](data: T, leftF: RecFun[T], rightF: RecFun[T]): RecFun[T] = input => { //Attempt to deserialize the left child first val (next, res) = leftF(input) res match { //If it succeeded, use waitForChild to wait for the right child case Right(tree) => (next, Left(waitForChild(Node(data, tree, _), rightF))) //Otherwise, try to deserialize the right child, then run the new left RecFun leftF2 again case Left(leftF2) => { val (next2, res2) = rightF(next) //Return the rest of the list, along with the new RecFun (next2, Left(res2 match { //If the right child is constructed, wait for the left child to be constructed case Right(tree) => waitForChild(Node(data, _, tree), leftF2) //Otherwise, run leftF2 first, then the new right RecFun rightF2 case Left(rightF2) => waitForChildren(data, leftF2, rightF2) })) } } } Here, one child is known, and we're just waiting for another.
/** * @param ctor Function that takes a child and finishes building parent tree * @param f Function to construct child */ def waitForChild[T](ctor: Tree[T] => Node[T], f: RecFun[T]): RecFun[T] = input => { //Try deserializing the child based on the function f val (next, res) = f(input) (next, res match { //If it's fully built, build the parent tree by applying ctor to it case Right(tree) => Right(ctor(tree)) //Otherwise, wait for the new RecFun case Left(recFun) => Left(waitForChild(ctor, recFun)) }) } Here is the code I used for testing:
val tree = Node( 1, Node(2, Node(3, Node(5, Empty, Empty), Empty), Node(4, Empty, Empty)), Empty ) val tree2 = makeTree(List(Some(1), Some(2), None, Some(3), Some(4), Some(5), None)) println(tree2) assert(tree == tree2) Here is a Scastie.
