---
tags: cs1101s
---

# CS1101S Studio S5 (T08C)

## Data Abstractions

### Question 1
Draw box-and-pointer for the values of the following expressions. Also give box and list notation.

list(list(1, 2, list(3)), list(4, 5), pair(6, 7));

pair(1, list(2, 3, pair(4, null)));

pair(1, pair(2, list(3, list(4, 5))));

### Question 2
Examine the following (incorrect) `reverse` function:

function reverse(lst) {
    return is_null(lst)
        ? null
        : pair(reverse(tail(lst)), head(lst));
}

Draw the box-and-pointer diagram, box notation and list notation for the result returned by the following function call:

reverse(list(1, 2, 3, 4));

### Question 3
Write expressions using `lst`, `head` and `tail` that will return 1 when the `lst` is bound to the following values:

list(7, list(6, 5, 4), 3, list(2, 1));

list(list(7), list(6, 5, 4), list(3, 2), 1);

list(7, list(6), list(5, list(4)), list(3, list(2, list(1))));

list(7, list(list(6, 5), list(4), 3, 2), list(list(1)));

## Bonus Round

### Question 1
The function `list_ref` can be applied to a list `xs` and a number `n`, and returns the `n`-th element of the list, starting counting at 0. So `list_ref(list(1, 2, 3), 2)` evaluates to 3. The position of an element in the list is called its *rank*; we say that the number 3 has rank 2 in the list. Write a Source function called `every_second` that takes a list as its only argument and returns a list containing all the elements of odd rank (i.e. every second element) from the input list.

function every_second(items) {
return (is_null(items)) || (is_null(tail(items))) 
        ? null 
        : pair(head(tail(items)),                 every_second(tail(tail(items))));
}

### Question 2
Write a Source §2 function called `sums` that takes a **list of numbers** as its only argument and returns a **list of numbers**, containing two elements: the first is the sum of all even-ranked numbers in the input list (ranks 0, 2, 4 etc), whereras the second element is the sum of all odd-ranked elements in the input list (ranks 1, 3, 5 etc).

function sums(list_of_numbers) {
    const even_list = every_second(pair("empty", list_of_numbers));
    const odd_list = every_second(list_of_numbers);
    return list(accumulate((x, y) => x + y, 0, even_list),
                accumulate((x, y) => x + y, 0, odd_list));
}

function every_odd(items){
    function every_2(n){
        return n > length(items) - 1
            ? null 
            : pair(list_ref(items,n),every_2(n+2));
    }
    return every_2(0);
}

function every_second(items){
    function get_element(list, n){
        return is_null(list)
            ? null
            : n % 2 === 1
                ? pair(head(list), get_element(tail(list),n + 1))
                : get_element(tail(list), n + 1);
        
    }
    
    return get_element(items, 0);
}

function sums(list){
    const accum_even = accumulate((x,y) => x + y, 0 ,every_second(list));
    const accum_odd = accumulate((x,y) => x + y, 0 ,every_odd(list));
    return pair(accum_even,pair(accum_odd,null));
}