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));
}