from typing import Iterable
from typing import Callable
from typing import Tuple
from typing import List
import itertools


def partition(items: Iterable, predicate: Callable) -> Tuple[List, List]:
    """
    :param items: iterable of items to split
    :param predicate: predicate to split by
    :return: a tuple of lists, first list does not satisfy the predicate, second list does
    """
    a, b = itertools.tee((predicate(item), item) for item in items)
    return ([item for pred, item in a if not pred],
            [item for pred, item in b if pred])