Разделение списка на список списков на основе предиката

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

в базовой библиотеке F # есть функция List.partition (на случай, если вы захотите реализовать это просто для того, чтобы она работала, а не для обучения написанию рекурсивных функций самостоятельно). Используя эту функцию, вы можете написать это:

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

Обратите внимание, что эта функция возвращает кортеж, а не возвращает список списков. Это немного отличается от того, что вы хотели, но если предикат возвращает просто true или false, тогда это имеет больше смысла.

Реализация функции 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 2

Редактировать: версия без версии с использованием foldBack, добавленная ниже.

Вот некоторый код, который использует списки и хвостовую рекурсию:

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

Вот потоковая версия, которая выводит результат по одному блоку за раз. Это позволяет избежать использования 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 также может использоваться для предотвращения обращения накопленных кусков.

обновление: вот версия с использованием 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 3

Просто переверните список один раз, а затем постройте структуру по порядку:

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 4

еще один ...

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

Answer 5

Другая версия 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, но он не хвостовой рекурсии - поэтому подходит только для небольших списков.