13th_Sept_list_and_trees_2

// append

// wanted: append(list(1,2,3), list(4,5,6)) -> list(1,2,3,4,5,6)

// attempt 1

const append1 = pair;

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

// not our desired result

// attempt 2

// if list1 is empty, we return list2 -> strategy
// append the tail of list 1 to list 2
// form a pair of the head and the result


function append2(xs, ys){
    return is_null(xs)
        ? ys
        : pair(head(xs), append2(tail(xs), ys));
}

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

// order of growth in time - theta(n) - ength of xs only cause we only traverse through xs
// order of growth in space - theta(n)

// number of deferred operations is n
// but here we have data structures
// everytime we call the pair function, we need space in memory -> even if it is iterative
// so n more spaces for creating the boxes
// theta(2n) which is basically theta(n) cause the constant doesnt matter


// reverse attempt 1 - in studio sheet 5

// reverse attempt 2

function reverse2(lst){
    return is_null(lst)
        ? null 
        : append(reverse2(tail(lst)), list(head(lst)));
}

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

// run time - n + (n-1) + (n-2)....(for every tail we take) -> n(n-1)/2 -> theta(n^2)
// not theta(n^2/2 - n/2) because we 
// space: ?


// third attempt to make it more efficient

function reverse3(xs){
    function rev(original, reversed){
        return is_null(original)
            ? reversed
            : rev(tail(original),
            pair(head(original), reversed));
        
        
    }
    
    return rev(xs, null);
}

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

// time -> theta(n) due to pair
// space -> theta(n) due to pair