Закрытие раздела по фильтру

Question

В Scala метод разбиения разделяет последовательность на две отдельные последовательности - те, для которых предикат является истинным, и те, для которых он ложен:

scala> List(1, 5, 2, 4, 6, 3, 7, 9, 0, 8).partition(_ % 2 == 0)
res1: (List[Int], List[Int]) = (List(2, 4, 6, 0, 8),List(1, 5, 3, 7, 9))

Обратите внимание, что реализация Scala обходит последовательность только один раз .

В Clojure функция partition-by разбивает последовательность на несколько подпоследовательностей, каждая из которых является самой длинной подгруппой, которая соответствует или не соответствует предикату:

user=> (partition-by #(= 0 (rem % 2)) [1, 5, 2, 4, 6, 3, 7, 9, 0, 8])
((1 5) (2 4 6) (3 7 9) (0 8))

в то время как split-by производит:

user=> (split-with #(= 0 (rem % 2)) [1, 5, 2, 4, 6, 3, 7, 9, 0, 8])
[() (1 5 2 4 6 3 7 9 0 8)]

Существует ли встроенная функция Clojure, которая выполняет ту же функцию, что и метод Scala partition?

Answer 1

Я считаю, что функция, которую вы ищете - clojure.core / group-by . Он возвращает карту ключей в списки элементов в исходной последовательности, для которых функция группировки возвращает этот ключ. Если вы используете предикат, производящий истину / ложь, вы получите искомый сплит.

user=> (group-by even? [1, 5, 2, 4, 6, 3, 7, 9, 0, 8])
{false [1 5 3 7 9], true [2 4 6 0 8]}

Если вы посмотрите на реализацию , она выполнит ваше требование использовать только один проход. Кроме того, он использует переходные процессы под капотом, поэтому он должен быть быстрее, чем другие решения, опубликованные до сих пор. Единственное предостережение в том, что вы должны быть уверены в том, какие клавиши генерирует ваша функция группировки. Если он выдаст nil вместо false, то ваша карта будет содержать список неисправных элементов под ключом nil. Если ваша группирующая функция выдает ненулевые значения вместо true, тогда вы можете передать значения, перечисленные в нескольких ключах. Не большая проблема, просто имейте в виду, что вам нужно использовать предикат, создающий истину / ложь, для вашей функции группировки.

Хорошая особенность group-by в том, что она более общая, чем просто разбиение последовательности на пропущенные и провальные элементы. Вы можете легко использовать эту функцию, чтобы сгруппировать вашу последовательность в любое количество категорий. Очень полезный и гибкий. Вероятно, поэтому group-by находится в clojure.core вместо separate.

Answer 2

Часть clojure.contrib.seq-utils:

user> (use '[clojure.contrib.seq-utils :only [separate]])
nil                                                                                                                                                         
user> (separate even? [1, 5, 2, 4, 6, 3, 7, 9, 0, 8])
[(2 4 6 0 8) (1 5 3 7 9)]                                                                                                                                   

Answer 3

Обратите внимание, что ответы Юргена, Адриана и Микеры проходят через входную последовательность дважды.

(defn single-pass-separate
  [pred coll]
  (reduce (fn [[yes no] item]
            (if (pred item)
              [(conj yes item) no]
              [yes (conj no item)]))
          [[] []]
          coll))

Один проход может быть только нетерпеливым.Ленивый должен быть в два прохода плюс слабо держаться за голову.

Редактировать: lazy-single-pass-separate возможно, но трудно понять.И на самом деле, я считаю, что это медленнее, чем простой второй проход.Но я не проверял это.

(defn lazy-single-pass-separate
  [pred coll]
  (let [coll       (atom coll)
        yes        (atom clojure.lang.PersistentQueue/EMPTY)
        no         (atom clojure.lang.PersistentQueue/EMPTY)
        fill-queue (fn [q]
                     (while (zero? (count @q))
                       (locking coll
                         (when (zero? (count @q))
                           (when-let [s (seq @coll)]
                             (let [fst (first s)]
                               (if (pred fst)
                                 (swap! yes conj fst)
                                 (swap! no conj fst))
                               (swap! coll rest)))))))
        queue      (fn queue [q]
                     (lazy-seq
                       (fill-queue q)
                       (when (pos? (count @q))
                         (let [item (peek @q)]
                           (swap! q pop)
                           (cons item (queue q))))))]
    [(queue yes) (queue no)]))

Это настолько ленивый, насколько вы можете получить:

user=> (let [[y n] (lazy-single-pass-separate even? (report-seq))] (def yes y) (def no n))
#'user/no
user=> (first yes)
">0<"
0
user=> (second no)
">1<"
">2<"
">3<"
3
user=> (second yes)
2

Глядя на вышесказанное, я бы сказал: «Стремись» или «пройти два прохода. "

Answer 4

Может быть, посмотрите https://github.com/amalloy/clojure-useful/blob/master/src/useful.clj#L50 - будет ли он пересекать последовательность дважды, зависит от того, что вы подразумеваете под "пересечь последовательность".

Изменить: Теперь, когда я не на своем телефоне, я думаю, что глупо, чтобы ссылаться вместо вставки:

(defn separate
  [pred coll]
  (let [coll (map (fn [x]
                    [x (pred x)])
                  coll)]
    (vec (map #(map first (% second coll))
              [filter remove]))))

Answer 5

Нетрудно написать что-то, что поможет:

(defn partition-2 [pred coll]
  ((juxt 
    (partial filter pred) 
    (partial filter (complement pred))) 
  coll))

(partition-2 even? (range 10))

=> [(0 2 4 6 8) (1 3 5 7 9)]