let partition xs ~f =
  let pos_queue = Queue.create ()
  and neg_queue = Queue.create () in

  let rec pos i =
    match Queue.dequeue pos_queue with
    | None -> (
      match next xs with
      | Some x when not (f x) -> Queue.enqueue neg_queue x ; pos i
      | e -> e
    )
    | e -> e

  and neg i =
    match Queue.dequeue neg_queue with
    | None -> (
      match next xs with
      | Some x when f x -> Queue.enqueue pos_queue x ; neg i
      | e -> e
    )
    | e -> e
  in
  from pos, from neg