Suppose I have a list like:
(def data [:a :b :c :d :e :f :g :h :b :d :x])
and predicates like:
(defn start? [x] (= x :b))
(defn stop? [x] (= x :d))
that mark the first & last elements of a sub-sequence. I want to return a list with subgroups like so:
(parse data) => [:a [:b :c :d] :e :f :g :h [:b :d] :x]
How can I use Clojure to accomplish this task?
You could use a custom stateful transducer:
(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]
I like the stateful transducer answer, but noticed the question doesn't say what the behavior should be if a start element is found but no stop element is found. If a subgroup is left open the transducer will truncate the input sequence, which might be unexpected/undesirable. Consider the example with stop elements removed:
(into [] (subgroups #{:b} #{:d}) [:a :b :c :e :f :g :h :b :x])
=> [:a] ;; drops inputs from before (last) subgroup opens
Transducers have a completing arity that could be used to flush any open subgroup in this case:
Completion (arity 1) - some processes will not end, but for those that do (like transduce), the completion arity is used to produce a final value and/or flush state. This arity must call the xf completion arity exactly once.
The only difference in this example and the original transducer example is the completing arity:
(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))))))))
Then dangling, open groups will be flushed:
(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]]
Notice in the last example that nested starts/opens don't result in nested groupings, which got me thinking about another solution...
When I thought about this more generally as "unflattening" a sequence, zippers came to mind:
(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))))
This creates a zipper on an empty list and builds it up using reduce over the input sequence. It takes a pair of predicates for opening/closing groups and allows for arbitrarily nested groups:
(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))
If performance is not an issue, I would use clojure.spec for this. First you define a grammar for the data you want to parse:
(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))
Now you can use the conform function to parse your data:
(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]]
The above output is not what we want, so we define function to render the result:
(defn render [[type data]]
(case type
:primitive data
:group `[~(:start data) ~@(:contents data) ~(:stop data)]))
And map it over the parsed data:
(mapv render (spec/conform ::elements data))
;; => [:a [:b :c :d] :e :f :g :h [:b :d] :x]
This spec-based solution is probably not the fastest code, but it is easy to understand, maintain, extend and debug.
The Clojure function split-with can be used to do most of the work. The only tricky bit is to make the subgroup include the stop? value as well. Here is one solution:
(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)))))
With result:
(parse data) => [:a [:b :c :d] :e :f :g :h [:b :d] :x]
We use t/glue and t/append so we can always deal with vectors and append only at the end (not the beginning like conj does with lists).
The use of cond-it-> at the end to avoid gluing on an empty [] vector is a bit ugly. It occurred to me later that this was a form of mutual recursion that would be ideal for the trampoline function:
(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]
Note that for any reasonable size parsing task (say less than a few thousand calls to parse-singles and parse-group you really don't need to use trampoline. In this case, just remove the # from the two calls to parse-singles and parse-group, and delete trampoline from the definition of parse.
As always, don't forget to bookmark the Clojure CheatSheet!
Here's a version that uses lazy-seq and split-with. The key is to think about what needs to be produced for each element in the sequence, in this case the pseudo code looks like:
;; for each element (e) in the input sequence
if (start? e)
(produce values up to an including (stop? e))
else
e
The Clojure code to implement it isn't much longer that the description above.
(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)
(defn start? [x] (= x :b))
(defn stop? [x] (= x :d))
(def data [:a :b :c :d :e :f :g :h :b :d :c])
It looks like split-with should be a good choice, but meh
(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)))
Just because I like FSM and quick-bench.
(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)))