Самый идиоматичный способ написания пакетов размера seq в F#
Я пытаюсь выучить 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 после того, как столкнулся с ошибками, пытаясь использовать изменяемый тип внутри замыкания. Использование ref особенно неприятно, поскольку для разыменования его необходимо использовать ! Оператор, который, находясь внутри выражения условия, может быть противоречащим интуиции для некоторых разработчиков, которые не будут считать его логическим. Другая проблема, с которой я столкнулся, заключается в том, что Seq.skip и Seq.take не похожи на псевдонимы Linq, поскольку выдают ошибку, если размер превышает размер последовательности.
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#? Сохранение исходного поведения, но желательно без изменяемой переменной.
10 ответов
Реализация этой функции с помощью seq<_> Тип идиоматически сложен - тип по своей природе изменчив, поэтому простого функционального способа просто не существует. Ваша версия довольно неэффективна, потому что она использует Skip неоднократно в последовательности. Лучший императивный вариант будет использовать 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).
Друг спросил меня об этом некоторое время назад. Вот переработанный ответ. Это работает и чисто:
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]]
Надеюсь, это поможет!
Ура, мы можем использовать List.chunkBySize, Seq.chunkBySize а также Array.chunkBySize в F# 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#, хотя
Я нашел это довольно кратким решением:
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 элементов из входной последовательности.
Мой метод включает в себя преобразование списка в массив и рекурсивное разбиение массива:
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]]
Вот простая реализация для последовательностей:
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]]
Это не возможно идиоматично, но это работает:
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
Эта версия проходит все мои тесты, которые я мог придумать, включая тесты для отложенной оценки и оценки одной последовательности:
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#, поэтому, если я что-то упустил - пожалуйста, исправьте меня, это будет очень цениться.
Вы можете решить свою задачу с помощью аналога 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];
...]
Рассматривайте его только как прототип, поскольку он выполняет много избыточных оценок исходной последовательности и вряд ли подходит для производственных целей.