Comment optimiser la division en F # de plus?

Question

Ce code divise une liste en deux parties par un prédicat qui prend une liste et renvoie false au moment de la division.

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) 

Est-ce que quelqu'un connaît des façons plus optimales et plus simples de le faire en F #?

Answer 1

Eh bien, vous pouvez le rendre récursif, mais vous devez inverser la liste. Vous ne voudriez pas le plier car il peut sortir de la boucle récursive à tout moment. J'ai fait un peu de test et l'inversion de la liste est plus que compensée par la récursivité de la queue.

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

Une version similaire à celle de Brian qui est récursive en queue et prend un seul prédicat de valeur.

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

Ceci est différent de la partition de fonction de bibliothèque en ce qu'elle arrête de prendre des éléments dès que le prédicat retourne faux peu comme 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

Non récursive, mais:

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

Voici une façon foldr:

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