---
tags: cs1101s
---

# CS1101S Studio S5 (T05J)

## Data Abstractions

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

ans here

### 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:

## In Class

### 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_FUN_second(list) {
    function iter(list,n) {
        return n > (length(list) - 1)
               ? null
               : pair(list_ref(list, n), iter(list, n+2));
    
    }
    return iter(list, 1);
}

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

### Before Question 2
Write a sum function that takes in a list as an argument and returns the sum of the elements in the list.

function sum(n) {
    function fun(n) {
        return is_null(n)
               ? 0
               : head(n) + fun(tail(n));        
    }
    return list(fun(every_second(n)), fun(every_first(n)));
} 

Write an iterative version of the sum function that takes in a list as an argument and returns the sum of the elements in the list.

### 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 sum(items){
    function summer(a, b, items){
        return is_null(items)
            ? pair(a,pair(b, null))
            : is_null(tail(items))
            ? summer(a + head(items), b, null)
            : summer(a + head(items), b + head(tail(items)), tail(tail(items)));
    }
    return summer(0,0, items);
}

James
function sums(items){
    
    function helper_even(items){
        return is_null(items) || is_null(tail(items))
        ? 0
        : head(tail(items)) + helper_even(tail(tail(items)));
    }
    
    function helper_odd(items){
        return is_null(items) || is_null(tail(items)) 
        ? 0
        : head(items) + helper_odd(tail(tail(items)));
    }
    
    return list(helper_odd(items),helper_even(items))

}

AI LIN 
function sums2(items) {
    
    function sum(items) {
        return length(items) <= 1
            ? 0
            : list_ref(items, 1) + sum(tail(tail(items)));
        
    }
    
    return pair(sum(items), list(sum(pair(1, items))));
}

sums(list(1,10,1,10,1,10));