Programming Assignment #6 (190 Points)

Due: Fri, Mar 14, 5:00pm

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

To start, download pa6.zip and run unzip pa6.zip. This will unleash three files

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

The zipfile also contains the following helper files that you will not modify:

And some sample output files for Problem #2:

Assignment Testing and Evaluation

Same as for Homework #5.

Submission Instructions

To turn in your solution, simply type 

$ make turnin
in the directory in which you are working. 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.

ScalaCheck JAR File

Writing tests can be tedious. To help reduce the burden, in this assignment we will learn to use ScalaCheck, a library for automatic property checking based on random test generation!

As you can see from the Makefile, we have downloaded the ScalaCheck JAR file as /cs130w/public/scalacheck_XXX.jar and added this file to the class path for compilation.

Furthermore, we have defined an alias for scala that includes the ScalaCheck JAR file on the classpath. So, you should be able to access the ScalaCheck library from the REPL simply by running scala. To verify that this alias has been preped correctly, try running: 

$ which scala
alias scala=
  ’scala -cp .:/home/linux/ieng6/cs130w/public/scalacheck_2.10-1.11.3.jar’
  /home/linux/ieng6/cs130w/public/bin/scala

Problem #1: 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) }
    })
  }
}
This trait includes the usual set operations which you will implement, and methods that uses add and remove for testing (we’ll see this later.)

Sets as Binary Search Trees

To implement the specification above, we will represent sets as Binary Search Trees that support efficient addition and removal of elements.

We represent the datatype as: 

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]
(The real code includes the implicits that allow for comparisons.)

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.

Note: Make sure you understand what the isOrdered method is doing!

(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. Furthermore, there should be no duplicates in the tree.

We will now use ScalaCheck for the first time to randomly generate a bunch of test cases for our build method. The property BstProperties.prop_bso_check (go read the definition) states that trees generated by the build method are indeed binary-search ordered. When you are done you should get the following behavior: 

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

(B) 10 points: Contains

Next, fill in the definition of the method 

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)

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

(C) 15 points: Fold

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 which we have supplied that uses 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

Now fill in the definition for 

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. If the x is already in the tree, then the output tree should be the same as the original. 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
And a few more properties (make sure to read and understand them): 
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

We’ve seen a bunch of properties go sailing through. But consider this: 

Scala> BstProperties.prop_multiset.check
! Falsified after 5 passed tests.
Uh oh... Let’s 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 particular list). Let’s see why the property failed by running the test on the failing input that ScalaCheck has automatically found for us!

First, copy that input into a variable: 

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, let’s run the property on that input. The property, defined in Bst.scala, 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. Let’s see if that’s true for the particular xs that we have above. 
scala> BST(xs).toList == xs.sorted
res2: Boolean = false
Hmm, why? Well, dig further. The left hand side of the equality is 
scala> BST(xs).toList
res3: List[Int] = List(1)
and the right hand side is 
scala> xs.sorted
res4: List[Int] = List(1, 1)
of course! The BST does not keep duplicates but vanilla sorting does! So the property itself is broken. Instead, 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: You can use the above strategy to fix your code when there are other failing tests, too. It just so happens that in this case, the property itself was "wrong". :-)

(F) 10 points: Remove Min

We also want to remove elements from the set. As a first step, write a method 

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 there is no minimum element, so 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))
or better, with the properties

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

(G) 20 points: Remove

Finally, use removeMin to fill in the definition of 

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)
And we can stress test with properties: 
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: Decorators (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 profile 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.

profile 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 except that, at each call, it 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).

After running 

$ make
you should see the following behavior at the Scala REPL: 
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:

  • Print a pipe symbol followed by a space (| ) for every level of nested function calls.
  • Print a comma then a minus sign then a space (,- ) next.
  • Print the name of the function being traced followed by a string representation of the argument in parentheses and a newline.
  • Next, increase the nesting level and call the function itself.
  • At the original nesting level, print a pipe symbol followed by a space (| ) for every level of nested function calls.
  • Print a backquote then a minus sign then a space (`- ).
  • Finally, print the string representation of the return value and a newline.
The return value of the function should be returned to the caller after all printing is complete.

When you are done, you should see the following behavior: 

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 handle exceptions nicely. If an exception occurs in the function, the nesting level must be adjusted to the appropriate level where the exception is caught.

Note: Scala reuses Java’s exception mechanism, so an exception is simply an object of type Throwable. See this for more info.

When you are done, you should get the following behavior: 

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)

(C) 20 points: Memoize

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 result for the given argument is already in the cache.

  • If so, the method should return the value the function returned when it was originally called with the given arguments.
  • If the function has not been called with the given argument, then call it, record the return value in the cache, and then return the value.

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

scala> 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 memo decorator so that it handles functions that throw exceptions. In particular,

  • extend the cache so that it stores whether the function returned a proper value or threw an exception. (Hint: You may want to use the Either type to keep track of this.)
  • extend the apply method so that if the call throws an exception, then the exception is stored in the cache (instead of the return value.)
  • extend the apply method so that if function is called with previously cached arguments, it should return the previous value if a proper value was returned, and it should throw the same exception that was thrown previously otherwise.

When you are done you should see the following behavior at the REPL: 

scala> 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)
    ...

Testing

When you have finished this entire problem, you can test your solution as follows: 

$ 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.

Note: When debugging the difference between your out file and decorators.out, you may find it helpful to run the following for a side-by-side comparison: 

$ vimdiff out decorators.out

Problem #3: Document Layout (Json.scala)

For this problem, you will write a simple document layout engine that allows nested documents to be printed cleanly.

A document is represented by an instance of the class: 

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
is represented as Doc(List("ruination", "whiterascal", "fattire")).

We have also provided implementations of methods for computing:

  • the height of a document (the number of lines)
  • the width of a document (the maximum number of characters in a line)
When all of the strings in a document have the same length (i.e. they all have length width), we refer to the document as a box document.

(A) 5 points: Padding

Fill in the definition of padBegin(xs, n, x) so that it returns:

  • the input list xs if the length of xs is greater than or equals to n; and
  • the input list xs padded with enough copies of x at the beginning to make the resulting list have length n.

When you are done, you should see the following behavior at the prompt. 

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)

scala> Doc.padBegin(List(1,2,3,4,5), 3, 0)
res: List[Int] = List(1,2,3,4,5)

(B) 5 points: More Padding

Fill in the definition of padEnd(xs, n, x), so that it behaves like padBegin except that any required padding is added at the end.

When you are done, you should see the following behavior at the prompt. 

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)

scala> Doc.padEnd(List(1,2,3,4,5), 3, 0)
res: List[Int] = List(1,2,3,4,5)

(C) 5 points: Left-Aligned Vertical Concat

Fill in the implementation of method vcat which, given the receiver (Doc) object and another Doc named that, returns a new box document that is the vertical concatenation of the receiver and that with the documents left-aligned.

When you are done, you should see the following behavior at the prompt. Note: The provided Doc.toString method prints square brackets around each line to make the string contents clear. 

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

scala> Doc("cat") vcat Doc("mongoose", "mouse")
res0: Doc = 
[cat     ]
[mongoose]
[mouse   ]

(D) 10 points: Top-Aligned Horizontal Concat

Next, fill in the implementation of method hcatT which, given the receiver (Doc) object and another Doc named that, returns a box new document that is the horizontal 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
res0: Doc = 
[1: cat     ]
[2: doggerel]
[3: moose   ]

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

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

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

(E) 10 points: Bottom-Aligned Horizontal Concat

Next, fill in the implementation of method hcatT hcatB which, given the receiver (Doc) object and another Doc named that, returns a new box document that is the horizontal 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
res5: Doc = 
[1: cat     ]
[2: doggerel]
[3: moose   ]

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

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

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

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

Testing

When you have both hcatT and vcat 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: JSON Rendering (Json.scala)

JavaScript Object Notation (JSON) 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.

We have defined a Scala class JVal to represent JSON values: 

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
Informally, a JVal is one of:
  • a base value of type String, or
  • a base value of type BigDecimal, or
  • an array of JVals, or
  • an object (i.e. dictionary) mapping String keys to JVals
In this problem, use the document formatter from the previous problem to convert JVals to pretty Docs, which can be shown as Strings in JSON format.

(A) 15 points: Rendering

Use the Doc formatting class defined above to fill in the definition of following function in JVal: 

def render(jv: JVal) : Doc

When you are done, you should see the following behavior at the prompt: 

scala> import JsonTest._

scala> JVal.render(jvReals(0))
res0: Doc = 
[{ fst : 1    ]
[, snd : cat }]

scala> JVal.render(jvReals(1))
res1: Doc = 
[{ fst : { fst : 1      ]
[        , snd : cat }  ]
[, snd : { fst : 1      ]
[        , snd : cat }  ]
[, thd : { fst : 1      ]
[        , snd : cat } }]

scala> JVal.render(jvReals(2))
res2: 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))
res3: Doc = 
[{ fst : 1                                            ]
[, snd : { fst : 2                                    ]
[        , snd : { fst : 3                            ]
[                , snd : { fst : 4                    ]
[                        , snd : { fst : 5            ]
[                                , snd : Nil } } } } }]

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

scala> JVal.render(jvReals(5))
res5: Doc = 
[[ 1  ]
[, 2  ]
[, 3  ]
[, 4 ]]

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

scala> JVal.render(jvReals(7))
res7: 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 }   ] }]
NOTE: The sample tests in Test.scala do not include the above examples.

OPTIONAL Problem #5: Serializiation (Json.scala)

NOTE: This problem will not be graded. It’s entirely up to you whether you want to get some experience working with a really cool feature of Scala.

It is rather tedious to write down JVals manually. Next, you will use Scala’s traits and implicits to automatically serialize Scala values (tuples, arrays, maps, and nested combinations thereof) into JSON values.

We have defined a trait 

trait Json { 
  def json: JVal
}
which represents values that are convertable to JVal (in Haskell parlance, Json is a typeclass). 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(x.json)
}
The write method takes any input of type A as long as A has an implicit view of of the Json trait, and converts it to a string. To do so, it uses the implicit .json method to obtain a JVal, which is then rendered as a String.

For example, to render some Scala values to JSON, just run: 

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

scala> 1.json
res5: JVal = JNum(1)

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

scala> (1,(2,(3,"Null"))).json
res9: JVal = JObj(Map(fst -> JNum(1),
                      snd -> JObj(Map(fst -> JNum(2),
                                      snd -> JObj(Map(fst -> JNum(3),
                                                      snd -> JStr(Null)
             ))))))
scala>
Assuming your render function from before is working properly, you should get: 
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 did not even define a JSON converter!!! Instead, Scala is composing the implicits for Int, String and (A, B) in a type-directed manner.

(A) 0 points: Converting Scala Triples

Using the definition of tup2Json for inspiration, fill in: 

implicit def
  tup3Json[A1 <% Json, A2 <% Json, A3 <% Json](p: (A1, A2, A3)) : Json
When you are done, you should see the following behavior at the prompt. 
scala> import Json._
scala> tup1.json 
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) 0 points: Converting Scala Lists

Next, fill in 

implicit def listJson[A <% Json](xs: List[A]) : Json
When you are done, you should see the following behavior at the prompt. 
scala> import Json._
scala> intl.json
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 }     }

(C) 0 points: Converting Scala Arrays

Next, fill in 

implicit def arrJson[A <% Json](xs: Array[A]) : Json
When you are done, you should see the following behavior at the prompt. 
scala> import Json._
scala> ints.json
res: JVal = JArr(List(JNum(1), JNum(2), JNum(3), JNum(4)))

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

(D) 0 points: Converting Scala Maps

Finally, fill in 

implicit def mapJson[A <% Json](m: Map[String, A]) : Json
When you are done, you should see the following behavior at the prompt. 
scala> import Json._
scala> mm.json
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 }     } }