Как оптимизировать разбиение в F # больше? - PullRequest
Новая
       18

Как оптимизировать разбиение в F # больше?

0 голосов
/ 11 ноября 2009

Этот код разбивает список на две части по предикату, который берет список и возвращает ложь в момент разделения. 

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)

Кто-нибудь знает более оптимальные и более простые способы сделать это в F #?

Ответы [ 3 ]

2 голосов
/ 11 ноября 2009

Ну, вы можете сделать его хвостовым рекурсивным, но тогда вы должны полностью изменить список. Вы не хотели бы свернуть это, так как это может выйти из рекурсивного цикла в любое время. Я провел небольшое тестирование, и перевернуть список - это больше, чем восполнить хвостовая рекурсия. 

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

Версия, похожая на версию Брайана, которая является хвостовой рекурсией и принимает предикат с одним значением. 

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

Это отличается от раздела библиотечной функции тем, что он прекращает принимать элементы, как только предикат возвращает ложный вид, подобный 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]
0 голосов
/ 13 ноября 2009

Вот несколько сложений: 

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
0 голосов
/ 11 ноября 2009

Не хвостовая рекурсия, но: 

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