Есть ли ленивая версия функции F # Seq.groupBy?

Я хотел бы лениво сгруппировать очень большую последовательность, используя следующий код:

// native F# version
let groups =
    Seq.initInfinite id
        |> Seq.groupBy (fun i -> i % 10)
for (i, group) in groups |> Seq.take 5 do
    printfn "%A: %A" i (group |> Seq.take 5)

Ожидаемый результат:

1: seq [1; 11; 21; 31; ...]
2: seq [2; 12; 22; 32; ...]
3: seq [3; 13; 23; 33; ...]
4: seq [4; 14; 24; 34; ...]
5: seq [5; 15; 25; 35; ...]

Однако на практике эта программа зацикливается бесконечно, ничего не печатая. Возможно ли это сделать на F #?

Я бы хотел использовать Linq вместо собственных функций, но и GroupBy, и ToLookup производят такое же поведение (даже несмотря на то, что Linq GroupBy должен быть ленивым):

// Linq version
let groups =
    Enumerable.GroupBy(
        Seq.initInfinite id,
        (fun i -> i % 10))
for group in groups |> Seq.take 5 do
    printfn "%A" (group |> Seq.take 5)

Возможно, я делаю что-то непреднамеренно, что вызывает нетерпеливую оценку?


f# linq lazy-evaluation lazy-sequences
person brianberns    schedule 09.05.2015    source источник
comment
Нет, это не ты, это реализация методов. Они не очень ленивы - они не начнут оценку, если вам не нужны результаты, но все результаты будут получены сразу, как только произойдет. Но это потому, что сценарий, подобный вашему, очень необычен.   -  person MarcinJuraszek    schedule 09.05.2015
comment
Хорошо, это разочаровывает. Спасибо.   -  person brianberns    schedule 09.05.2015

Ответы (2)


arrow_upward
2
arrow_downward

Можно сказать две вещи:

Прежде всего, как узнать, сколько групп будет в бесконечной последовательности? Другими словами, сколько предметов вам нужно материализовать, чтобы получить 5 групп сверху? Сколько вам нужно было бы материализовать, если бы вы попросили 11 групп? Концептуально непросто даже неформально объяснить, что должно происходить, когда вы лениво группируетесь.

Во-вторых, Rx-версия group by является ленивой и, вероятно, максимально приближена к тому, что вы хотите: http://rxwiki.wikidot.com/101samples#toc24 Эта версия group by работает, потому что она реагирует на каждый элемент и запускает соответствующую группу как таковую, вы получаете событие, когда новый элемент потребляется, и вы получаете информация о том, в какой группе это произошло, в отличие от получения списка групп.

person Daniel Fabian    schedule 09.05.2015
comment
Зачем мне знать, сколько групп будет впереди, если сами группы возвращаются в ленивой последовательности? Если 5-я группа не сгенерирована до триллионного элемента в последовательности, очевидно, что взять 5 групп будет очень дорого. Тем не менее, команда take n на уровне группы должна возвращать первые N групп, сгенерированных последовательностью, точно так же, как take n на уровне элементов возвращает первые N элементов, сгенерированных последовательностью. Чем последовательности на уровне группы так отличаются от последовательностей на уровне элементов? - person brianberns; 09.05.2015
comment
(Кроме того, практически говоря, я действительно точно знаю, сколько групп будет в этом случае, поскольку функция группировки - это оператор мода. Но даже в этом случае функция groupBy слишком нетерпелива, потому что я не могу передать это информации во время разговора. Может быть, есть разумное решение проблемы, учитывая конечный, полностью определенный набор групп заранее? Подпись будет чем-то вроде groupByLazy fixedArrayOfGroups groupingFunction inputSequence.) - person brianberns; 09.05.2015
comment
Проблема в следующем: скажем, вы перечислили вторую группу. Чтобы добраться до первого элемента этой группы, вам нужно перечислить некоторое количество элементов, верно? Что бы вы с ними сделали? Кэш? Игнорируй их? - person Daniel Fabian; 09.05.2015
comment
В принципе, что вам нужно сделать, это что-то вроде Seq.unzip - person Daniel Fabian; 09.05.2015
comment
@DanielFabian: Эти элементы будут кешированы. Разве не так сегодня работает groupBy? Я должен иметь возможность перечислить вторую группу так далеко, как захочу, затем вернуться и перечислить первую группу без потери каких-либо элементов. Объем памяти, потребляемой реализацией, будет увеличиваться и уменьшаться по мере перечисления различных групп, но я до сих пор не понимаю, почему необходимо перечислять всю базовую последовательность, чтобы построить реализацию. - person brianberns; 09.05.2015
comment
@brianberns Мне больше хотелось показать проблемы, стоящие за действительно ленивой группой. Как именно тот, что вы всегда знаете, сколько групп вы получите, только когда вы перечисляете все элементы. Так, например, для перечисления всех групп в основном требуется полная итерация и т. Д. Такое поведение будет нелегко предсказать, и оно сильно зависит от данных. В частности, вы можете взорвать память при доступе к определенной (более поздней) группе и т. Д. Поэтому я думаю, что компромисс был сделан в пользу текущей реализации. - person Daniel Fabian; 09.05.2015
comment
@DanielFabian: Да, для перечисления всех групп потребуется полная итерация базовой последовательности, но это именно то, что делает существующий groupBy сегодня, поэтому я не считаю это новой проблемой. Да, поведение будет зависеть от данных, использование памяти может резко возрасти и т. Д., Но опять же, это не отличается от того, что мы имеем сегодня с groupBy. Другими словами, предлагаемое поведение не хуже, чем у существующей groupBy, а в некоторых случаях потенциально намного лучше. Я вообще не считаю это компромиссом, поскольку в том, что я предлагаю, нет обратной стороны. Может, посмотрю, смогу ли сам реализовать ... - person brianberns; 09.05.2015
comment
Согласен, от твоего поведения хуже не было бы. Но менее детерминированный. Итак, компромисс между неоптимальным, но детерминированным и лучшим, но о котором труднее рассуждать. Лично я вижу достоинства обеих возможных реализаций. Вы бы предпочли лучше для некоторых входов, но иногда плохо. А FSharp.Core в среднем оказался хуже, но его легко предсказать. - person Daniel Fabian; 09.05.2015
comment
Да, полагаю. Я думаю, им следует изменить подпись существующей функции groupBy, поскольку seq подразумевает лень. Это действительно seq ‹_› [], а не seq ‹seq ‹_››. - person brianberns; 09.05.2015
comment
Согласились, они сделали это с помощью Async.parallel - person Daniel Fabian; 09.05.2015

arrow_upward
1
arrow_downward

Моя библиотека Hopac для F # имеет реализацию так называемого потоки выбора (presentation), которые являются ленивыми и параллельными / асинхронными, а также предоставляют groupBy.

person Community    schedule 09.05.2015