Rubric for Problem Set 2

A rubric in this context is an explanation of how a problem set was graded. The solution may be found on the course website.

Advisory:

Even when a function has type parameters in its header, it is usually not necessary to include values for them in a function call. That is, you can write importantFunc(...) instead of importantFunc[...](...). The compiler will infer the missing types from context. The exceptions are corner cases like List(). Sometimes you have to help the compiler out by writing List[Cookie](), or it will infer that it's a list of Nothing, which results in weird error messages.

Convention:

[Repeated from PS1 rubric (I realize students hadn't seen the solutions to PS1 when they turned in PS2)] — Scala style calls for indentation by 2 spaces; if your editor has default indentation = 4 spaces, or, worse yet, by a tab character, change the setting. If indentation by tab is wired in, find a new editor. (Tab stops are set by the reader of the code, not the writer; it's unpredictable what the code will look like to the reader if it contains tabs.)

[Repeated from PS1 rubric] — Avoid using the return statement or any other "nonlocal goto" except throwing exceptions. The correct way (as far as CS470/570 is concerned) to exit a loop "prematurely" is to add a (typically Boolean) variable whose value may be set when the condition requiring premature exit is detected, and read in the while condition.

Make sure that subexpressions are indented so that every line starts on a column to the right of the column the containing expression starts in. Here's what not to do:

   case ... => if (...) {
     ...
   }     — These lines violate the rule.  The "}" 
   else  — and "else" start in the same column as "case".

Better:
   case ... => if (...) {
       ...
     }
     else

It's even clearer with a pair of braces around the if-expression but they're not necessary.

Reality:

Exactly how many points were taken off for violating the following "suggestions" was a matter of deciding how obvious and damaging the violation was.

1. Fight old bad habits: Sure, you're used to certain familiar coding patterns, so given a new problem you reach for a tool in your kit. Well, it's time to think of developing a new toolkit. Don't always think of a loop as accumulating something, and every problem as one of figuring out what needs to be accumulated. The accumulation pattern is a "fold left" pattern, but some problems have much cleaner solutions using the "fold right" tool. Think about whether that's true for this problem.

   It's useful to daydream about different cases when first approaching a problem, but don't automatically start writing an "if – then – else" or "case … match { case … => … }" without being prepared to throw it all away. The problem isn't that you won't be able to finish having started this way; the problem is that you will always be able to finish. That's because if a problem has a solution, then that problem + some assumption A also has a solution.^Theorem So if you write

   if (A) C_T  else C_F

   then you'll be able to write C_T, with the added information that A, and you'll be able to write C_F, with the added information that ¬A. But if you start to notice big overlaps between C_T and C_F, you should stop and consider whether the time to check whether A is true is at the beginning, or at some later point, or never. You don't have to do this stopping and considering, but if you don't you'll have a clumsy, overstuffed program. Especially if you repeat this mistake every chance you get.

2. Feel free to create as many functions as you need. You may come to the conclusion from early examples that recursive functions never need auxiliary functions. They often do. In fact, it's a healthy design technique, whether the function you're writing is recursive or not, to imagine an auxiliary function you need, and write a quick informal definition of what it's supposed to do (an argument-assumptions/result-requirements spec), not how it does it. Continue writing your original function assuming you have this function, then go back and implement it later. (And please, give functions names that say what they do. Don't name your functions helperFcn1, helperFcn2, etc.) At some point you may realize that the function you need is one you're already defining. Eureka! Feel free to call it; you've found two ends of a string, and tying them together will … yes, wrap up the solution recursively.

   But again, don't forget to revisit guesses you made early on in a program's development. If an auxiliary function F turns out to do almost nothing besides call some other function G, then perhaps the "almost nothing" bit can be moved into G, or moved to the callers of F, and F can be eliminated. Maybe not; maybe even though F does very little, that very little can't be moved to G (because G has other callers, say), and can't be moved to the caller(s) of F (because it would spoil their natural beauty). Leave it alone, then! Just make sure that if it survives it has an informative name! Perhaps its original informative name you can now see isn't quite right. Change it while you have a chance.

3. Use immutable data structures. This is the crucial respect in which a program using immutable data structures differs from a program using mutable ones: If procedure p makes a change to a mutable data structure x and returns n values (i.e., an n-tuple^{Tiny tuples} (v₁, …, v_n)), the equivalent procedure p' making a "change" to the immutable version of x must return an extra value: (v₁, … {}, v_n, x'), where x' is the new version of x. (It doesn't have to be the last value returned, of course, but if it isn't returned, then the "change" accomplishes nothing.)

   In the simplest case, p might have changed its x and returned no value (in Scala, returned (); the compiler is friendly enough not to require you to ensure that, if p has return type Unit, the last expression in p actually evaluates to (), but any other value is discarded and () will be returned). The new version, p', returns one value, x'. If p changes k data structures, it will have to return k new values besides the previous ones it returned.

   This may seem like a big hassle. It did to me when I first heard the idea. And it seems inefficient. If you make an actual change to a data structure, you don't have to copy big pieces of it. I have changed my mind. For one thing, the cost of copying depends on how the abstraction is implemented. Immutable hash tables (or "hash maps") are not simple arrays, so you're not copying an array every time you copy one with a small change. They're implemented so they share some structure with the map they're a copy of. (I don't know the details.)

   The main advantage of immutable data structures is that you get to think of them as constants. This frees your mind dramatically. For instance, if you want to compare some property of a data structure before and after changing it, with a mutable data structure you have to think, often very carefully, about when to measure and how much to measure. With an immutable data structure, that issue goes away. You have one variable whose value is the earlier version, and one whose value is the later one. They can't possibly "change out from under you." If the measurement is rarely needed, then you don't make it unless you have to. It's just a question of when the garbage collector gets its hands on the earlier version (by which colorful phrase I mean, "when no pointers to it are still accessible by the program").

4. A recursive function almost always has at least one parameter ("formal argument"). If you are going to do something to a recursively defined data structure, and that something involves looking at every level of the recursively defined structure, then that something is probably a recursive function one of whose parameters is bound to a piece of the recursively defined structure.

   However, this must be qualified by one caveat: If the class definition for the subpieces is something you control^Control (it might be the class for the object you started with), then another option is to make the recursive function a member of that class definition. Then instead of function(subpiece, ...) you would write subpiece.function(...). Knowing when to use one approach rather than the other is tricky, but if in doubt use the first version.

   In the case of PS2Q1, though, the second option is not possible. An instance of a PS2Q1 has no subpieces that are also instances of PS2Q1. Its subpieces are lists of integers. The class List is not under your control. If you want to write a recursive function to do one of the tasks for question 2, define an auxiliary function. You can define it any convenient place. One such place is the companion object for the class. Another is the body of the function that calls it.

   A good sign of trouble is if you are building a new object just so you can call your recursive function. You're writing something like ...+ new Foo(...).recursiveFunc(...) or

      val x1 = ...
      val f1 = new Foo(...)
      x1 + f1.recursiveFunc(...)
   

5. Don't casually compute the length of a linked list:

   Avoid calculating the size of a list unless you really need it, and be suspicious of any code that computes the length of the same list repeatedly. Linked lists are wonderful data structures, but they're not good at accessing elements beyond the first two or three, and computing the length requires iterating down the entire list. (The size of a collection is the same as its length). Be especially suspicious of repeated calls to length in a loop or recursion. Even if the list is getting smaller with each recursive call, the resulting algorithm will still have time complexity proportional to N².

   A test such as l.length > 0 is really a waste. If the length is actually > 0, the entire march down the list is painful to contemplate, because the exact number computed is almost certainly useless. Just say l.nonEmpty or just l != Nil. Better yet, use pattern matching.

   Another idea, occasionally useful, is to call the function shorter: shorter(l, k) is t if l's length is ≤ k. (You'll have to write shorter yourself; it's not built in.) Instead of writing l.length > 0, write !shorter(l,1).

   I took no points off for this mistake, because I made it myself! The original solution for 1C was correct, but took the length of every tail of the list nums.

6. Don't casually use "append" (::: or ++ or +^{Append versions}): The Scala collections API, and most other functional languages, make it too easy to append two linked lists. You write l₁ ::: l₂ and get a nice functional feeling. It doesn't look much worse than x₁ :: l₂. But it requires copying l₁, which takes time proportional to the length of l₁. Most collections, not just linked lists, have this problem (queues being an obvious exception).

   If the call to ":::" is in a loop, the problem is compounded. Suppose you are adding to a list l by collecting items in a loop of some sort, and every time you find an item w that is worth keeping you execute

   l = l ::: List(w)

   Then if the length of l is n by the time you're done, the time required to execute the loop is proportional to n². A simple change to

   l = w :: l

   reduces the time to O(n). Of course, now the elements will be in the opposite order when you're done collecting them. If that matters, as it often does, just do this after the loop is through collecting:

   l = l.reverse

   This operation is again O(n). Instead of taking time proportional to n², the entire thing takes time proportional to n.