f# - Splitting a list into list of lists based on predicate -

(i aware of this question, relates sequences, not problem here)

given input (for example):

let testlist =      [          "*text1";        "*text2";        "text3";        "text4";        "*text5";        "*text6";        "*text7"     ]  let pred (s:string) = s.startswith("*") 

i able call myfunc pred testlist , output:

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

this current solution, don't nested list.revs (ignore fact takes seq input)

let shunt pred sq =     let shunter (prevpick, acc) (pick, a) =          match pick, prevpick         | (true, true)  -> (true, (a :: (list.hd acc)) :: (list.tl acc))         | (false, _)    -> (false, acc)         | (true, _)     -> (true, [a] :: acc)      sq          |> seq.map (fun -> (pred a, a))         |> seq.fold shunter (false, [])          |> snd         |> list.map list.rev         |> list.rev 

edit: rev-less version using foldback added below.

here's code uses lists , tail-recursion:

//divides list l chunks elements match pred let divide pred l =     let rec aux buf acc l =         match l,buf         //no more input , empty buffer -> return acc         | [],[] -> list.rev acc          //no more input , non-empty buffer -> return acc + rest of buffer         | [],buf -> list.rev (list.rev buf :: acc)          //found matches pred: put in buffer , go next in list         | h::t,buf when pred h -> aux (h::buf) acc t         //found doesn't match pred. continue don't add empty buffer acc         | h::t,[] -> aux [] acc t         //found input doesn't match pred. add buffer acc , continue empty buffer         | h::t,buf -> aux [] (list.rev buf :: acc) t     aux [] [] l 

usage:

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

using list data structure buffer means needs reversed when outputting contents. may not problem if individual chunks modestly sized. if speed/efficiency becomes issue, use queue<'a> or `list<'a>' buffers, appending fast. using these data structures instead of lists means lose powerful list pattern matching. in opinion, being able pattern match lists outweighs presence of few list.rev calls.

here's streaming version outputs result 1 block @ time. avoids list.rev on accumulator in previous example:

let dividestream pred l =     let rec aux buf l =         seq { match l, buf               | [],[] -> ()               | [],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 

this streaming version avoids list.rev on accumulator. using list.foldback can used avoid reversing accumulated chunks well.

update: here's version using foldback

//divides list l chunks elements match pred let divide2 pred l =     let f x (acc,buf) =         match pred x,buf         | true,buf -> (acc,x::buf)         | false,[] -> (acc,[])         | false,buf -> (buf::acc,[])      let rest,remainingbuffer = list.foldback f l ([],[])     match remainingbuffer     | [] -> rest     | buf -> buf :: rest