分割基於謂詞列表到列表清單

Question

（我知道this question，但它涉及到的序列，這是不是在這裏我的問題）

鑑於此輸入（例如）：

let testlist = 
    [ 
     "*text1"; 
     "*text2"; 
     "text3"; 
     "text4"; 
     "*text5"; 
     "*text6"; 
     "*text7" 
    ] 

let pred (s:string) = s.StartsWith("*") 

我想能夠調用MyFunc pred testlist並得到如下的輸出：

[ 
    ["*text1";"*text2"]; 
    ["*text5";"*text6";"*text7"] 
] 

這是我目前的解決方案，但我真的不喜歡嵌套List.revs（忽視的事實是它需要SEQ作爲輸入）

let shunt pred sq = 
    let shunter (prevpick, acc) (pick, a) = 
     match pick, prevpick with 
     | (true, true) -> (true, (a :: (List.hd acc)) :: (List.tl acc)) 
     | (false, _) -> (false, acc) 
     | (true, _)  -> (true, [a] :: acc) 

    sq 
     |> Seq.map (fun a -> (pred a, a)) 
     |> Seq.fold shunter (false, []) 
     |> snd 
     |> List.map List.rev 
     |> List.rev 

Answer 1

編輯：以下添加REV-更少折返使用版本。

下面是一個使用列表和尾遞歸一些代碼：

//divides a list L into chunks for which all elements match pred 
let divide pred L = 
    let rec aux buf acc L = 
     match L,buf with 
     //no more input and an empty buffer -> return acc 
     | [],[] -> List.rev acc 
     //no more input and a non-empty buffer -> return acc + rest of buffer 
     | [],buf -> List.rev (List.rev buf :: acc) 
     //found something that matches pred: put it in the buffer and go to next in list 
     | h::t,buf when pred h -> aux (h::buf) acc t 
     //found something that doesn't match pred. Continue but don't add an empty buffer to acc 
     | h::t,[] -> aux [] acc t 
     //found input that doesn't match pred. Add buffer to acc and continue with an empty buffer 
     | h::t,buf -> aux [] (List.rev buf :: acc) t 
    aux [] [] L 

用法：

> divide pred testlist;; 
val it : string list list = 
    [["*text1"; "*text2"]; ["*text5"; "*text6"; "*text7"]] 

使用清單作爲一個緩衝區的數據結構意味着它總是需要被當反轉輸出內容。如果個別大小適中，這可能不成問題。如果速度/效率成爲問題，那麼可以使用Queue<'a>或'列表<'a>'作爲緩衝區，爲此添加速度很快。但是使用這些數據結構而不是列表也意味着你失去了強大的列表模式匹配。在我看來，能夠模式匹配列表勝過了幾個List.rev調用的存在。

下面是一個流式版本，一次輸出一個塊的結果。這就避免了前面例子中的蓄電池的List.rev：

let dividestream pred L = 
    let rec aux buf L = 
     seq { match L, buf with 
       | [],[] ->() 
       | [],buf -> yield List.rev buf 
       | h::t,buf when pred h -> yield! aux (h::buf) t 
       | h::t,[] -> yield! aux [] t 
       | h::t,buf -> yield List.rev buf 
          yield! aux [] t } 
    aux [] L 

這個流版本避免了蓄電池的List.rev。使用List.foldBack也可以用於避免反轉累積的塊。

更新：下面是一個使用折返版本

//divides a list L into chunks for which all elements match pred 
let divide2 pred L = 
    let f x (acc,buf) = 
     match pred x,buf with 
     | true,buf -> (acc,x::buf) 
     | false,[] -> (acc,[]) 
     | false,buf -> (buf::acc,[]) 

    let rest,remainingBuffer = List.foldBack f L ([],[]) 
    match remainingBuffer with 
    | [] -> rest 
    | buf -> buf :: rest 

Answer 2

沒有在F＃核心庫List.partition功能（如果你想實現這只是爲了有工作，而不是學習如何寫遞歸函數）。使用這個函數，你可以這樣寫：

> testlist |> List.partition (fun s -> s.StartsWith("*")) 
val it : string list * string list = 
    (["*text1"; "*text2"; "*text5"; "*text6"; "*text7"], ["text3"; "text4"]) 

請注意，這個函數返回一個元組而不是返回一個列表列表。這與你想要的有點不同，但如果謂詞返回正確或錯誤，那麼這就更有意義了。

partition函數返回的元組的執行也有點簡單，所以它可能是學習的目的有用：

let partition pred list = 
    // Helper function, which keeps results collected so 
    // far in 'accumulator' arguments outTrue and outFalse 
    let rec partitionAux list outTrue outFalse = 
    match list with 
    | [] -> 
     // We need to reverse the results (as we collected 
     // them in the opposite order!) 
     List.rev outTrue, List.rev outFalse 
    // Append element to one of the lists, depending on 'pred' 
    | x::xs when pred x -> partitionAux xs (x::outTrue) outFalse 
    | x::xs -> partitionAux xs outTrue (x::outFalse) 

    // Run the helper function 
    partitionAux list [] [] 

Answer 3

的shunt另一個版本：

let shunt pred lst = 
    let rec tWhile pred lst = 
     match lst with 
     | []     -> [], [] 
     | hd :: tl when pred hd -> let taken, rest = tWhile pred tl 
            (hd :: taken), rest 
     | lst     -> [], lst 
    let rec collect = function 
     | [] -> [] 
     | lst -> let taken, rest = tWhile pred lst 
       taken :: (collect (snd (tWhile (fun x -> not (pred x)) rest))) 
    collect lst 

這一個避免List.rev但它不是尾遞歸 - 所以只適用於小列表。

Answer 4

只需扭轉列表一旦前面，然後爲了構建結構容易：

let Shunt p l = 
    let mutable r = List.rev l 
    let mutable result = [] 
    while not r.IsEmpty do 
     let mutable thisBatch = [] 
     while not r.IsEmpty && not(p r.Head) do 
      r <- r.Tail 
     while not r.IsEmpty && p r.Head do 
      thisBatch <- r.Head :: thisBatch 
      r <- r.Tail 
     if not thisBatch.IsEmpty then 
      result <- thisBatch :: result 
    result   

外while涉及每個「批處理」，和第一內while跳過任何不匹配謂詞，然後是另一個while，它抓住所有那些在當前批次中執行並存儲它們的人。如果此批次中有任何內容（最後一個可能爲空），請將其添加到最終結果中。

這是一個例子，我認爲本地命令式代碼簡單地優於純功能對應代碼。上面的代碼很容易編寫和推理。

Answer 5

又一個......

let partition pred lst = 
    let rec trec xs cont = 
     match xs with 
     | []    -> ([],[]) |> cont 
     | h::t when pred h -> (fun (y,n) -> h::y,n) >> cont |> trec t 
     | h::t    -> (fun (y,n) -> y,h::n) >> cont |> trec t 
    trec lst id 

那麼我們可以定義分流：

let shunt pred lst = lst |> partition pred |> (fun (x,y) -> [x;y])