def partition(lis, predicate):
  """
  Splits a list into two lists based on a predicate. The first list will contain
  all elements of the provided list where predicate is true, and the second list
  will contain the rest
  """
  as_list = list(lis)
  true_list = []
  false_list = []
  for l in as_list:
    pred_value = predicate(l)
    if pred_value is True:
      true_list.append(l)
    elif pred_value is False:
      false_list.append(l)
    else:
      raise Exception("Invalid predicate")

  return true_list, false_list