Linked list partition function and reversed results

Question

I wrote this F# function to partition a list up to a certain point and no further -- much like a cross between takeWhile and partition.

let partitionWhile c l =
    let rec aux accl accr =
        match accr with
        | [] -> (accl, [])
        | h::t ->
            if c h then
                aux (h::accl) t
            else
                (accl, accr)
    aux [] l

The only problem is that the "taken" items are reversed:

> partitionWhile ((>=) 5) [1..10];;
val it : int list * int list = ([5; 4; 3; 2; 1], [6; 7; 8; 9; 10])

Other than resorting to calling rev, is there a way this function could be written that would have the first list be in the correct order?

Witchcraft

Answer 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.

Maggs

you could try defining the CPS to pass two arguments instead of a tuple, like aux (fun acc l -> f (h::acc) l) t and calling it as aux (fun a b -> (a,b)) l, if that's allowed in F#. this would avoid the tuple unpacking and repacking on each continuation call, and might become faster overall (again, if the compiler doesn't already optimize this on its own). – Rollick

of course that final continuation is just the same as calling (rev_append (rev accl), accr) with the elements of the first half (rev accl) already baked in, already in reverse. (with rev_append (h::t) acc = rev_append t (h::acc)). – Rollick

Answer 2

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

Stagg

Other than because it's easier, is there a reason to favor an accumulator + List.rev over CPS? – Maggs

Easier to write, easier to read, and probably more performant. – Stagg

I'm going to have to read up on continuations more before I can say anything... hm.... – Witchcraft

I don't know about more performant as using continuations seemed very efficient, but I definitely stand behind easier to write/read. – Espousal

@David Yeah, I'm still trying to wrap my head around Daniel's answer. It's not a form I'm familiar with. Though as with most functional idioms and probably programming idioms in general, I think it might become fairly readable once it clicks. Performance might be something that I'd have to measure quite a few times... – Witchcraft

@Brian: I added some measurements to my answer. Your suspicion is confirmed. – Maggs

@Stagg Thanks, I ended up doing List.rev. Marking Daniel's as answer anyway because he did the research that convinced me to do so. – Witchcraft

Answer 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)

Moffett

Answer 4

You can rewrite the function like this:

let partitionWhile c l =
  let rec aux xs =
    match xs with
      | [] -> ([], [])
      | h :: t ->
          if c h then
            let (good, bad) = aux t in
              (h :: good, bad)
          else
            ([], h :: t)
  aux l

Yes, as Brian has noted it is no longer tail recursive, but it answers the question as stated. Incidentally, span in Haskell is implemented exactly the same way in Hugs:

span p []       = ([],[])
span p xs@(x:xs')
    | p x       = (x:ys, zs)
    | otherwise = ([],xs)
    where (ys,zs) = span p xs'

A good reason for preferring this version in Haskell is laziness: In the first version all the good elements are visited before the list is reversed. In the second version the first good element can be returned immediately.

Angarsk

FYI, this is not tail-recursive, so it will blow up with StackOverflowException on a very large list. – Stagg

Seems like a rather risky way to implement an algorithm that might be used for huge lists. Does Haskell provide a larger stack or something? – Witchcraft

@Rei The reason is laziness. I'd better mention that too. – Angarsk

in Racket, which is kind of Lisp/Scheme system, this would work fine because Racket uses the heap for the control stack as well. so its stack has no artificial limit to its size and is only limited by the whole available memory in the computer. – Rollick

Answer 5

I don't think I'm the only one to learn a lot from (struggling with) Daniel's CPS solution. In trying to figure it out, it helped me change several potentially (to the beginner) ambiguous list references, like so:

    let partitionWhileCps cond l1 =

        let rec aux f l2 = 
            match l2 with
            | h::t when cond h ->   aux  (fun (acc, l3) -> f (h::acc, l3))  t
            | l4 -> f ([], l4)

        aux id l1

(Note that "[]" in the l4 match is the initial acc value.) I like this solution because it feels less kludgey not having to use List.rev, by drilling to the end of the first list and building the second list backwards. I think the other main way to avoid .rev would be to use tail recursion with a cons operation. Some languages optimize "tail recursion mod cons" in the same way as proper tail recursion (but Don Syme has said that this won't be coming to F#).

So this is not tail-recursive safe in F#, but it makes my answer an answer and avoids List.rev (this is ugly to have to access the two tuple elements and would be a more fitting parallel to the cps approach otherwise, I think, like if we only returned the first list):

    let partitionWhileTrmc cond l1 = 

        let rec aux acc l2 =  
            match l2 with 
            | h::t when cond h ->  ( h::fst(aux acc t), snd(aux acc t)) 
            | l3 -> (acc, l3)

        aux [] l1

Strutting

making the same recursive call twice is extremely not-good, performance-wise, makes your second code exponential: T(n+1) = 2 * T(n) + O(1) (the run time doubles with each step along the list). that's why it is better to make just one recursive call. to get two values from it, there are two techniques. 1: return two values in a tuple 2. use CPS with binary continuation functions. – Rollick