How to optimize splitting in F# more?

Question

This code is splitting a list in two pieces by a predicate that take a list and return false in the moment of splitting.

let split pred ys =
    let rec split' l r = 
        match r with
        | [] -> []
        | x::xs -> if pred (x::l) then x::(split' (x::l) xs) else []
    let res = split' [] ys
    let last = ys |> Seq.skip (Seq.length res) |> Seq.toList
    (res, last)

Do someone knows more optimal and simpler ways to do that in F#?

Answer 1

Well you can make it tail recursive but then you have to reverse the list. You wouldn't want to fold it since it can exit out of the recursive loop at any time. I did a little testing and reversing the list is more than made up for by tail recursion.

// val pred : ('a list -> bool)
let split pred xs =
    let rec split' l xs ys = 
        match xs with
        | [] -> [], ys
        | x::xs -> if pred (x::l) then (split' (x::l) xs (x::ys)) else x::xs, ys 
    let last, res = split' [] xs []
    (res |> List.rev, last)

A version similar to Brian's that is tail recursive and takes a single value predicate.

// val pred : ('a -> bool)
let split pred xs =
    let rec split' xs ys =
        match xs with
        | [] -> [], ys
        | x::xs -> if pred x then (split' xs (x::ys)) else (x::xs), ys
    let last, res = split' xs []
    (res |> List.rev, last)

This is different from the library function partition in that it stops taking elements as soon as the predicate returns false kind of like Seq.takeWhile.

// library function
let x, y = List.partition (fun x -> x < 5) li
printfn "%A" x  // [1; 3; 2; 4]
printfn "%A" y  // [5; 7; 6; 8]

let x, y = split (fun x -> x < 5) li
printfn "%A" x  // [1; 3]
printfn "%A" y  // [5; 7; 2; 4; 6; 8]

Answer 2

Not tail-recursive, but:

let rec Break pred list =
    match list with
    | [] -> [],[]
    | x::xs when pred x -> 
        let a,b = Break pred xs
        x::a, b
    | x::xs -> [x], xs

let li = [1; 3; 5; 7; 2; 4; 6; 8]
let a, b = Break (fun x -> x < 5) li    
printfn "%A" a  // [1; 3; 5]
printfn "%A" b  // [7; 2; 4; 6; 8]

// Also note this library function
let x, y = List.partition (fun x -> x < 5) li
printfn "%A" x  // [1; 3; 2; 4]
printfn "%A" y  // [5; 7; 6; 8]

Answer 3

Here is some foldr way:

let split' pred xs = let f (ls,rs,cond) x = if cond (ls@[x]) then (ls@[x],rs,cond) else (ls,rs@[x],(fun _->false))
                     let ls,rs,_ = List.fold f ([],[],pred) xs
                     ls, rs