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 append(list1, list2):
    return (list2 if is_none(list1)
            else pair(head(list1), append(tail(list1), list2)))
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 decode(bits, tree):
    def decode_1(bits, current_branch):
        if is_none(bits):
            return None
        else:
            next_branch = choose_branch(head(bits),
                                        current_branch)
            return (pair(symbol_leaf(next_branch),
                         decode_1(tail(bits), tree))
                    if is_leaf(next_branch)
                    else decode_1(tail(bits), next_branch))
    return decode_1(bits, tree)

def choose_branch(bit, branch):
    return (left_branch(branch)
            if bit == 0
            else right_branch(branch)
            if bit == 1
            else error("bad bit -- choose_branch", bit))

my_leaf_1 = make_leaf("A", 8)
my_leaf_2 = make_leaf("B", 3)

my_tree = make_code_tree(my_leaf_1, my_leaf_2)

print(tail(decode(llist(0, 1, 1, 0), my_tree)))

# expected: [ 'B', [ 'B', [ 'A', None ] ] ]
