Recitation 7: Parametric data and visitors
Goals: Practice implementing the visitor pattern and using generics in a novel class.
Goals:
Getting started
// Represents functions of signature A -> R, for some argument type A and // result type R interface IFunc<A, R> { R apply(A input); } // generic list interface IList<T> { // map over a list, and produce a new list with a (possibly different) // element type <U> IList<U> map(IFunc<T, U> f); } // empty generic list class MtList<T> implements IList<T> { public <U> IList<U> map(IFunc<T, U> f) { return new MtList<U>(); } } // non-empty generic list class ConsList<T> implements IList<T> { T first; IList<T> rest; ConsList(T first, IList<T> rest) { this.first = first; this.rest = rest; } public <U> IList<U> map(IFunc<T, U> f) { return new ConsList<U>(f.apply(this.first), this.rest.map(f)); } }
To begin, implement the equivalent of foldr from ISL on IList<T>s. What new types will you need?
Write a test that sums a list of numbers using your foldr method.
Let there be JSON
JSON is an industry-standard data structure that allows for the storage and sharing of tree-shaped data. Below is a definition of a subset of JSON (more will come later). A JSON can either be a blank value, a number, boolean, or string. In the real world, JSON numbers can have decimal values, but for our purposes we’ll stick to integers.
// a json value interface JSON {} // no value class JSONBlank implements JSON {} // a number class JSONNumber implements JSON { int number; JSONNumber(int number) { this.number = number; } } // a boolean class JSONBool implements JSON { boolean bool; JSONBool(boolean bool) { this.bool = bool; } } // a string class JSONString implements JSON { String str; JSONString(String str) { this.str = str; } }
Implement the JSONVistor<T> interface, which is a IFunc<JSON, T> and follows the visitor pattern over JSONs.
Define a JSONToNumber visitor, which coverts a JSON to its number value. Blanks are converted to 0, booleans 0 or 1 depending on if the value is false or true, strings their length, and numbers their value.
Map over a list of JSON and produce all of their numbers as a test.
What’s data without a little self-reference?
As the definition for JSON stands in our current form, it’s not very useful. After all, it doesn’t allow for our favorite type of data: lists! Let’s extend the definition to allow for them.
//a list of JSON values class JSONList implements JSON { IList<JSON> values; JSONList(IList<JSON> values) { this.values = values; } }
Extend the visitor pattern on JSONs as needed.
A JSONList’s value is the sum of all of its sub-values converted to their number value. Extend JSONToNumber as needed.
Do a sanity check: does your JSON interface have anything other than an accept method? If so, you have likely not implemented the visitor pattern correctly. Ask a staff member for further clarification. If not, continue onwards.
Finders, keepers
Implement an IPred<T> interface, which is a function that always returns a boolean. Be sure to extend it with the proper interface.
Design the findSolutionOrElse method on IList<T>’s, which has the following header: <U> U findSolutionOrElse(IFunc<T, U> convert, IPred<U> pred, U backup). It finds the first element in the list where the result of function applied to that element passes the predicate, and then returns that result. If no such element is found, backup is returned.
JSON: The whole shebang
What does this remind you of? What does JSON stand for anyways?
// a list of JSON pairs class JSONObject implements JSON { IList<Pair<String, JSON>> pairs; JSONObject(IList<Pair<String, JSON>> pairs) { this.pairs = pairs; } } // generic pairs class Pair<X, Y> { X x; Y y; Pair(X x, Y y) { this.x = x; this.y = y; } }
Extend the visitor pattern on JSONs as needed.
Define a JSONObject’s numeric value is the sum of all of the values of its sub-JSON components; the string keys are ignored. Extend JSONToNumber as needed.
Define a JSONFind visitor, which is constructed with a string and returns the first JSON value it finds in a pair with that string as the keyword. If no such element can be found, return a JSONBlank. Hint: In order to know whether to continue searching, you’ll need to know if your current value is blank or not. You may wish to use instanceof here, and we will allow it here, though there are cleaner solutions... but we have not encountered the Java concepts necessary for them yet.
JSON: Flattened edition
Design a visitor, JSONFlatten, which flattens a JSON to a list of pairs of its atomic elements and the path needed to get there. For example, if we had the following JSON object (written in JSON notation):
{ "bizz": "buzz", "foo": false, "abc": [null, {"efg": 42}] }
we would want to produce an IList<Pair<String, JSON>> with these elements, in this order:
new Pair<String, JSON>("bizz", new JSONString("buzz")); new Pair<String, JSON>("foo", new JSONBool(false)); new Pair<String, JSON>("abc-0", new JSONBlank()); new Pair<String, JSON>("abc-1-efg", new JSONNumber(42));