13th_Sept_list_and_trees_4_tree

// trees

// a tree of a certain data type is a list whose elements are of that data typew
// or trees of that data type

// tree of numbers:
// const treeA = list(1,2,3,4)
// const treeB = list(list(1,2), list(3,4))
// const treeC = null; // can be a tree of anytype - basically empty tree of anytype

// const treeD = list(list(1,2), null, 3, list(4, null));
// still a tree of numbers^

// cannot have a tree of nulls or a tree of pairs since they are not data types as such

// the root of top lol: eg
// [[1,[2,null]],3,4]
// first root out 3 and 4 and then further another branch for 1 and 2

// alternative definition of trees in terms of pairs - see slides

/*

A tree of a certain data type is
    either null
    or a pair
        - whose tail is a tree of that data type and
        - whose head is
            – either of that data type
            – or a tree of that data type

*/

// counting data items in a tree

// if list is empty return 0
// add number of items in head to number of items in tail


// if head is a tree/list we count
// if not, its a data item and we add 1


function count_data_items(tree){
    return is_null(tree)
        ? 0
        : (is_list(head(tree)) ? count_data_items(head(tree)) : 1)
        +
        count_data_items(tail(tree));
}



// scale a tree

// tree is still a list with some additional conditions
// map function may help


// mapping over trees

function map_tree(f, tree){
    
    return map(sub_tree => 
                    ! is_list(sub_tree)
                    ? f(sub_tree)
                    : map_tree(f, sub_tree));
    
}

function scale_tree(tree, k) {
    return map_tree(data_item => data_item * k, tree);
}