---
tags: cs1101s
---

# CS1101S Studio S6 (T05J)

## Problem Solving and List Processing

### Question 1
Write the function `map` **using `accumulate`**. Name your function `my_map`.

//Seeu Sim
function my_map(f, xs){
    return accumulate((x, y) => pair(f(x), my_map(f, tail(xs))), 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.**

// Ai Lin :D
function remove_duplicates(lst) {
    return is_null(lst)
        ? null
        : pair(head(lst), 
        remove_duplicates(filter(x => !equal(head(lst), x), 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 null;
    } else {
        // Combinations that do not use the head coin.
        const combi_A = ...
        // Combinations that do not use the head coin
        // for the remaining amount.
        const combi_B = ...
        
        // Combinations that use the head coin.
        const combi_C = ...
        
        return append(combi_A, combi_C);
    }
}

function makeup_amount(x, coins) {
    if (x === 0) {
        return list(null);
    } else if (x < 0 || is_null(coins)) {
        return null;
    } else {
        
        const combi_A = makeup_amount(x, tail(coins));
        
        const combi_B = makeup_amount(x - head(coins), tail(coins));
        
        // const combi_C = map(m => append(list(head(coins)), m), combi_B);
        const combi_C = map(m => pair(head(coins), m), 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.

function subsets(xs) {
    if (is_null(xs)) {
        return list(null);
    } else {
        const A = subsets(tail(xs));
        
        const B = map(x => pair(head(xs), x), A);
        
        return append(A, B);
    }
}
subsets(list(1,2,3));

### 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*.

function permutations(xs) {
    if (is_null(xs)) {
        return list(null);
    } else {
        const list_of_lists = 
            map(x => map(y => 
                pair(x,y)
            , permutations(remove(x, xs)))
            ,xs);
        return accumulate(append, null, list_of_lists);
    }
}