Эмпирическое правило, которое я использую в этих сценариях (т. Е. Тех, в которых вы хотите, чтобы одна входная последовательность создавала несколько выходных последовательностей), заключается в том, что из следующих трех желаемых свойств вы обычно можете иметь только два:
- Эффективность (пройти входную последовательность только один раз, не удерживая голову)
- Лень (производить элементы только по запросу)
- Нет общего изменяемого состояния
Версия в clojure.core выбирает (1,3), но отказывается от (2), создавая сразу весь раздел. И Python, и Haskell выбирают (1,2), хотя это не сразу очевидно: разве в Haskell нет вообще изменяемого состояния? Что ж, его ленивая оценка всего (а не только последовательностей) означает, что все выражения являются преобразователями, которые начинаются как чистые листы и записываются только тогда, когда их значение необходимо; реализация span, как вы говорите, использует один и тот же преобразователь span p xs' в обеих своих выходных последовательностях, так что в зависимости от того, какая из них сначала нужна, "отправляет" его в результат другой последовательности, выполняя действие на расстоянии, которое необходимо для сохранить другие прекрасные свойства.
Как вы отметили, альтернативная реализация Clojure, с которой вы связались, выбирает (2,3).
Проблема в том, что для partition-by отклонение либо (1) , либо (2) означает, что вы держите начало некоторой последовательности: либо вход, либо один из выходов. Поэтому, если вам нужно решение, в котором можно обрабатывать произвольно большие разделы произвольно большого ввода, вам нужно выбрать (1,2). В Clojure это можно сделать несколькими способами:
- Возьмите подход Python: верните что-то более похожее на итератор, чем на seq - seqs дают более строгие гарантии отсутствия мутации и обещают, что вы можете безопасно пройти их несколько раз и т.д. и т.д. Если вместо seq seqs вы вернете итератор из итераторы, то потребление элементов из любого одного итератора может свободно изменять или аннулировать другой (и). Это гарантирует, что потребление происходит по порядку и что память может быть освобождена.
- Возьмите подход Haskell: вручную проанализируйте все, с большим количеством обращений к
delay, и потребуйте, чтобы клиент вызывал force столько раз, сколько необходимо для получения данных. Это будет намного уродливее в Clojure и значительно увеличит глубину вашего стека (использование этого на нетривиальном вводе, вероятно, взорвет стек), но теоретически это возможно.
- Напишите что-нибудь более приправленное Clojure (но все же довольно необычное), имея несколько изменяемых объектов данных, которые координируются между выходными последовательностями, каждый из которых обновляется по мере необходимости, когда что-то запрашивается от любого из них.
Я почти уверен, что любой из этих трех подходов возможен, но, честно говоря, все они довольно сложные и отнюдь не естественные. Абстракция последовательности Clojure просто не упрощает создание структуры данных, которая вам нужна. Я советую вам, если вам нужно что-то подобное, а разделы могут быть слишком большими, чтобы их было удобно разместить, просто примите немного другой формат и сделайте немного больше бухгалтерского учета: избегайте дилеммы (1,2,3), не создавая несколько выходные последовательности у всех!
Поэтому вместо ((2 4 6 8) (1 3 5) (10 12) (7)) формат вывода для чего-то вроде (partition-by even? [2 4 6 8 1 3 5 10 12 7]), вы можете принять немного более уродливый формат: ([::key true] 2 4 6 8 [::key false] 1 3 5 [::key true] 10 12 [::key false] 7). Это несложно произвести и потребить, хотя писать это немного долго и утомительно.
Вот одна из разумных реализаций производящей функции:
(defn lazy-partition-by [f coll]
(lazy-seq
(when (seq coll)
(let [x (first coll)
k (f x)]
(list* [::key k] x
((fn part [k xs]
(lazy-seq
(when (seq xs)
(let [x (first xs)
k' (f x)]
(if (= k k')
(cons x (part k (rest xs)))
(list* [::key k'] x (part k' (rest xs))))))))
k (rest coll)))))))
И вот как его использовать, сначала определив общий reduce-grouped, который скрывает детали формата группировки, а затем пример функции count-partition-sizes для вывода ключа и размера каждого раздела без сохранения каких-либо последовательностей в памяти:
(defn reduce-grouped [f init groups]
(loop [k nil, acc init, coll groups]
(if (empty? coll)
acc
(if (and (coll? (first coll)) (= ::key (ffirst coll)))
(recur (second (first coll)) acc (rest coll))
(recur k (f k acc (first coll)) (rest coll))))))
(defn count-partition-sizes [f coll]
(reduce-grouped (fn [k acc _]
(if (and (seq acc) (= k (first (peek acc))))
(conj (pop acc) (update-in (peek acc) [1] inc))
(conj acc [k 1])))
[] (lazy-partition-by f coll)))
user> (lazy-partition-by even? [2 4 6 8 1 3 5 10 12 7])
([:user/key true] 2 4 6 8 [:user/key false] 1 3 5 [:user/key true] 10 12 [:user/key false] 7)
user> (count-partition-sizes even? [2 4 6 8 1 3 5 10 12 7])
[[true 4] [false 3] [true 2] [false 1]]
Изменить: взглянув на него еще раз, я не совсем уверен, что мой reduce-grouped намного полезнее, чем (reduce f init (map g xs)), поскольку он не дает вам четкого указания на то, когда ключ меняется. Так что, если вам действительно нужно знать, когда группа меняется, вам понадобится более умная абстракция или использовать мою оригинальную lazy-partition-by без какой-либо "умной" оболочки.
person
amalloy
schedule
14.07.2014
