let rec select f k list =
  match list with
    | [] -> ([], [])
    | pivot::rem ->
      let (b, a) = partition (f pivot) rem in
      let len = length a in
      if len = k
      then (a, pivot::b)
      else if len < k
      then
        let (b1, b2) = select f (k - (len+1)) b in
        ((append a (pivot::b1)), b2)
      else (* len > k *)
        let (a1, a2) = select f k a in
        (a1, append b (pivot::a2))