AssignmentFeedback.md

layout	title
page	Scala Style Guide

On this page we will periodically publish feedback specific to individual assignments. For feedback which applies to coding style in general, visit the Scala Style Guide wiki page.

Week 4: Types and Pattern Matching (Huffman Coding)

The following table indicates how often each of the issues occurred during this assignment (the Scala Style Guide describes the first 12 issues).

#1 (casts)	6%
#2 (indent)	15%
#3 (line length)	52%
#4 (use locals)	40%
#5 (good names)	26%
#6 (common subexpr)	2%
#7 (copy-paste)	0%
#8 (semicolons)	23%
#9 (print stmts)	6%
#10 (return)	0%
#11 (vars)	4%
#12 (redundant if)	5%
#4.1 (weight / chars)	43%
#4.2 (::: vs ++)	100%
#4.3 (list matching)	51%
#4.4 (sort too often)	18%
#4.5 (type patterns)	18%

#4.1 Unnecessary recursive Computation for "weight" and / or "chars"

Every code tree (leaf or fork) contains the full weight and list of characters. Therefore, implementing def weight and def chars does not require a recursive computation.

#4.2 List Concatenation with :::

Lists can be concatenated with either :::, as most solutions do, or using the ++ operator. The latter has the advantage of being applicable to other sequence types (and also exists for other collection types), while ::: only exists for lists.

#4.3 Using "isEmpty", "head" and "tail" instead of Pattern Matching

Some submissions make extensive use of isEmpty, head and tail instead of using pattern matches on lists. The corresponding code is longer and less elegant, for example

def count(ch: Char, counter: Int, list: List[Char]): Int = {
  if (list.isEmpty || !list.contains(ch)) counter
  else if (list.head.equals(ch)) count(ch, counter + 1, list.tail)
  else count(ch, counter, list.tail)
}

is more clearly written as follows:

def count(ch: Char, counter: Int, list: List[Char]): Int = list match {
  case Nil => counter
  case x :: xs =>
    val newCounter = if (x == ch) counter + 1 else counter
    count(ch, newCounter, xs)
}

Note that the call to list.contains(ch) was removed: it was counter-productive: the entire list is traversed at every iteration, therefore the first implementation has complexity O(n^2). The second implementation has complexity O(n).

Note that the counter parameter is not required, the method can be written as follows (although it won't be tail-recursive anymore):

def count(ch: Char, list: List[Char]): Int = list match {
  case Nil => 0
  case x :: xs =>
    val increment = if (x == ch) 1 else 0
    increment + count(ch, xs)
}

#4.4 Calling "sort" in a recursive Function

To sort the list of frequencies, some solutions of makeOrderedLeafList call sort in every iteration - this is unnecessary, calling it once on the entire list would be enough. To avoid the problem, a helper method might be required. Example:

def makeOrderedLeafList(freqs: List[(Char, Int)]): List[Leaf] =
  freqs.sortWith((a,b) => a._2 <= b._2) match {
    [...] makeOrderedLeafList(someTail) [...]
  }

#4.5 Avoid Type Patterns

There is one form of pattern matching - type patterns - which should be avoided in general. A type pattern has the following form:

expr match {
  case x: T => ...
}

A type pattern is equivalent to a type test and a cast:

if (expr.isInstanceOf[T]) {
  val x = expr.asInstanceOf[T]
  ...
}

In all cases where we found type patterns in the submissions, they should have been replaced by ordinary pattern matches. In an ordinary pattern, you can at the same time match on the type of a value and define value bindings for its fields. For example, the following implementation

def weight(tree: CodeTree): Int = tree match {
  case x: Fork => x.weight
  case x: Leaf => x.weight
}

is better written as follows:

def weight(tree: CodeTree): Int = tree match {
  case Fork(_, _, _, w) => w
  case Leaf(_, w)       => w
}

Week 3: Object-Oriented Sets (TweetSet)

The following table indicates how often each of the issues occurred during this assignment (the Scala Style Guide describes the first 12 issues).

#1 (casts)	1 %
#2 (indent)	12 %
#3 (line length)	37 %
#4 (use locals)	0 %
#5 (good names)	13 %
#6 (common subexpr)	59 %
#7 (copy-paste)	54 %
#8 (semicolons)	20 %
#9 (print stmts)	1 %
#10 (return)	0 %
#11 (vars)	4 %
#12 (redundant if)	0 %
#3.1 (union)	52 %

#3.1 Union should be implemented using dynamic method invocation

Instead of implementing union in the base class TweetSet and testing for isEmpty, a more elegant solution is to keep union abstract in the base class and provide an implementation in each subclass:

abstract class TweetSet {
  def union(that: TweetSet): TweetSet
}
class Empty extends TweetSet {
  def union(that: TweetSet): TweetSet = ???
}
class NonEmpty extends TweetSet {
  def union(that: TweetSet): TweetSet = ???
}