Как я могу сгруппировать последовательные элементы списка, используя предикаты start / stop?

Question

Предположим, у меня есть список вроде:

(def data [:a :b :c :d :e :f :g :h :b :d :x])

и такие предикаты, как:

(defn start? [x] (= x :b))
(defn stop?  [x] (= x :d))

, которые отмечают первый и последний элементы подпоследовательности. Я хочу вернуть список с подгруппами, например, так:

(parse data) => [:a [:b :c :d] :e :f :g :h [:b :d] :x]

Как я могу использовать Clojure для выполнения этой задачи?

Answer 1

Только потому, что я люблю FSM и быстрый стенд.

(let [start? #(= % :b)
          stop?  #(= % :d)
          data   [:a :b :c :d :e :f :g :h :b :d :x]]
        (letfn [(start [result [x & xs]]
                    #(collect-vec (conj result [x]) xs))

                (collect-vec [result [x & xs]]
                    #(if (nil? x)
                         result
                         ((if (stop? x) initial collect-vec)
                             (conj (subvec result 0 (dec (count result))) (conj (last result) x)) xs)))

                (collect [result [x & xs]]
                    #(initial (conj result x) xs))

                (initial [result [x & xs :as v]]
                    (cond (nil? x) result
                          (start? x) #(start result v)
                          :else (fn [] (collect result v))))]
            (trampoline initial [] data)))

Answer 2

Если производительность не является проблемой, я бы использовал для этого clojure.spec .Сначала вы определяете грамматику для данных, которые вы хотите проанализировать:

(ns playground.startstop
  (:require [clojure.spec.alpha :as spec]))

(defn start? [x] (= x :b))
(defn stop?  [x] (= x :d))

(spec/def ::not-start-stop #(and (not (start? %))
                                 (not (stop? %))))

(spec/def ::group (spec/cat :start start?
                            :contents (spec/* ::not-start-stop)
                            :stop stop?))

(spec/def ::element (spec/alt :group ::group
                              :primitive ::not-start-stop))

(spec/def ::elements (spec/* ::element))

Теперь вы можете использовать функцию conform для анализа ваших данных:

(def data [:a :b :c :d :e :f :g :h :b :d :x])

(spec/conform ::elements data)
;; => [[:primitive :a] [:group {:start :b, :contents [:c], :stop :d}] [:primitive :e] [:primitive :f] [:primitive :g] [:primitive :h] [:group {:start :b, :stop :d}] [:primitive :x]]

Приведенный выше вывод нечто мы хотим, поэтому мы определяем функцию для визуализации результата:

(defn render [[type data]]
  (case type
    :primitive data
    :group `[~(:start data) ~@(:contents data) ~(:stop data)]))

и сопоставляем его с проанализированными данными:

(mapv render (spec/conform ::elements data))
;; => [:a [:b :c :d] :e :f :g :h [:b :d] :x]

Это решение на основе спецификации, вероятно, не самый быстрый код, но его легко понять, поддерживать, расширять и отлаживать.

Answer 3

Мне нравится ответ преобразователя с состоянием , но заметил, что вопрос не говорит о том, что должно быть, если элемент start найден, но не stop элемент найден.Если подгруппа остается открытой , преобразователь усекает входную последовательность, что может быть неожиданным / нежелательным.Рассмотрим пример с удаленными элементами stop :

(into [] (subgroups #{:b} #{:d}) [:a :b :c :e :f :g :h :b :x])
=> [:a] ;; drops inputs from before (last) subgroup opens

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

Завершение (арность 1) - некоторые процессы не заканчиваются, но для тех, которые делают (например, преобразование), арность завершения используется для получения окончательного значения и / или состояния сброса.Эта арность должна вызывать арфию завершения xf ровно один раз.

Единственная разница в этом примере и оригинальном примере преобразователя состоит в том, что завершает арность:

(defn subgroups-all [start? stop?]
  (let [subgroup (volatile! nil)]
    (fn [rf]
      (fn
        ([] (rf))
        ([result] ;; completing arity flushes open subgroup
         (let [sg @subgroup]
           (if (seq sg)
             (do (vreset! subgroup nil)
                 (rf result sg))
             (rf result))))
        ([result item]
         (let [sg @subgroup]
           (cond
             (and (seq sg) (stop? item))
             (do (vreset! subgroup nil)
                 (rf result (conj sg item)))
             (seq sg)
             (do (vswap! subgroup conj item)
                 result)
             (start? item)
             (do (vreset! subgroup [item])
                 result)
             :else (rf result item))))))))

Затем свисающие, открытые группы будут сброшены:

(into [] (subgroups-all #{:b} #{:d}) [:a :b :c :d :e :f :g :h :b :x])
=> [:a [:b :c :d] :e :f :g :h [:b :x]]
(into [] (subgroups-all #{:b} #{:d}) [:a :b :c :e :f :g :h :b :x])
=> [:a [:b :c :e :f :g :h :b :x]]

Обратите внимание, что в последнем примере вложенные запуск / открытие не приводят к вложенным группировкам, что заставило меня задуматься о другом решении ...

Вложенные группы и застежки-молнии

Когда я подумала об этом в более общем смысле как о "разворачивании" последовательности, мне в голову пришли молнии:

(defn unflatten [open? close? coll]
  (when (seq coll)
    (z/root
     (reduce
      (fn [loc elem]
        (cond
          (open? elem)
          (-> loc (z/append-child (list elem)) z/down z/rightmost)
          (and (close? elem) (z/up loc))
          (-> loc (z/append-child elem) z/up)
          :else (z/append-child loc elem)))
      (z/seq-zip ())
      coll))))

Это создаетзастегните молнию на пустом списке и создайте его, используя reduce поверх последовательности ввода.Он принимает пару предикатов для открытия / закрытия групп и допускает произвольно вложенные группы:

(unflatten #{:b} #{:d} [:a :b :c :b :d :d :e :f])
=> (:a (:b :c (:b :d) :d) :e :f)
(unflatten #{:b} #{:d} [:a :b :c :b :d :b :b :d :e :f])
=> (:a (:b :c (:b :d) (:b (:b :d) :e :f)))
(unflatten #{:b} #{:d} [:b :c :e :f])
=> ((:b :c :e :f))
(unflatten #{:b} #{:d} [:d :c :e :f])
=> (:d :c :e :f)
(unflatten #{:b} #{:d} [:c :d])
=> (:c :d)
(unflatten #{:b} #{:d} [:c :d :b])
=> (:c :d (:b))

Answer 4

(defn start? [x] (= x :b))
(defn stop?  [x] (= x :d))
(def data [:a :b :c :d :e :f :g :h :b :d :c])

Похоже, split-with должно быть хорошим выбором, но ме

(loop [data data
       res []]
  (let [[left tail] (split-with (comp not start?) data)
        [group [stop & new-data]] (split-with (comp not stop?) tail)
        group (cond-> (vec group) stop (into [stop]))
        new-res (cond-> (into res left)
                  (seq group) (into [group]))]
    (if (seq new-data)
      (recur new-data new-res)
      new-res)))

Answer 5

Вот версия, которая использует lazy-seq и split-with.Ключ в том, чтобы подумать о том, что нужно создать для каждого элемента в последовательности, в этом случае псевдокод выглядит так:

;; for each element (e) in the input sequence

if (start? e) 
  (produce values up to an including (stop? e))
else 
  e

Код Clojure для его реализации не намного длиннее, чем описаниевыше.

(def data [:a :b :c :d :e :f :g :h :b :d :x])

(def start? #(= :b %))
(def stop?  #(= :d %))

(defn parse [vals]
  (when-let [e (first vals)]
    (let [[val rst] (if (start? e)
                      (let [[run remainder] (split-with (complement stop?) vals)]
                        [(concat run [(first remainder)]) (rest remainder)])
                      [e (rest vals)])]
      (cons val (lazy-seq (parse rst))))))

;; this produces the following output
(parse data) ;; => (:a (:b :c :d) :e :f :g :h (:b :d) :x)

Answer 6

Вы можете использовать пользовательский преобразователь с отслеживанием состояния:

(defn subgroups [start? stop?]
  (let [subgroup (volatile! nil)]
    (fn [rf]
      (fn
        ([] (rf))
        ([result] (rf result))
        ([result item]
         (let [sg @subgroup]
           (cond
             (and (seq sg) (stop? item))
             (do (vreset! subgroup nil)
               (rf result (conj sg item)))
             (seq sg)
             (do (vswap! subgroup conj item)
               result)
             (start? item)
             (do (vreset! subgroup [item])
               result)
             :else (rf result item))))))))

(into []
      (subgroups #{:b} #{:d})
      [:a :b :c :d :e :f :g :h :b :d :x])
; => [:a [:b :c :d] :e :f :g :h [:b :d] :x]

Answer 7

Функция Clojure split-with может использоваться для выполнения большей части работы. Единственный хитрый момент - заставить подгруппу также включать значение stop?. Вот одно из решений:

(ns tst.demo.core
  (:use tupelo.core demo.core tupelo.test))

(def data [:a :b :c :d :e :f :g :h :b :d :x])

(defn start? [x] (= x :b))
(defn stop?  [x] (= x :d))

(defn parse [vals]
  (loop [result []
         vals   vals]
    (if (empty? vals)
      result
      (let [[singles group-plus]  (split-with #(not (start? %)) vals)
            [grp* others*]        (split-with #(not (stop? %)) group-plus)
            grp        (glue grp* (take 1 others*))
            others     (drop 1 others*)
            result-out (cond-it-> (glue result singles)
                         (not-empty? grp) (append it grp))]
        (recur result-out others)))))

С результатом:

(parse data) => [:a [:b :c :d] :e :f :g :h [:b :d] :x]

Мы используем t/glue и t/append, поэтому мы можем всегда иметь дело с векторами и добавлять только в конце (а не в начале, как conj со списками).

---

Обновление

Использование cond-it-> в конце, чтобы избежать склеивания пустого [] вектора, немного уродливо. Позже мне пришло в голову, что это была форма взаимной рекурсии, которая была бы идеальной для функции trampoline:

(ns tst.demo.core
  (:use tupelo.core demo.core tupelo.test))

(def data [:a :b :c :d :e :f :g :h :b :d :x])

(defn start? [x] (= x :b))
(defn stop?  [x] (= x :d))

(declare parse-singles parse-group)

(defn parse-singles [result vals]
  (if (empty? vals)
    result
    (let [[singles groupies] (split-with #(not (start? %)) vals)
          result-out (glue result singles)]
      #(parse-group result-out groupies))))

(defn parse-group [result vals]
  (if (empty? vals)
    result
    (let [[grp-1 remaining] (split-with #(not (stop? %)) vals)
          grp      (glue grp-1 (take 1 remaining))
          singlies (drop 1 remaining)
          result-out   (append result grp)]
      #(parse-singles result-out singlies))))

(defn parse [vals]
  (trampoline parse-singles [] vals))

(dotest
  (spyx (parse data)))

(parse data) => [:a [:b :c :d] :e :f :g :h [:b :d] :x]

Обратите внимание, что для любой задачи синтаксического анализа разумного размера (скажем, менее нескольких тысяч вызовов parse-singles и parse-group вам действительно не нужно использовать trampoline. В этом случае просто удалите # из два вызова parse-singles и parse-group и удаление trampoline из определения parse.

---

Clojure CheatSheet

Как всегда, не забудьте добавить в закладки Clojure CheatSheet!