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

sample_tree = make_code_tree(
                  make_leaf("A", 4),
                  make_code_tree(
                      make_leaf("B", 2),
                      make_code_tree(
                          make_leaf("D", 1),
                          make_leaf("C", 1))))
sample_frequencies = llist(llist("A", 4),
                           llist("B", 2),
                           llist("C", 1),
                           llist("D", 1))

print(sample_tree
      == generate_huffman_tree(sample_frequencies))

# expected: True
