display is useful for seeing the intermediate results of a function as it runs. It's tiresome to clutter our programs with calls to display, though. A way to log the inputs and outputs of a function would be nice.
Define the function debug1, which takes a function argument f and returns a function that, when called, writes its input and output to the console, and returns the same thing f would have when called. In other words, the type of debug1 is (x -> y) -> (x -> y).
function debug1(f) {
// ?
}
function fact(n) {
return n === 0 ? 1 : n * fact(n-1);
}
var fact_debug = debug1(fact);
// Console output
10:48:01 PM fact_debug(5);
10:48:01 PM <- 5
10:48:01 PM -> 120
10:48:01 PM 120This isn't very useful yet, though. What would be nice is if we could see the input and output of every recursive call of fact. How can we modify fact so the following appears?
10:52:06 PM fact_debug(5);
10:52:06 PM <- 5
10:52:06 PM <- 4
10:52:06 PM <- 3
10:52:06 PM <- 2
10:52:06 PM <- 1
10:52:06 PM <- 0
10:52:06 PM -> 1
10:52:06 PM -> 1
10:52:06 PM -> 2
10:52:06 PM -> 6
10:52:06 PM -> 24
10:52:06 PM -> 120
10:52:06 PM 120debug1 is a special case of another higher-order function, decorate1, which abstracts out what happens before the function is called and after. It's a bit verbose to describe, but how it's used is in the following examples. Its type is (a -> b, c -> d) -> (b -> c) -> a -> d (!).
function in(x) {
display("<- " + x);
return x;
}
function out(x) {
display("-> " + x);
return x;
}
function decorate1(before, after) {
// ?
}
var debug1 = decorate1(in, out);
function fact(n) {
return n === 0 ? 1 : n * fact_debug(n - 1);
}
var fact_debug = debug1(fact);
fact_debug(5);
// The same stuff appears in the console as beforeDefine the function take, which returns a prefix of a list.
take(2, list(1, 2, 3)); // list(1, 2)Define the function drop, which returns a suffix of a list by dropping the first n elements.
drop(2, list(1, 2, 3)); // list(3)Define the function last, which returns the last element of a list.
last(list(1, 2, 3)); // 3Define the function init, which all but the last element of a list.
init(list(1, 2, 3)); // list(1, 2)Define the function replace_n, which takes three arguments: x, n, and a list. It replaces the nth element of the list with x.
replace_n("hello", 1, list(1, 2, 3)); // list(1, "hello", 3)Define the function insert_into, which takes three arguments: x, n, and a list. It inserts x at the nth position of the list, shifting the following elements back.
insert("hello", 2, list(1, 2, 3)); // list(1, 2, "hello", 3)Define the function splice, which takes three arguments: index, count, and a list. It returns count elements of the list, starting from index.
splice(3, 0, list(1,2,3,4)); // []
splice(0, 1, list(1,2,3,4)); // list(1)
splice(1, 2, list(1,2,3,4)); // list(2, 3)
splice(1, 7, list(1,2,3,4)); // list(2, 3, 4)Define the function partition, which partitions a list into two halves: the first consisting only of elements which satisfy a given predicate, and the second containing those which don't. It returns a pair of lists.
partition(even, list(1,2,3,4)); // pair(list(2, 4), list(1, 3))Redefine all these with accumulate.
We've seen how we can remove one level of nesting from a list, 'flattening' it, using accumulate and append. Can we generalise this so it removes all nesting from a given list?
Write the function flatten, which flattens an arbitrarily-nested list into one with no nesting at all.
flatten(list(1, 2, list(3, list(4, list(5))), list(6)));
// list(1, 2, 3, 4, 5, 6)Disregarding punctuation marks, an English sentence is simply a collection of words, each word being a sequence of letters. Suppose we'd like to represent words and sentences as JediScript lists. A word would be a JediScript list of characters (defined as single-letter strings) and a sentence would be a list of words.
// "I am rich"
list(list("I"), list("a", "m"), list("r", "i", "c", "h"));
// "JediScript is cool"
list(list("J", "e", "d", "i", "S", "c", "r", "i", "p", "t"),
list("i", "s"),
list("c", "o", "o", "l"));Write a function count_in_sentence that takes a sentence as represented above and returns a list with two elements: the number of words in the sentence, and the number of characters in the sentence. Assume that spaces count as one character per space, and that there is exactly one space between each word (but none at the start or end of the sentence). There is one period character at the end of each sentence.
count_in_sentence(list(list("I"),
list("l", "i", "k", "e"),
list("p", "i", "e")));
// returns list(3, 11)Write a function most_frequent_letters that takes a sentence and returns a list of letters that occur most frequently in the given sentence. If only one such letter exists, return a list with one element. When counting, treat upper and lower case letters to be equal, and only return lower case letters, using the function to_lower_case (you may use this function as a black box).
function to_lower_case(letter) {
return letter.toLowerCase();
}
most_frequent_letters(list(list("S", "h", "e"),
list("l", "i", "k", "e", "s"),
list("p", "i", "e", "s")));
// returns list("e", "s")Write a function find_end_with that takes a sentence and an additional list of letters. The function should return a list of words from the given sentence that end with the given sequence of letters.
find_end_with(list(list("I"),
list("a", "m"),
list("s", "a", "m")),
list("a", "m"));
// returns list(list("a", "m"), list("s", "a", "m"))Pig Latin is an English-language game where ordinary words are encoded into peculiar, foreign-sounding equivalents. Here are some example words and their Pig Latin versions:
apple - appleway
noodles - oodlesnay
programming - ogrammingpray
While variants of the rules of encoding exist, we will adopt a simple version as follows:
- For words beginning with a vowel, add
wayat the end of the word. - For words beginning with consonant(s), bring all consonants at the front of the word to the back, then add
ay.
Write a function that takes a list-sentence and returns its pig latin equivalent.
pig_latin(list(list("t", "e", "a"),
list("i", "s"),
list("n", "i", "c", "e")));
// returns list(list("e", "a", "t", "a", "y"),
// list("i", "s", "w", "a", "y"),
// list("i", "c", "e", "n", "a", "y"))We've seen how to write list-processing functions like map and filter in terms of accumulate:
function map(f, xs) {
return accumulate(function(c, t) {
return pair(f(c), t);
}, [], xs);
}
function filter(pred, xs) {
return accumulate(function(c, t) {
if (pred(c)) {
return pair(c, t);
} else {
return t;
}
}, [], xs);
}This works well, but we can't compose these operations on lists much without curry2 or nesting.
Notice that the only thing that changes when calling accumulate is the function we pass it. What if we were able to compose a series of functions expressing what it means to map or filter in terms of what accumulate expects, then pass that to accumulate? That would give us a greater degree of flexibility.
We call the function that we pass to accumulate a reducing function. It is of the form (a, b) -> b. For example, pair is a reducing function: it takes an item and a list of items, and returns a list of items.
Define the function mapper, which takes a function f and returns a reducing function that, when used with accumulate, maps f over a list. After that define filterer, which takes a predicate and returns its corresponding reducing function.
function even(x) {
return x % 2 === 0;
}
function inc(x) {
return x + 1;
}
accumulate(mapper(inc), [], list(1, 2, 3, 4)); // list(2, 3, 4, 5)
accumulate(filterer(even), [], list(1, 2, 3, 4)); // list(2, 4)This is more general, but we still can't compose these functions. Let's extract out the means of combination as well.
Define the functions mapping and filtering such that these work:
var reduction = mapping(inc);
accumulate(reduction(pair), [], list(1, 2, 3, 4)); // list(2, 3, 4, 5)
var reduction2 = filtering(even);
accumulate(reduction2(pair), [], list(1, 2, 3, 4)); // list(2, 4)In other words, mapping and filtering take f and a predicate respectively and return a function. This new function takes the means of combination and returns a reducing function.
We are currently using pair as a means of combination. Notice that pair has the same signature as a reducing function. This means that we could actually use a reducing function as a means of combination, which turns out to be really powerful!
The functions that mapping and filtering return are called transducers. They take a reducing function and return another reducing function. Whatever they return can then be used with accumulate. We can compose a series of transducers, then pass in a final reducing function at the end, which will serve as a means of combination.
Define the transducer t so that accumulating with it produces the following results. You should make use of compose, mapping, and filtering.
var t = compose(/* your answer here */);
accumulate(t(pair), [], list(1, 2, 3, 4)); // list(3, 5)
accumulate(t(plus), 0, list(1, 2, 3, 4)); // 8As a consequence of extracting out the means of combination, we have separated the transformations we perform on a list from the resulting structure, allowing us to break lists apart and put them together in more flexible ways.
We have seen how abstraction lets us separate interface from representation. Data can be representated in many ways, but that doesn't matter as long as we know how to operate on it.
For example, we may represent a list using a function.
function make_difflist(lst) {
return function(r) {
return append(lst, r);
};
}
var a = make_difflist(list(1, 2, 3));This representation is called a difference list.
Define the function difflist_to_list, which takes a difference list and converts it into a list.
difflist_to_list(a); // list(1, 2, 3)Define the functions empty_difflist, which takes no arguments and returns an empty difference list, and is_empty_difflist, which checks if its argument is an empty difference list.
var empty = empty_difflist();
is_empty_difflist(empty); // true
is_empty_difflist([]]); // false
is_empty_difflist(1); // falseDefine the function append_difflist, which takes two difference lists and joins them into a new difference list. append_difflist should work correctly with empty difference lists.
var a = make_difflist(list(1, 2, 3));
var b = make_difflist(list(4, 5, 6));
var c = append_difflist(a, b);
difflist_to_list(c); // list(1, 2, 3, 4, 5, 6)pair_difflist can then defined in terms of append_difflist.
Difference lists are surprisingly useful in certain situations. What is fundamentally different about lists and difference lists? Having answered that, write a function that operates on lists, and that has different time complexity when a difference list is used instead.