Самый идиоматичный способ написания пакетов размера seq в F #

Question

Я пытаюсь выучить F #, переписав некоторые алгоритмы C #, которые у меня есть, в идиоматический F #.

Одной из первых функций, которые я пытаюсь переписать, является пакетное исполнение, где:

[1..17] |> batchesOf 5

, которое разделит последовательность на пакеты с максимум пятью в каждой, то есть:

[[1; 2; 3; 4; 5]; [6; 7; 8; 9; 10]; [11; 12; 13; 14; 15]; [16; 17]]

Моя первая попытка сделать это несколько уродлива, когда я прибегнул к использованию изменяемого объекта ref после того, как столкнулся с ошибками, пытаясь использовать внутри типа mutable закрытиеИспользование ref особенно неприятно, поскольку для разыменования его необходимо использовать оператор ! , который в выражении условия может быть противоречащим интуиции для некоторых разработчиков, которые будут читать его как логическийне .Другая проблема, с которой я столкнулся, заключается в том, что Seq.skip и Seq.take не похожи на псевдонимы Linq, поскольку выдают ошибку, если size превышает размер последовательности.

let batchesOf size (sequence: _ seq) : _ list seq =
    seq {
        let s = ref sequence
        while not (!s |> Seq.isEmpty)  do
            yield !s |> Seq.truncate size |> List.ofSeq
            s := System.Linq.Enumerable.Skip(!s, size)
    }

В любом случае, какой самый элегантный / идиоматичный способ переписать это на F #?Сохранение исходного поведения, но желательно без изменяемой переменной ref .

Answer 1

Реализация этой функции с использованием типа seq<_> идиоматически сложна - тип является изменчивым, поэтому простого функционального способа не существует.Ваша версия довольно неэффективна, потому что она постоянно использует Skip в последовательности.Лучшим вариантом imperative будет использование GetEnumerator и просто перебор элементов с использованием IEnumerator.В этом фрагменте вы можете найти различные императивные опции: http://fssnip.net/1o

Если вы изучаете F #, то лучше попробовать написать функцию, используя тип списка F #.Таким образом, вы можете использовать идиоматический функциональный стиль.Затем вы можете написать batchesOf, используя сопоставление с шаблоном с аргументом рекурсии и накопителя, например:

let batchesOf size input = 
  // Inner function that does the actual work.
  // 'input' is the remaining part of the list, 'num' is the number of elements
  // in a current batch, which is stored in 'batch'. Finally, 'acc' is a list of
  // batches (in a reverse order)
  let rec loop input num batch acc =
    match input with
    | [] -> 
        // We've reached the end - add current batch to the list of all
        // batches if it is not empty and return batch (in the right order)
        if batch <> [] then (List.rev batch)::acc else acc
        |> List.rev
    | x::xs when num = size - 1 ->
        // We've reached the end of the batch - add the last element
        // and add batch to the list of batches.
        loop xs 0 [] ((List.rev (x::batch))::acc)
    | x::xs ->
        // Take one element from the input and add it to the current batch
        loop xs (num + 1) (x::batch) acc
  loop input 0 [] []

В качестве сноски императивную версию можно сделать немного лучше, используя вычислительное выражение дляработа с IEnumerator, но это не стандартная и довольно продвинутая уловка (например, см. http://fssnip.net/37).

Answer 2

Друг спросил меня об этом некоторое время назад.Вот переработанный ответ.Это работает и чисто:

let batchesOf n =
    Seq.mapi (fun i v -> i / n, v) >>
    Seq.groupBy fst >>
    Seq.map snd >>
    Seq.map (Seq.map snd)

Или нечистая версия:

let batchesOf n =
    let i = ref -1
    Seq.groupBy (fun _ -> i := !i + 1; !i / n) >> Seq.map snd

Они производят seq<seq<'a>>.Если вам действительно нужно иметь 'a list list, как в вашем примере, просто добавьте ... |> Seq.map (List.ofSeq) |> List.ofSeq, как в:

> [1..17] |> batchesOf 5 |> Seq.map (List.ofSeq) |> List.ofSeq;;
val it : int list list = [[1; 2; 3; 4; 5]; [6; 7; 8; 9; 10]; [11; 12; 13; 14; 15]; [16; 17]]

Надеюсь, что это поможет!

Answer 3

Ура, мы можем использовать List.chunkBySize, Seq.chunkBySize и Array.chunkBySize в F # 4, как упомянуто Брэд Коллинз и Скотт Влашин .

Answer 4

Это можно сделать без рекурсии, если вы хотите

[0..20] 
    |> Seq.mapi (fun i elem -> (i/size),elem) 
    |> Seq.groupBy (fun (a,_) -> a)
    |> Seq.map (fun (_,se) -> se |> Seq.map (snd));;
val it : seq<seq<int>> =
  seq
    [seq [0; 1; 2; 3; ...]; seq [5; 6; 7; 8; ...]; seq [10; 11; 12; 13; ...];
     seq [15; 16; 17; 18; ...]; ...]

В зависимости от того, как вы думаете, это может быть легче понять. Решение Томаса, вероятно, более идиоматично, хотя F #

Answer 5

Я нашел это довольно кратким решением:

let partition n (stream:seq<_>) = seq {
    let enum = stream.GetEnumerator()

    let rec collect n partition =
        if n = 1 || not (enum.MoveNext()) then
            partition
        else
            collect (n-1) (partition @ [enum.Current])

    while enum.MoveNext() do
        yield collect n [enum.Current]
}

Он работает с последовательностью и создает последовательность.Выходная последовательность состоит из списков из n элементов из входной последовательности.

Answer 6

Мой метод заключается в преобразовании списка в массив и рекурсивном разбиении массива:

    let batchesOf (sz:int) lt = 
        let arr = List.toArray lt

        let rec bite curr =
            if (curr + sz - 1 ) >= arr.Length then
                [Array.toList arr.[ curr .. (arr.Length - 1)]]
            else
                let curr1 = curr + sz 
                (Array.toList (arr.[curr .. (curr + sz - 1)])) :: (bite curr1)   

        bite 0

    batchesOf 5 [1 .. 17]

    [[1; 2; 3; 4; 5]; [6; 7; 8; 9; 10]; [11; 12; 13; 14; 15]; [16; 17]]

Answer 7

Вот простая реализация для последовательностей:

let chunks size (items:seq<_>) =
  use e = items.GetEnumerator()
  let rec loop i acc =
    seq {
      if i = size then 
        yield (List.rev acc)
        yield! loop 0 []
      elif e.MoveNext() then
        yield! loop (i+1) (e.Current::acc)
      else
        yield (List.rev acc)
    }
  if size = 0 then invalidArg "size" "must be greater than zero"
  if Seq.isEmpty items then Seq.empty else loop 0 []

let s = Seq.init 10 id
chunks 3 s 
//output: seq [[0; 1; 2]; [3; 4; 5]; [6; 7; 8]; [9]]

Answer 8

Возможно, это не идиоматично, но работает:

let batchesOf n l = 
    let _, _, temp', res' = List.fold (fun (i, n, temp, res) hd ->
                                           if i < n then
                                             (i + 1, n, hd :: temp, res)
                                           else
                                             (1, i, [hd], (List.rev temp) :: res)) 
                                       (0, n, [], []) l
    (List.rev temp') :: res' |> List.rev

Answer 9

Эта версия проходит все мои тесты, которые я только мог придумать, включая тесты для ленивой оценки и оценки одной последовательности:

let batchIn batchLength sequence =
    let padding = seq { for i in 1 .. batchLength -> None } 
    let wrapped = sequence |> Seq.map Some
    Seq.concat [wrapped; padding]
    |> Seq.windowed batchLength 
    |> Seq.mapi (fun i el -> (i, el)) 
    |> Seq.filter (fun t -> fst t % batchLength = 0) 
    |> Seq.map snd
    |> Seq.map (Seq.choose id)
    |> Seq.filter (fun el -> not (Seq.isEmpty el))

Я все еще новичок в F #, поэтому, если я что-то упустил - пожалуйста, исправьтея буду очень признателен.

Answer 10

Вы можете решить свою задачу с помощью аналога Clojure partition библиотечной функции ниже:

let partition n step coll =
    let rec split ss =
        seq {
            yield(ss |> Seq.truncate n)
            if Seq.length(ss |> Seq.truncate (step+1)) > step then
                yield! split <| (ss |> Seq.skip step)
            }
    split coll

При использовании в качестве partition 5 5 он предоставит вам требуемую batchesOf 5 функциональность:

[1..17] |> partition 5 5;;
val it : seq<seq<int>> =
  seq
    [seq [1; 2; 3; 4; ...]; seq [6; 7; 8; 9; ...]; seq [11; 12; 13; 14; ...];
     seq [16; 17]]

В качестве бонуса, играя с n и step, вы можете использовать его для нарезки перекрывающихся пакетов или скользящих окон и даже применять к бесконечным последовательностям, как показано ниже:

Seq.initInfinite(fun x -> x) |> partition 4 1;;
val it : seq<seq<int>> =
  seq
    [seq [0; 1; 2; 3]; seq [1; 2; 3; 4]; seq [2; 3; 4; 5]; seq [3; 4; 5; 6];
     ...]

Рассматривайте его как только прототип , так как он выполняет много избыточных оценок исходной последовательности и вряд ли пригоден для производственных целей.