根据谓词将列表拆分为列表列表 [英] Splitting a list into list of lists based on predicate

问题描述

(我知道

(I am aware of this question, but it relates to sequences, which is not my problem here)

给出此输入(例如):

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

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

我希望能够调用MyFunc pred testlist并获得以下输出:

I would like to be able to call MyFunc pred testlist and get this output:

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

这是我当前的解决方案，但我真的不喜欢嵌套的List.revs(忽略将Seq作为输入的事实)

This is my current solution, but I don't really like the nested List.revs (ignore the fact that it takes Seq as input)

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

推荐答案

使用下面添加的foldBack的无转速版本.

以下是一些使用列表和尾递归的代码:

Here's some code that uses lists and tail-recursion:

//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>或"List<'a>"，因为它们的添加速度很快.但是，使用这些数据结构而不是列表也意味着您将失去强大的列表模式匹配.我认为，能够对匹配列表进行模式设置胜过一些List.rev调用.

Using a list as data structure for a buffer means that it always needs to be reversed when outputting the contents. This may not be a problem if individual chunks are modestly sized. If speed/efficiency becomes an issue, you could use a Queue<'a> or a `List<'a>' for the buffers, for which appending is fast. But using these data structures instead of lists also means that you lose the powerful list pattern matching. In my opinion, being able to pattern match lists outweighs the presence of a few List.rev calls.

这里是流式版本，一次输出一个块的结果.这样可以避免上例中累加器上的List.rev:

Here's a streaming version that outputs the result one block at a time. This avoids the List.rev on the accumulator in the previous example:

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也可以避免反转累积的块.

This streaming version avoids the List.rev on the accumulator. Using List.foldBack can be used to avoid reversing the accumulated chunks as well.

更新:这是使用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

这篇关于根据谓词将列表拆分为列表列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！