Linked list partition function and reversed results

Solution 1:

Here's a continuation-based version. It's tail-recursive and returns the list in the original order.

let partitionWhileCps c l =
  let rec aux f = function
    | h::t when c h -> aux (fun (acc, l) -> f ((h::acc), l)) t
    | l -> f ([], l)
  aux id l

Here are some benchmarks to go along with the discussion following Brian's answer (and the accumulator version for reference):

let partitionWhileAcc c l =
  let rec aux acc = function
    | h::t when c h -> aux (h::acc) t
    | l -> (List.rev acc, l)
  aux [] l

let test = 
  let l = List.init 10000000 id
  (fun f ->
    let r = f ((>) 9999999) l
    printfn "%A" r)

test partitionWhileCps // Real: 00:00:06.912, CPU: 00:00:07.347, GC gen0: 78, gen1: 65, gen2: 1
test partitionWhileAcc // Real: 00:00:03.755, CPU: 00:00:03.790, GC gen0: 52, gen1: 50, gen2: 1

Cps averaged ~7s, Acc ~4s. In short, continuations buy you nothing for this exercise.

Solution 2:

I expect you can use continuations, but calling List.rev at the end is the best way to go.

Solution 3:

I usually prefer Sequences over List as they are lazy and you got List.toSeq and Seq.toList functions to convert between them. Below is the implementation of your partitionWhile function using sequences.

let partitionWhile (c:'a -> bool) (l:'a list) = 
    let fromEnum (e:'a IEnumerator) = 
        seq { while e.MoveNext() do yield e.Current}
    use e = (l |> List.toSeq).GetEnumerator()
    (e |> fromEnum |> Seq.takeWhile c |> Seq.toList)
    ,(e |> fromEnum |> Seq.toList)