def length(items):
    return (0 if is_none(items)
            else 1 + length(tail(items)))
def append(list1, list2):
    return (list2 if is_none(list1)
            else pair(head(list1), append(tail(list1), list2)))
def make_leaf(symbol, weight):
    return llist("leaf", symbol, weight)
def is_leaf(object):
    return head(object) == "leaf"
def symbol_leaf(x): return head(tail(x))

def weight_leaf(x): return head(tail(tail(x)))
def left_branch(tree): return head(tail(tree))

def right_branch(tree): return head(tail(tail(tree)))

def symbols(tree):
    return (llist(symbol_leaf(tree))
            if is_leaf(tree)
            else head(tail(tail(tail(tree)))))
def weight(tree):
    return (weight_leaf(tree)
            if is_leaf(tree)
            else head(tail(tail(tail(tail(tree))))))
def make_code_tree(left, right):
    return llist("code_tree", left, right,
                 append(symbols(left), symbols(right)),
                 weight(left) + weight(right))
def adjoin_set(x, set):
    return (llist(x)
            if is_none(set)
            else pair(x, set)
            if weight(x) < weight(head(set))
            else pair(head(set), adjoin_set(x, tail(set))))
def make_leaf_set(pairs):
    if is_none(pairs):
        return None
    else:
        first_pair = head(pairs)
        return adjoin_set(
                   make_leaf(head(first_pair),        # symbol
                             head(tail(first_pair))), # frequency
                   make_leaf_set(tail(pairs)))
# successive_merge function to be written by student
def generate_huffman_tree(pairs):
    return successive_merge(make_leaf_set(pairs))
def successive_merge(leaves):
    return (head(leaves)
            if length(leaves) == 1
            else successive_merge(
                     adjoin_set(
                         make_code_tree(head(leaves),
                                        head(tail(leaves))),
                         tail(tail(leaves)))))
def member(item, x):
    return (None if is_none(x)
            else x if item == head(x)
            else member(item, tail(x)))
def encode_symbol(symbol, tree):
    def contains_symbol(symbol, current_tree):
        return not is_none(member(symbol, symbols(current_tree)))
    if is_leaf(tree):
        return None
    else:
        left_tree = left_branch(tree)
        right_tree = right_branch(tree)
        return (pair(0, encode_symbol(symbol, left_tree))
                if contains_symbol(symbol, left_tree)
                else pair(1, encode_symbol(symbol, right_tree))
                if contains_symbol(symbol, right_tree)
                else error("symbol not found -- encode_symbol"))
# encode_symbol function to be written by students
def encode(message, tree):
    return (None
            if is_none(message)
            else append(encode_symbol(head(message), tree),
                        encode(tail(message), tree)))
lyrics_frequencies = llist(llist("A", 2),
                           llist("NA", 16),
                           llist("BOOM", 1),
                           llist("SHA", 3),
                           llist("GET", 2),
                           llist("YIP", 9),
                           llist("JOB", 2),
                           llist("WAH", 2))
lyrics_tree = generate_huffman_tree(lyrics_frequencies)
lyrics = llist(
    "GET", "A", "JOB",
    "SHA", "NA", "NA", "NA", "NA", "NA", "NA", "NA", "NA",
    "GET", "A", "JOB", "SHA", "NA", "NA", "NA", "NA", "NA",
    "NA", "NA", "NA", "WAH", "YIP", "YIP", "YIP", "YIP",
    "YIP", "YIP", "YIP", "YIP", "YIP", "SHA", "BOOM"
   )

print(length(encode(lyrics, lyrics_tree)))
# 84

# expected: 84
