CS1101S Studio S6 (T08C)

Problem Solving and List Processing

Question 1

Write the function map using accumulate. Name your function my_map.

function my_map(f, xs) {
    return accumulate((x, y) => pair(f(x), y) , null, xs);
}

Question 2

Write a function called remove_duplicates that takes in a list as its only argument and returns a list with duplicate elements removed. The order of the elements in the returned list does not matter. Use filter in your function.

function remove_duplicates(lst) {
    return length(lst) === 0
        ? null 
        : pair(head(lst), remove_duplicates(filter(x => x !== head(lst),tail(lst))));
}

Question 3

Our friend Louis Reasoner has a pocket full of change. He wants to buy a snack that will cost him x cents, and he wants to know all the ways in which he can use his change to make up that amount. Please help him in writing a function which takes as parameters the amount x and a list of all the coins Louis has in his pocket, and returns a list of lists, such
that each sub-list of the result contains a valid combination to make up x. A combination may appear more than once, since it may be using different coins of the same denomination. Help Louis by filling in the ellipses ... in his incomplete solution:

function makeup_amount(x, coins) {
    if (x === 0) {
        return list(null);
    } else if (x < 0 || is_null(coins))  {
        return list();
    } else {
        // Combinations that do not use the head coin.
        const combi_A = makeup_amount(x, tail(coins));
        // Combinations that do not use the head coin
        // for the remaining amount.
        const combi_B = makeup_amount(x - head(coins),                         tail(coins));
        
        // Combinations that use the head coin.
        const combi_C = map(x => pair(head(coins), x), combi_B);
        
        return append(combi_A, combi_C);
    }
}

Bonus Round

Question 1

Write a function called remove_duplicates that takes in a list as its only argument and returns a list with duplicate elements removed. The order of the elements in the returned list does not matter. Use accumulate in your function.

Question 2

In this question, lists represent sets. Each element of the set appears exactly once in its list representation, and the order does not matter. So the list list(1, 2, 3) represents the same set as the list list(3, 2, 1).

In this question, you are supposed to compute all subsets of a given set. Your function subsets takes as argument a list, representing the given set, and needs to return a list of lists, each representing a unique subset of the given set.

Question 3

A permutation of a list s is a list with the same elements as s, but in a possibly different order. For example, the list list(3,1,2) is a permutation of list(1,2,3). Write a function permutations that takes a list s as argument and returns a list of all permutations of s.