CS220 Fall 2020 - Final Exam Solutions

2. Write the most general (possibly parametric) type signature for the following function:
let h = f => g => x => f(f(g))(g(x))
Solution: Let T be the type of x. Then g: T => R. Since f(g) is argument of f, but also has its result
type, f has the same argument and result type, that of g, T => R. In turn, since g(x) is of type R and
argument to f(f(g)), of type T => R, we have T = R. Thus, h has type
((T => T) => T => T) => (T => T) => T => T, with => being right-associative.

3. Write a function that takes a list whose elements are lists and produces a “flattened” list
with the elements of list 1, followed by those of list 2, etc.

function flatten(lls) {
function append(l1, l2) {
return l1.isEmpty() ? l2 : node(l1.head(),append(l1.tail(),l2));
}
return lls.isEmpty() ? lls : append(lls.head(),flatten(lls.tail()));
}
Comment: this is not tail-recursive. One could tail-recursively build the reverse, and reverse it.

4. 1. Write a function that takes an array `[a1, a2, …, an]`, a function `f`, and a thunk `st` for a
memoized stream, and returns the stream of values `f(a1), f(a2), …, f(an)`, followed by all
elements produced by `st`. The thunk `st` is of type `Memo>`, which would be
produced by a call like `memo0(() => somestream)`. Use `reduceRight()`, no loops.

let prepend = (a, f, st) => a.reduceRight((acc, e) =>
memo0(() => snode(f(e), acc)), st).get();

2. Write a function that takes an array of infinite streams, and returns a stream that
interleaves their values (all first values of all streams, then all second values, etc.)
You may use the function you wrote above, and `map()` for arrays. Use no loops.

let interall = a => prepend(a, s => s.head(),
memo0(() => interall(a.map(s => s.tail()))));

3. Write a function that takes an array of letters (one-character strings), and returns the
stream of all strings that can be formed with these letters, starting with the empty string
`""`. It should be possible to obtain any string with a finite number of `tail()` operations on
the produced stream.
Hint: Generate the strings ordered by length, and alphabetically for the same length.
Produce longer strings by appending a letter to each string of the stream. Use the
interleaving function you wrote above, and `map()` for streams. Use no loops.

let allstr = a => snode("", memo0(() =>
interall(a.map(sym => smap(allstr(a), str => str + sym)))));
5. Write a function that evaluates an expression, as given by parser.parseExpression(...).value.
Return Success(true) or Success(false) if the expression can be evaluated to a Boolean, using
short-circuit evaluation, and the only expression nodes accessed in this process are the
constants true and false, and the operators && and ||. Return Failure with an informative
message in any other case.
function booleval(e) {
switch(e.kind) {
case 'boolean': return new Success(e.value);
case 'operator': switch(e.op) {
case '&&': return booleval(e.e1).then(v =>
v ? booleval(e.e2) : new Success(false));
case '||': return booleval(e.e1).then(v =>
v ? new Success(true) : booleval(e.e2));
default: return new Failure('unknown operator ' + e.op);
}
default: return new Failure('unknown node ' + e.kind);
}
}
6. Write a class that supports both memoized evaluation of a function and communication of
newly computed values to subscribed observers. The constructor of this class should have two
arguments, `f` and `n`, where `f` is a function that takes a natural number as argument, and `n`
is the number of values to memoize, from `f(0)` to `f(n-1)`.
The class should have a method `get(k: number)`, returning `f(k)`, and a `subscribe` method
with the semantics seen for the Observables design pattern.
class MemoFun {
constructor(f, n) {
let arr = [];
for (let i = 0; i < n; ++i) { arr.push({ eval: false }); }
let observers = [];
this.get = function(i) {
if (0 <= i && i < n) {
if (!arr[i].eval) {
arr[i] = { eval: true, v: f(i) }
this.update(arr[i].v);
}
return arr[i].v;
} else {
let v = f(i);
this.update(v);
return v;
}
}
this.subscribe = func => observers.push(func);
this.update = val => observers.forEach(func => func(val));
}
}

7. Write a function that performs multiplication of two natural numbers, working on their
binary representations.
Fill in the code skeleton given below, and argue correctness based on writing invariants and
assertions:

function bitmul(a, b) {
let x = a;
let y = b;
let r = 0;
// invariant: r + x * y = a * b
// initially: 0 + a*b = a*b
while (y > 0) { // y is the loop variant for termination
// y = 2*(y/2) + y % 2, or y = 2 * (y >> 1) + (y & 1)
// r + x * (2*(y/2) + y % 2) = a * b
if ((y & 1) > 0) { r += x; }
// r + x * (2*(y/2)) = a * b
y = y >> 1; // y strictly decreases, so loop terminates
x = x << 1;
// r + x * y = a * b (invariant reestablished)
}
// r + x * y = a * b && y = 0 => r = a * b
return r;
}

欢迎咨询51作业君