CSE 130, SP16 - HW #6 (220 points)

See the top of this for instructions on installing Scala at home. Remember that this is only to enable you to play with the assignment at home: The final version turned in must work on the ACS Linux machines. While you can use Windows/Mac etc. to begin working with Scala, the code you turn in must be that required for the Linux environment.

Overview

The overall objective of this assignment is to introduce you to some of the advanced features of Scala, including case classes, implicits and randomized property checking.

The assignment is spread over a single zip file hw6.zip. When you download and open it with unzip hw6.zip out come tumbling the following files

which contain several skeleton Scala functions, with missing bodies, which currently contain the placeholder text sys.error("TO BE WRITTEN").
Your task is to replace the placeholder text in those files with the appropriate Scala code for each case.

Assignment Testing and Evaluation

Your functions/programs must compile and/or run on a ACS Linux machine (e.g. ieng6.ucsd.edu) as this is where your solutions will be checked. While you may develop your code on any system, ensure that your code runs as expected on an ACS machine prior to submission. You should test your code in the directories from which the zip files (see below) will be created, as this will approximate the environment used for grading the assignment.

Most of the points, will be awarded automatically, by evaluating your functions against a given test suite. test.ml contains a very small suite of tests which gives you a flavor of of these tests. At any stage, by typing at the UNIX shell :

> make test | grep "130>>" > log

The last line of the file log must contain the word ``Compiled" otherwise you get a zero for the whole assignment.

If for some problem, you cannot get the code to compile, leave it as is with the sys.error("TO BE DONE") with your partial solution enclosed below as a comment.

The second last line of the log file will contain your overall score, and the other lines will give you a readout for each test. You are encouraged to try to understand the code in Test.scala, but you will not be graded on this.

Alternately, after doing make in the UNIX shell, inside the Scala shell, type:

scala> import Test._ 
scala> Test() 
  .
  .
130>> Results: ...
130>> Compiled

and it should return a pair of integers, reflecting your score and the max possible score on the sample tests. If instead an error message appears, your code will receive a zero.

Submission Instructions

turnin will provide you with a confirmation of the submission process; make sure that the size of the file indicated by turnin matches the size of your zip file. See the ACS Web page on turnin for more information on the operation of the program.

Problem 1: ADTs Strike Back: Case-Classes (Bst.scala)

For this problem, you will use Scala’s case-classes to implement an Abstract Set datatype, whose properties are captured by the following trait:

trait AbstractSet[A] extends Iterable[A] {
  def contains(n: A): Boolean
  def add(n: A): AbstractSet[A]
  def remove(n: A): AbstractSet[A]
  
  // For Testing
  def execCmds(cmds: List[(Boolean, A)]): AbstractSet[A] = {
    cmds.foldLeft(this)((s, cmd) => { 
      if (cmd._1) { this.add(cmd._2) } else { this.remove(cmd._2) }
    })
  }
}

includes the usual set operations which you will implement, and method that uses add and remove for testing (we’ll see this later.)

Overview: Sets via Binary-Search-Trees

The sets will be represented as Binary Search Trees that support efficient addition and removal of elements.

case class Node[A](elt: A, left: BST[A], right: BST[A]) extends BST[A]
case class Leaf[A]() extends BST[A]
sealed abstract class BST[A] extends AbstractSet[A]

Thus, values of type BST[A] are of the form Leaf() or Node(e, l, r) where e is an element of type A and l and r are left and right subtrees of type BST[A].

We will only use trees that are binary search ordered, which is to say, trees t such that t.isOrdered evaluates to true.

(a) 10 points: build

Fill in the definition of the method BST.build_ that converts the supplied List[A] into a BST[A] by recursively splitting the list up into sub-lists, converting the sub-lists to trees. Make sure that the resulting BST[A] is binary-search-ordered.

scala> BstProperties.prop_bso.check
+ OK, passed 100 tests.

(b) 10 points: contains

def contains(x: A): Boolean

so that t.contains(x) returns true iff the element x is in the tree t. When you are done, you should see the following behavior at the REPL

scala> BST.t2
res6: BST[Int] = Node(5, 10, 20, 30)

scala> List(5,6,10,11,20,21,30,31).map(BST.t2 contains _)
res7: List[Boolean] = List(true, false, true, false, true, false, true, false)

Writing tests is tedious, instead we will check properties! This one (go read the definition, or else!) states that trees generated by the build method are indeed binary-search ordered.

scala> BstProperties.prop_contains_elt.check
+ OK, passed 100 tests.

Now, write a fold method that performs an in-order traversal of the tree, accumulating the results as it goes.

def fold[B](f: (B, A) => B, acc: B): B

When you are done, various bonus properties of the tree get unlocked by virtue of the iterator method that we have supplied that uses the above fold. In particular, you should get the following behavior

cala> BST.t2.toList
res11: List[Int] = List(5, 10, 20, 30)

scala> BST.t2.toString
res13: String = BST(5, 10, 20, 30)

You should also check the property that the trees you build actually contain the elements from the source list.

scala> BstProperties.prop_contains_elts.check
+ OK, passed 100 tests.

(d) 10 points: add

def add(x:A): BST[A]

which returns a (new) BST which has the same elements as the original tree plus the new element x. Of course, the new tree should also satisfy the binary-search-ordering invariant. When you are done, you should see the following behavior

scala> BST.t2
res0: BST[Int] = BST(5, 10, 20, 30)

scala> BST.t2.add(12)
res1: BST[Int] = BST(5, 10, 12, 20, 30)

scala> val t2_new = BST.t2.add(12)
t2_new: BST[Int] = BST(5, 10, 12, 20, 30)

scala> t2_new.isOrdered
res2: Boolean = true

Writing tests by hand is boring, so instead we check the property that the added elements are indeed in the new set. (Make sure you understand the properties.)

Scala> BstProperties.prop_add_elt.check
+ OK, passed 100 tests.

scala> BstProperties.prop_add_elts_old.check
+ OK, passed 100 tests.

(e) 5 points: debug the property

Scala> BstProperties.prop_multiset.check
! Falsified after 5 passed tests.

Uh oh. Lets try to debug the code and property to see why the test fails. In the scala shell, you should see something like this:

scala> BstProperties.prop_multiset.check
! Falsified after 4 passed tests.
> ARG_0: List("1", "1")

You might see something different for ARG_0, i.e. some other list, but nevertheless you will see some kind of list. Well, lets see why the property failed, by running the test on the failing input that Scalacheck has automatically found for us!

scala> val xs = List(1, 1)
xs: List[Int] = List(1, 1)

(again, your failing input may be slightly different, because Scalacheck finds them by random sampling.) Now, lets run the property on that input. How? Well the property is

forAll((xs: List[Int]) => BST(xs).toList == xs.sorted)

That is, for any list xs the result of building a BST from xs and converting it to a list, should be identical to just sorting the list xs. Lets see if that is true, for the particular xs that we have above.

scala> BST(xs).toList == xs.sorted
res2: Boolean = false

scala> BST(xs).toList
res3: List[Int] = List(1)

scala> xs.sorted
res4: List[Int] = List(1, 1)

of course! The BST does not keep duplicates (no duplicates on the LHS), but vanilla sorting does keep duplicates! So the property is broken, we want to check only that the BST has all the elements from xs without any duplicates.

Fix the property so that it passes. Do this in a meaningful way – don’t just replace it with true.

Note: Use the above strategy to fix your code when there are other failing tests too (its just in this one case that the property itself was “wrong” :)).

(f) 10 points: removeMin

def removeMin : (A, BST[A])

that returns a tuple of the minimum element in the tree, and the tree containing all elements except the minimum. (If the tree passed in is empty, so there is no minimum element, use sys.error to indicate the problem.) When you are done you should see this behavior

Scala> BST.t2.removeMin
res7: (Int, BST[Int]) = (5,BST(10, 20, 30))

Scala> BstProperties.prop_remove_min.check
+ OK, passed 100 tests.

(g) 20 points: remove

def remove(x: A): BST[A]

which returns the set containing all elements except x. Of course, the new set should satisfy the binary-search-ordering property. When you are done, you should see the following behavior.

scala> BST.t2.remove(12)
res1: BST[Int] = BST(5, 10, 20, 30)

scala> BST.t2
res2: BST[Int] = BST(5, 10, 20, 30)

scala> BST.t2.remove(20)
res3: BST[Int] = BST(5, 10, 30)

scala> BstProperties.prop_remove_elt.check
+ OK, passed 100 tests.

scala> BstProperties.prop_remove_elt_old.check
+ OK, passed 100 tests.

scala> BstProperties.prop_bst_equiv_gold.check
+ OK, passed 100 tests.

Problem 2: Functions Are Objects (Decorators.scala)

In Scala, functions are (also) objects. In this exercise, you will see an example of the decorator design pattern , where we add functionality to objects via wrappers.

In the file Decorators.scala there is an example decorator profiled and stub code for decorators trace and memo that you will fill in. The file DecoratorTest.scala contains several examples of decorated functions. The expected output for all these functions is available in decorators.out.

profiled is an object whose field cm maps strings to an integer counter (initially 0). The apply method

def apply[A, B](name: String)(f: A => B) = new Function1[A, B] {...}

takes two arguments, a name string and a function f and returns a new function object whose apply method behaves just like f but at each call, increments the count associated with the name. Thus, to find out how many times a decorated function named name has been called, we can simply call profile.count(name).

scala> import Decorators._
scala> import DecoratorTest._

scala> profile.count("fac")
res0: Int = 0

scala> fac(5)
res1: Int = 120

scala> profile.count("fac")
res2: Int = 5

scala> fac(10)
res3: Int = 3628800

scala> profile.count("fac")
res4: Int = 15

scala> profile.reset("fac")

scala> profile.count("fac")
res6: Int = 0

scala> fac(4)
res7: Int = 24

scala> profile.count("fac")
res8: Int = 4

(a) 20 points: Tracing

Complete the definition for the decorator trace. (You may need to add extra private fields to the function object that the trace object’s apply method returns.) When the decorated function is called, the decorator should print out an ASCII art tree of the recursive calls and their return values. The format of the tree should be as follows:

The return value of the function should be return to the caller after all printing is complete.

scala> import Decorators._
scala> import DecoratorTest._

scala> fibT(5)
,- fibT(5)
| ,- fibT(4)
| | ,- fibT(3)
| | | ,- fibT(2)
| | | | ,- fibT(1)
| | | | `- 1
| | | | ,- fibT(0)
| | | | `- 1
| | | `- 2
| | | ,- fibT(1)
| | | `- 1
| | `- 3
| | ,- fibT(2)
| | | ,- fibT(1)
| | | `- 1
| | | ,- fibT(0)
| | | `- 1
| | `- 2
| `- 5
| ,- fibT(3)
| | ,- fibT(2)
| | | ,- fibT(1)
| | | `- 1
| | | ,- fibT(0)
| | | `- 1
| | `- 2
| | ,- fibT(1)
| | `- 1
| `- 3
`- 8
res9: Int = 8

scala> even(5)
,- even(5)
| ,- odd(4)
| | ,- even(3)
| | | ,- odd(2)
| | | | ,- even(1)
| | | | `- false
| | | `- false
| | `- false
| `- false
`- false
res10: Boolean = false

(b) 10 points: Tracing with Exceptions

Extend your tracing function to properly handle exceptions. If an exception occurs in the function, the nesting level must be adjusted to the appropriate level where the exception is caught.

scala> changeT(List(5, 3), 6)
,- changeT((List(5, 3),6))
| ,- changeT((List(5, 3),1))
| | ,- changeT((List(3),1))
| | | ,- changeT((List(),1))
| ,- changeT((List(3),6))
| | ,- changeT((List(3),3))
| | | ,- changeT((List(3),0))
| | | `- List()
| | `- List(3)
| `- List(3, 3)
`- List(3, 3)

Next, complete the definition of the memo decorator. The purpose of this decorator is to cache the results of calls to a function, and to directly return the cached result on subsequent calls with the same arguments.

To this end, you need to add a private cache to the wrapped function object. In the apply method of the wrapped object, you should check whether the given arguments are already in the cache.

Once you have implemented the function, you should get the following behavior at the Python prompt:

scala> import DecoratorTest._
import DecoratorTest._

scala> snooze(0)
// 5 second pause
res0: Int = 1

scala> snooze(0)
// practically instantaneous
res1: Int = 1

(d) 10 points: Memoize with exceptions

Extend the decorator so that it handles functions that throw exceptions. That is,

Hint: Scala reuses Java’s exception mechanism, so an exception is simply an object of type Throwable. See this for a refresher.

Hint: You may want to use the Either to remember whether the function threw an exception or returned a real value.

scala> import DecoratorTest._
import DecoratorTest._

scala> hissy(0)
// 5 second pause
res0: Boolean = true 

scala> hissy(1)
// 5 second pause
DecoratorTest$HissyFitException
	at DecoratorTest$$anonfun$16.apply$mcZI$sp(Test.scala:123)
	at DecoratorTest$$anonfun$16.apply(Test.scala:121)
    ...

scala> hissy(0)
// practically instantaneous
res1: Boolean = true 

scala> hissy(1)
// practically instantaneous

DecoratorTest$HissyFitException
	at DecoratorTest$$anonfun$16.apply$mcZI$sp(Test.scala:123)
	at DecoratorTest$$anonfun$16.apply(Test.scala:121)
    ...

$ make decorators
$ scala DecoratorTest > out
$ diff out decorators.out
$

That is, the output file out should be identical to the supplied, reference output file decorators.out.

Problem 3: Document Layout Engine (Json.scala)

For this problem you will write a simple document layout engine, that allows the clean printing of nested documents.

class Doc(val lines: List[String])

Thus, a document is a list of lines, each of which is a string. For example, the document

ruination
whiterascal
fattire

Doc(List("ruination", "whiterascal", "fattire"))

(a) 5 points: Tail Recursion Revisited

Fill in the definition of padBegin(xs, n, x), which returns a list of length n with enough copies of x (at the beginning) followed by xs. When you are done, you should see the following behavior at the prompt.

//If length is less than n then output is padding ++ input 
scala> Doc.padBegin(List(1,2,3,4,5), 10, 0)
res: List[Int] = List(0,0,0,0,0,1,2,3,4,5)

//If length is greater than n then output is same as input
scala> Doc.padBegin(List(1,2,3,4,5), 3, 0)
res: List[Int] = List(1,2,3,4,5)

(b) 5 points: Don’t really need more recursion…

Fill in the definition of padEnd(xs, n, x), which returns a list of length n with xs followed by enough copies of x (at the end). When you are done, you should see the following behavior at the prompt.

//If length is less than n then output is input ++ padding 
scala> Doc.padEnd(List(1,2,3,4,5), 10, 0)
res: List[Int] = List(1,2,3,4,5,0,0,0,0,0)

//If length is greater than n then output is same as input
scala> Doc.padEnd(List(1,2,3,4,5), 3, 0)
res: List[Int] = List(1,2,3,4,5)

Fill in the implementation of method vcat which given the receiver (Doc) object and another Doc (named that), returns a new document that is the vertical concatenation of the receiver and that with the documents aligned at the left. When you are done, you should see the following behavior at the prompt.

scala> val d0 = Doc("cat") vcat Doc("mongoose")
d0: Doc = 
cat
mongoose

(d) 10 points: Horizontal Concat (Aligned at Top)

Next, fill in the implementation of method hcatT which given the receiver (Doc) object and another Doc (named that), returns a new document that is the horizontally concatenation of the receiver and that with the top lines horizontally aligned. When you are done, you should see the following behavior at the prompt.

scala> val dks = Doc("1: ", "2: ", "3: ")
scala> val dvs = Doc("cat", "doggerel", "moose")

scala> dks hcatT dvs
res: Doc = 
1: cat
2: doggerel
3: moose

scala> Doc("{ ") hcatT dks hcatT dvs 
{ 1: cat
  2: doggerel
  3: moose

scala> dvs hcatT Doc(" ") hcatT dks
res3: Doc = 
cat      1: 
doggerel 2: 
moose    3: 

scala> dvs hcatT Doc("---> at the top")
res5: Doc = 
cat     ---> at the top
doggerel
moose

(e) 10 points: Horizontal Concat (Aligned at Bottom)

Next, fill in the implementation of method hcatB which given the receiver (Doc) object and another Doc (named that), returns a new document that is the horizontally concatenation of the receiver and that with the bottom lines horizontally aligned. When you are done, you should see the following behavior at the prompt.

scala> val dks = Doc("1: ", "2: ", "3: ")
scala> val dvs = Doc("cat", "doggerel", "moose")

scala> dks hcatB dvs
res: Doc = 
1: cat
2: doggerel
3: moose

scala> Doc("{ ") hcatB dks hcatB dvs 
  1: cat
  2: doggerel
{ 3: moose

scala> dks hcatB dvs hcatB Doc(" }")
1: cat
2: doggerel
3: moose    }

scala> dvs hcatB Doc(" ") hcatB dks
res3: Doc = 
cat      1: 
doggerel 2: 
moose    3: 

scala> dvs hcatB Doc("---> at the bottom")
res5: Doc = 
cat      
doggerel
moose   ---> at the bottom

When both hcat and vcat are working you should get the following behavior at the prompt:

scala> val d0 = Doc("cat") vcat Doc("mongoose")
scala> val d1 = d0 hcatT Doc(" ") hcatT d0 hcatT Doc(" ") hcatT d0
d1: Doc = 
cat      cat      cat
mongoose mongoose mongoose

scala> val d2 = Doc("apple") vcat d1
d2: Doc = 
apple
cat      cat      cat
mongoose mongoose mongoose

scala> val d3 = d2 hcatT Doc(" ") hcatT d2
d3: Doc = 
apple                      apple
cat      cat      cat      cat      cat      cat
mongoose mongoose mongoose mongoose mongoose mongoose

Problem 4: Rendering Json Values (Json.scala)

JSON – JavaScript Object Notation is a lightweight data-interchange format, that is human- and machine-readable, and commonly used in so-called AJAX web applications like Gmail, FaceBook etc. to ship data across machines.

sealed abstract class JVal 
case class JStr(s: String)            extends JVal
case class JNum(n: BigDecimal)        extends JVal
case class JObj(o: Map[String, JVal]) extends JVal
case class JArr(a: List[JVal])        extends JVal

In this problem, use the document formatter from above to convert JVal to pretty Doc which can be shown as Strings, and then

(a) 15 points: Rendering JVal

Use the Doc formatting class defined above to fill in the definition of the function JVal.render

def render(jv: JVal) : Doc

scala> import JsonTest._
import JsonTest._

scala> JVal.render(jvReals(0))
res4: Doc = 
{ fst : 1
, snd : "cat" }

scala> JVal.render(jvReals(1))
res5: Doc = 
{ fst : { fst : 1
        , snd : "cat" }
, snd : { fst : 1      
        , snd : "cat" }
, thd : { fst : 1      
        , snd : "cat" } }

scala> JVal.render(jvReals(2))
res6: Doc = 
{ fst : 1
, snd : "cat"                    
, thd : { fst : { fst : 1        
                , snd : "cat" }  
        , snd : { fst : 1        
                , snd : "cat" }  
        , thd : { fst : 1        
                , snd : "cat" } } }

scala> JVal.render(jvReals(3))
res10: Doc = 
{ fst : 1
, snd : { fst : 2                                    
        , snd : { fst : 3                            
                , snd : { fst : 4                    
                        , snd : { fst : 5            
                                , snd : "Nil" } } } } }

scala> JVal.render(jvReals(4))
res: Doc = 
{ { fst : "one"
  , snd : 1 }
, { fst : "two"  
  , snd : 2 }    
, { fst : "three"
  , snd : 3 }     }


scala> JVal.render(jvReals(5))
res: Doc = 
{ 1
, 2
, 3
, 4 }

scala> JVal.render(jvReals(6))
res8: Doc = 
{ mon : 10
, tue : 20
, wed : 30 }

scala> JVal.render(jvReals(7))
scala> JVal.render(jvReals(7))
res6: Doc = 
{ eng : { { fst : "one"
          , snd : 1 }
        , { fst : "two"  
          , snd : 2 }    
        , { fst : "three"
          , snd : 3 }     }
, spanish : { { fst : "uno"   
              , snd : 1 }     
            , { fst : "dos"   
              , snd : 2 }     
            , { fst : "tres"  
              , snd : 3 }    }
, french : { { fst : "un"     
             , snd : 1 }      
           , { fst : "deux"   
             , snd : 2 }      
           , { fst : "trois"  
             , snd : 3 }     } }

Problem 5: Serializing Scala Values with TypeClasses (Json.scala)

Now, it is rather lame to have to write down JVal manually. Next, you will use Scala’s traits and implicits to automatically serialize comples Scala scala values tuples, arrays, maps, and nested combinations thereof, into Json values.

trait Json[T] { 
  def json(t: T): JVal
}

which corresponds to a typeclass representing values that can be converted to JVal. The object JsonWriter uses the above trait to define methods that will serialize Scala values:

object JsonWriter {
  def write(v: JVal): String = 
    JVal.render(v).toString 
  def write[A: Json](x: A): String = 
    write(Json.toJson(x))
}

The write method takes any input of type A as long as A has the Json trait, and converts it a String. To do so, it uses the implicit Just.toJson method to obtain a JVal which is then rendered as a String.

scala> import Json._ //puts the implicit views into scope

scala> Json.toJson(1)
res5: JVal = JNum(1)

scala> Json.toJson("dog")
res6: JVal = JStr(dog)

scala> Json.toJson((1,(2,(3,"Null"))))
res9: JVal = JObj(Map(fst -> JNum(1), snd -> JObj(Map(fst -> JNum(2), snd -> JObj(Map(fst -> JNum(3), snd -> JStr(Null)))))))
scala>

scala> JsonWriter.write(1,(2,(3,"Null")))
res10: String = 
{ fst : 1
, snd : { fst : 2                 
        , snd : { fst : 3         
                , snd : "Null" } } }

Note that in the last case, we are automatically converting a type for which we didn’t even a Json converter (!) because Scala is composing the implicits for Int, String and (A, B) in a type-directed manner.

(a) 5 points: Convert Scala Triples To Json

Using the definition of tuple2Json for inspiration, fill in the definition of tuple3Json. When you are done, you should see the following behavior at the prompt.

scala> import Json._
scala> Json.toJson(tup1)

res16: JVal = JObj(Map(fst -> JObj(Map(fst -> JNum(1), snd -> JStr(cat))), snd -> JObj(Map(fst -> JNum(1), snd -> JStr(cat))), thd -> JObj(Map(fst -> JNum(1), snd -> JStr(cat)))))


scala> JsonWriter.write(tup1)
res13: String = 
{ fst : { fst : 1
        , snd : "cat" }
, snd : { fst : 1      
        , snd : "cat" }
, thd : { fst : 1      
        , snd : "cat" } }

scala> JsonWriter.write(tup2)
res14: String = 
{ fst : 1
, snd : "cat"                    
, thd : { fst : { fst : 1        
                , snd : "cat" }  
        , snd : { fst : 1        
                , snd : "cat" }  
        , thd : { fst : 1        
                , snd : "cat" } } }

(b) 10 points: Convert Scala Lists To Json

Next, fill in listJson. When you are done, you should see the following behavior at the prompt.

scala> import Json._
scala> Json.toJson(intl)
res17: JVal = JArr(List(JObj(Map(fst -> JStr(one), snd -> JNum(1))), JObj(Map(fst -> JStr(two), snd -> JNum(2))), JObj(Map(fst -> JStr(three), snd -> JNum(3)))))

scala> JsonWriter.write(intl)
res18: String = 
{ { fst : "one"
  , snd : 1 }
, { fst : "two"  
  , snd : 2 }    
, { fst : "three"
  , snd : 3 }     }

Next, fill in arrJson . When you are done, you should see the following behavior at the prompt.

scala> import Json._
scala> Json.toJson(ints)
res: JVal = JArr(List(JNum(1), JNum(2), JNum(3), JNum(4)))

scala> JsonWriter.write(ints)
res: String = 
{ 1
, 2
, 3
, 4 }

(d) 10 points: Convert Scala Maps To Json

Finally, fill in mapJson. When you are done, you should see the following behavior at the prompt.

scala> import Json._
scala> Json.toJson(mm)
res: JVal = JObj(Map(mon -> JNum(10), tue -> JNum(20), wed -> JNum(30)))

scala> JsonWriter.write(mm)
res: String = 
{ mon : 10
, tue : 20
, wed : 30 }



scala> JsonWriter.write(lang)
res8: String = 
{ eng : { { fst : "one"
          , snd : 1 }
        , { fst : "two"  
          , snd : 2 }    
        , { fst : "three"
          , snd : 3 }     }
, spanish : { { fst : "uno"   
              , snd : 1 }     
            , { fst : "dos"   
              , snd : 2 }     
            , { fst : "tres"  
              , snd : 3 }    }
, french : { { fst : "un"     
             , snd : 1 }      
           , { fst : "deux"   
             , snd : 2 }      
           , { fst : "trois"  
             , snd : 3 }     } }

CSE 130 SP16- HW #6 (220 points)

Due by 23:59:59 on Friday, Jun 3, 2016

Installing Scala

Overview

Assignment Testing and Evaluation

Submission Instructions

Problem 1: ADTs Strike Back: Case-Classes (Bst.scala)

Overview: Sets via Binary-Search-Trees

(a) 10 points: build

(b) 10 points: contains

(c) 15 points: fold

(d) 10 points: add

(e) 5 points: debug the property

(f) 10 points: removeMin

(g) 20 points: remove

Problem 2: Functions Are Objects (Decorators.scala)

(a) 20 points: Tracing

(b) 10 points: Tracing with Exceptions

(c) 20 points: Memoize

(d) 10 points: Memoize with exceptions

Problem 3: Document Layout Engine (Json.scala)

(a) 5 points: Tail Recursion Revisited

(b) 5 points: Don’t really need more recursion…

(c) 5 points: Vertical Concat (Aligned at Left)

(d) 10 points: Horizontal Concat (Aligned at Top)

(e) 10 points: Horizontal Concat (Aligned at Bottom)

Problem 4: Rendering Json Values (Json.scala)

(a) 15 points: Rendering `JVal`

Problem 5: Serializing Scala Values with TypeClasses (Json.scala)

(a) 5 points: Convert Scala Triples To Json

(b) 10 points: Convert Scala Lists To Json

(c) 5 points: Convert Scala Arrays To Json

(d) 10 points: Convert Scala Maps To Json

CSE 130 SP16- HW #6 (220 points)

Due by 23:59:59 on Friday, Jun 3, 2016

Installing Scala

Overview

Assignment Testing and Evaluation

Submission Instructions

Problem 1: ADTs Strike Back: Case-Classes (Bst.scala)

Overview: Sets via Binary-Search-Trees

(a) 10 points: build

(b) 10 points: contains

(c) 15 points: fold

(d) 10 points: add

(e) 5 points: debug the property

(f) 10 points: removeMin

(g) 20 points: remove

Problem 2: Functions Are Objects (Decorators.scala)

(a) 20 points: Tracing

(b) 10 points: Tracing with Exceptions

(c) 20 points: Memoize

(d) 10 points: Memoize with exceptions

Problem 3: Document Layout Engine (Json.scala)

(a) 5 points: Tail Recursion Revisited

(b) 5 points: Don’t really need more recursion…

(c) 5 points: Vertical Concat (Aligned at Left)

(d) 10 points: Horizontal Concat (Aligned at Top)

(e) 10 points: Horizontal Concat (Aligned at Bottom)

Problem 4: Rendering Json Values (Json.scala)

(a) 15 points: Rendering JVal

Problem 5: Serializing Scala Values with TypeClasses (Json.scala)

(a) 5 points: Convert Scala Triples To Json

(b) 10 points: Convert Scala Lists To Json

(c) 5 points: Convert Scala Arrays To Json

(d) 10 points: Convert Scala Maps To Json

(a) 15 points: Rendering `JVal`