Reguła, z której korzystam w tych scenariuszach (tj. Tych, w których chcesz, aby pojedyncza sekwencja wejściowa tworzyła wiele sekwencji wyjściowych) jest taka, że z następujących trzech pożądanych właściwości, możesz ogólnie mieć tylko dwa:
- Sprawność (przemierzać sekwencję wejściową tylko raz, więc nie trzymać głowę)
- Lenistwo (produkować elementy tylko na żądanie)
- nie podzielił państwowych zmienny
Wersja w clojure.core wybiera (1,3), ale rezygnuje z (2), tworząc jednocześnie całą partycję. Python i Haskell wybierają (1,2), chociaż nie jest to od razu oczywiste: czy Haskell w ogóle nie ma stanu zmiennego? Cóż, leniwy pomiar wszystkiego (nie tylko sekwencji) oznacza, że wszystkie wyrażenia są thunks, które rozpoczynają się jako puste pola i są zapisywane tylko wtedy, gdy ich wartość jest potrzebna; implementacja span, jak mówisz, dzieli ten sam thunk z span p xs' w obu swoich sekwencjach wyjściowych, tak że to, co jest potrzebne, najpierw "wysyła" je do wyniku drugiej sekwencji, wykonując akcję z odległości niezbędnej do zachowaj inne miłe właściwości.
Alternatywna implementacja Clojure powiązana z wybranymi (2,3), jak zauważyłeś.
Problem polega na tym, że dla partition-by, spadku albo (1) lub (2) oznacza, że trzymasz głowę niektórych sekwencji: albo wejście lub jedno z wyjść. Jeśli więc potrzebujesz rozwiązania, w którym można obsłużyć dowolnie duże partycje arbitralnie dużego wejścia, musisz wybrać (1,2). Istnieje kilka sposobów można to zrobić w Clojure:
- Weź podejście Python: return coś bardziej jak iterator niż seq - seqs zrobić mocniejsze gwarancje o braku mutacji, a obiecuję, że bezpiecznie można je przemierzać wiele razy, itd. Jeśli zamiast seqs zwrócisz iterator iteratorów, to konsumowanie elementów z dowolnego iteratora może dowolnie mutować lub unieważniać inne. To gwarantuje, że konsumpcja odbywa się w porządku i że pamięć może zostać uwolniona.
- Podejście Haskella: ręcznie odfaj wszystko, z mnóstwem połączeń do
delay i wymagaj od klienta dzwonienia pod numer force tak często, jak to konieczne, aby uzyskać dane. To będzie dużo brzydsze w Clojure i znacznie zwiększy twoją głębię stosu (użycie tego na nietrywialnym wejściu prawdopodobnie zepsułoby stos), ale teoretycznie jest to możliwe.
- Napisz coś więcej smaku Clojure (ale wciąż całkiem niezwykłego) dzięki kilku zmiennym obiektom danych, które są skoordynowane pomiędzy kolejnymi wyjściowymi numerami, z których każdy jest aktualizowany w razie potrzeby, gdy coś jest wymagane od żadnego z nich.
Jestem pewien, że każde z tych trzech podejść jest możliwe, ale szczerze mówiąc, wszystkie są dość trudne i wcale nie są naturalne. Abstrakcja sekwencji Clojure po prostu nie ułatwia tworzenia struktury danych, którą chcesz. Moja rada jest taka, że jeśli potrzebujesz czegoś takiego, a partycje mogą być zbyt duże, aby zmieścić się wygodnie, po prostu zaakceptuj nieco inny format i wykonaj nieco więcej czynności związanych z księgowaniem: unikaj dylematu (1,2,3), nie produkując wielu sekwencje wyjściowe!
Więc zamiast ((2 4 6 8) (1 3 5) (10 12) (7)) jest Twój format czegoś podobnego (partition-by even? [2 4 6 8 1 3 5 10 12 7]), można przyjąć nieco brzydsze format: ([::key true] 2 4 6 8 [::key false] 1 3 5 [::key true] 10 12 [::key false] 7). Nie jest to ani trudne do wyprodukowania, ani trudne do konsumpcji, chociaż pisanie jest nieco zbyt długie i żmudne.
Oto jeden rozsądny realizacja funkcji produkującej:
(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)))))))
A oto jak je konsumować, najpierw definiowania rodzajowe reduce-grouped który ukrywa szczegóły formatu grupowania, a następnie przykładem funkcja count-partition-sizes do wyjścia klucz i rozmiar każdej partycji bez zachowania jakichkolwiek sekwencji w pamięci:
(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]]
Edit: znowu Patrząc na to, że nie jestem prawdziwym Jestem przekonany, że mój reduce-grouped jest o wiele bardziej przydatny niż (reduce f init (map g xs)), ponieważ tak naprawdę nie daje wyraźnego wskazania, kiedy klucz się zmienia. Więc jeśli potrzebujesz wiedzieć, kiedy grupa się zmieni, będziesz potrzebować mądrzejszej abstrakcji lub użyć mojego oryginalnego lazy-partition-by bez "inteligentnego" owijania jej.
Czy poprawiam to, jeśli zamieniam '(lazy-seq @tail)' na '(lazy-seq (drop-while # (= fv (keyfn%)) @tail))', które zadziała również w przypadku kiedy 'processfn' nie pochłania całkowicie argumentu? – tempestadept
Wygląda również na to, że wersja bez 'drop-while' traci pierwszy element każdej części poza pierwszą. – tempestadept
@tempestadept Dzięki za debugowanie, naprawiono te problemy z edycjami powyżej. (1) 'drop-while' musi być' (lazy-seq (drop-while ...)), aby zapobiec pochopnej ocenie argumentów 'drop-while'. (2) Błąd off-by-one był spowodowany tym, że 'take-while' musi sprawdzić pierwszą fałszywą wartość. W związku z tym musimy podeprzeć ogon z pierwszą obojętną wartością, aby pozostać na jednym z przodu. –