def partition(xs, key):
    """Split xs by key, returning a list of matching elements and
    a list of non-matching elements.

    xs -- list -- items to partition

    key -- f(x) -> bool -- partitioning function

    returns -- (list, list) -- matches & non-matches
    """
    matches, not_matches = [], []
    for x in xs:
        (matches if key(x) else not_matches).append(x)
    return matches, not_matches