def make_table():
    return llist("*table*")
def lookup(key, table):
    record = assoc(key, tail(table))
    return (None
            if is_none(record)
            else tail(record))

def assoc(key, records):
    return (None
            if is_none(records)
            else head(records)
            if key == head(head(records))
            else assoc(key, tail(records)))
def insert(key, value, table):
    record = assoc(key, tail(table))
    if is_none(record):
        set_tail(table,
                 pair(pair(key, value), tail(table)))
    else:
        set_tail(record, value)
    return "ok"
def memoize(f):
    table = make_table()
    def memoized(x):
        previously_computed_result = lookup(x, table)
        if is_none(previously_computed_result):
            result = f(x)
            insert(x, result, table)
            return result
        else:
            return previously_computed_result
    return memoized
memo_fib = memoize(lambda n: (0
                              if n == 0
                              else 1
                              if n == 1
                              else memo_fib(n - 1) +
                                   memo_fib(n - 2)))

print(memo_fib(5))

# expected: 5
