F # разбить последовательность на подсписки на каждом n-м элементе

Question

Скажем, у меня есть последовательность из 100 элементов. Каждый десятый элемент мне нужен новый список из предыдущих 10 элементов. В этом случае я получу список из 10 подсписков.

Seq.take (10) выглядит многообещающе, как я могу несколько раз вызвать его, чтобы вернуть список списков?

Answer 1

теперь есть Seq.chunkBySize доступно:

[1;2;3;4;5] |> Seq.chunkBySize 2 = seq [[|1; 2|]; [|3; 4|]; [|5|]]

Answer 2

Это неплохо:

let splitEach n s =
    seq {
        let r = ResizeArray<_>()
        for x in s do
            r.Add(x)
            if r.Count = n then
                yield r.ToArray()
                r.Clear()
        if r.Count <> 0 then
            yield r.ToArray()
    }

let s = splitEach 5 [1..17]
for a in s do
    printfn "%A" a
(*
[|1; 2; 3; 4; 5|]
[|6; 7; 8; 9; 10|]
[|11; 12; 13; 14; 15|]
[|16; 17|]
*)

Answer 3

У меня есть эволюция трех решений. Ни один из них не сохраняет порядок элементов ввода, что, надо надеяться, в порядке.

Мое первое решение довольно некрасиво (используя ref-ячейки):

//[[4; 3; 2; 1; 0]; [9; 8; 7; 6; 5]; [14; 13; 12; 11; 10]; [17; 16; 15]]
let solution1 =
    let split s n =
        let i = ref 0
        let lst = ref []
        seq {
            for item in s do
                if !i = n then
                    yield !lst
                    lst := [item]
                    i := 1
                else
                    lst := item::(!lst)
                    i := !i+1
            yield !lst
        } |> Seq.toList
    split {0..17} 5

Мое второе решение исключает использование ячеек ref в первом решении, но, следовательно, вынуждает использовать прямой доступ IEnumerator (нажмите на одну сторону, выдвиньте другую)!

//[[17; 16; 15]; [14; 13; 12; 11; 10]; [9; 8; 7; 6; 5]; [4; 3; 2; 1; 0]]
let solution2 =
    let split (s:seq<_>) n =
        let e = s.GetEnumerator()
        let rec each lstlst lst i =
            if e.MoveNext() |> not then
                lst::lstlst
            elif i = n then
                each (lst::lstlst) [e.Current] 1
            else 
                each lstlst ((e.Current)::lst) (i+1)
        each [] [] 0
    split {0..17} 5

Мое третье решение основано на втором решении, за исключением того, что оно «обманывает», принимая список в качестве входных данных вместо seq, что позволяет наиболее элегантному решению использовать сопоставление с образцом, как указывает Томас, в seq не хватает (поэтому были вынуждены использовать прямой доступ к IEnumerator).

//[[17; 16; 15]; [14; 13; 12; 11; 10]; [9; 8; 7; 6; 5]; [4; 3; 2; 1; 0]]
let solution3 =
    let split inputList n =
        let rec each inputList lstlst lst i =
            match inputList with
            | [] -> (lst::lstlst)
            | cur::inputList ->
                if i = n then
                    each inputList (lst::lstlst) [cur] 1    
                else
                    each inputList lstlst (cur::lst) (i+1)
        each inputList [] [] 0
    split [0..17] 5

Если важно сохранить порядок элементов, вы можете использовать List.rev для этой цели. Например, в Solution2 измените последнюю строку функции split на:

each [] [] 0 |> List.rev |> List.map List.rev

Answer 4

Я считаю, что это будет самый быстрый:

let windowChunk n xs =
    let range = [0 .. Seq.length xs]
    Seq.windowed n xs |> Seq.zip range 
                      |> Seq.filter (fun d -> (fst d) % n = 0)
                      |> Seq.map(fun x -> (snd x))

т.е. Окно списка, zip со списком целых чисел, удалить все перекрывающиеся элементы, а затем отбросить целочисленную часть кортежа.

Answer 5

Если сомневаетесь, используйте сгиб.

let split n  = let one, append, empty = Seq.singleton, Seq.append, Seq.empty
               Seq.fold (fun (m, cur, acc) x -> 
                           if m = n then (1, one x, append acc (one cur))
                           else (m+1, append cur (one x), acc))
                        (0, empty, empty)
               >> fun (_, cur, acc) -> append acc (one cur)

Преимущество в том, что он полностью функционален, но при этом касается каждого элемента последовательности ввода только один раз (*) (в отличие от Seq.take +Seq.skip решений, предложенных выше).

(*) Предполагая O (1) Seq.append.Я, конечно, должен на это надеяться.

Answer 6

Возможно, эта простая реализация может быть полезна:

let splitAt n xs =  (Seq.truncate n xs, if Seq.length xs < n then Seq.empty else Seq.skip n xs)

let rec chunk n xs =
    if Seq.isEmpty xs then Seq.empty
    else
        let (ys,zs) = splitAt n xs
        Seq.append (Seq.singleton ys) (chunk n zs)

Например:

> chunk 10 [1..100];;
val it : seq<seq<int>> =
  seq
    [seq [1; 2; 3; 4; ...]; seq [11; 12; 13; 14; ...]; 
     seq [21; 22; 23; 24; ...]; seq [31; 32; 33; 34; ...]; ...]

> chunk 5 [1..12];;
val it : seq<seq<int>> =
  seq [seq [1; 2; 3; 4; ...]; seq [6; 7; 8; 9; ...]; seq [11; 12]]

Answer 7

Я думаю, что решение от Брайана, пожалуй, самый разумный простой вариант. Проблема с последовательностями заключается в том, что они не могут быть легко обработаны с помощью обычного сопоставления с образцом (например, функциональные списки). Один из способов избежать этого - использовать LazyList из F # PowerPack.

Другой вариант - определить построитель вычислений для работы с типом IEnumerator. Недавно я написал что-то подобное - Вы можете получить это здесь . Тогда вы можете написать что-то вроде:

let splitEach chunkSize (s:seq<_>) =
  Enumerator.toSeq (fun () -> 
    let en = s.GetEnumerator()
    let rec loop n acc = iter {
      let! item = en
      match item with 
      | Some(item) when n = 1 -> 
          yield item::acc |> List.rev 
          yield! loop chunkSize []
      | Some(item) -> 
          yield! loop (n - 1) (item::acc)
      | None -> yield acc |> List.rev }
    loop chunkSize [] )

Это позволяет использовать некоторые функциональные шаблоны для обработки списков - в частности, вы можете написать это как обычную рекурсивную функцию (аналогичную той, которую вы бы написали для списков / отложенных списков), но это обязательно под прикрытием (let! constructo из iter берет следующий элемент и изменяет перечислитель).

Answer 8

Из головы:

let rec split size list =
if List.length list < size then
    [list]
else
    (list |> Seq.take size |> Seq.toList) :: (list |> Seq.skip size |> Seq.toList |> split size)