def split(list, index):
    """
    Split the given list into two sublists at the given index and return
    both sublists.  The first sublist should contain items at index 0
    through `index - 1`, and the second sublist should contain the items
    at index `index` through the end.  If the given index is too high,
    return `(list, ())`.
    """
    if index <= 0:
        return ((), list)
    elif list == ():
        return ((), ())
    else:
        head, tail = list
        sub1, sub2 = split(tail, index - 1)
        return ((head, sub1), sub2)