StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>First of all, I believe and if I may say so, you've done a very good job. I can suggest a couple of slight changes to your code:</p> <pre><code>abstract class Tree case class Node(value: Int, left: Tree, right: Tree) extends Tree case object Nil extends Tree </code></pre> <ol> <li>Tree doesn't need to be a case-class, besides using a case-class as non-leaf node is deprecated because of possible erroneous behaviour of automatically generated methods.</li> <li><code>Nil</code> is a singleton and best defined as a case-object instead of case-class. </li> <li><p>Additionally consider qualifying super class <code>Tree</code> with <code>sealed</code>. <code>sealed</code> tells compiler that the class can only be inherited from within the same source file. This lets compiler emit warnings whenever a following match expression is not exhaustive - in other words doesn't include all possible cases.</p> <p>sealed abstract class Tree </p></li> </ol> <p>The next couple of improvement could be made to the <code>sumTree</code>:</p> <pre><code>def sumTree(t: Tree) = { // create a helper function to extract Tree value val nodeValue: Tree=>Int = { case Node(v,_,_) => v case _ => 0 } // parametrise fold with Tree to aid type inference further down the line fold[Tree](t,Nil,(acc,l,r)=>Node(acc + nodeValue(l) + nodeValue(r) ,l,r)) } </code></pre> <p><code>nodeValue</code> helper function can also be defined as (the alternative notation I used above is possible because a sequence of cases in curly braces is treated as a function literal):</p> <pre><code>def nodeValue (t:Tree) = t match { case Node(v,_,_) => v case _ => 0 } </code></pre> <p>Next little improvement is parametrising <code>fold</code> method with <code>Tree</code> (<code>fold[Tree]</code>). Because Scala type inferer works through the expression sequentially left-to-right telling it early that we're going to deal with Tree's lets us omit type information when defining function literal which is passed to <code>fold</code> further on.</p> <p>So here is the full code including suggestions:</p> <pre><code>sealed abstract class Tree case class Node(value: Int, left: Tree, right: Tree) extends Tree case object Nil extends Tree object Tree { def fold[B](t: Tree, e: B, n: (Int, B, B) => B): B = t match { case Node(value, l, r) => n(value,fold(l,e,n),fold(r,e,n)) case _ => e } def sumTree(t: Tree) = { val nodeValue: Tree=>Int = { case Node(v,_,_) => v case _ => 0 } fold[Tree](t,Nil,(acc,l,r)=>Node(acc + nodeValue(l) + nodeValue(r) ,l,r)) } } </code></pre> <p>The recursion you came up with is the only possible direction that lets you traverse the tree and produce a modified copy of the immutable data structure. Any leaf nodes have to be created first before being added to the root, because individual nodes of the tree are immutable and all objects necessary to construct a node have to be known before the construction: leaf nodes need to be created before you can create root node.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload