Sorting a rich sequence without (sort)

I ran into a problem that seem 4Clojure-ish the other day, and failed to figure it out. Suppose you have a sequence something like this:

[A D B E C F]

and you want to end up with something like

[[A B C] [D E F]]

Here’s the catch: each item is actually a rich hiccup vector, meaning you can’t do a plain sort. I managed to get them in the right order with partition and interleave, but then I had too many layers of [ and ( on them. So, with only their ORDER to go on, how can they be re-ordered so all the odd are in one container, all the even in the other?

EDIT: I marked the code as solution which gave one of the several good answers below, but readers who don’t care for all the “entertainment” of reading the whole thread should also see this great answer about the principle of transducers: Sorting a rich sequence without (sort) - #43 by outrovurt

I came up with the following that seems to give the correct result. It relies on the indices instead of on sorting.

(let [l [:A :D :B :E :C :F]]
  (->> (range (count l))
       (partition 2)
       (apply map vector)
       (map #(map l %))))  

Output is ((:A :B :C) (:D :E :F))

1 Like
(def raw '[A D B E C F])

(->> raw
     (partition 2)
     (reduce (fn [[l r] [x y]] [(conj l x) (conj r y)]) [[] []]))
;;[[A B C] [D E F]]

no intermediate collections

(defn intervec [v init offset]
  (let [n  (/ (count v) 2)]
    (eduction (map (fn [idx]
                     (nth v (+ (+ init idx) (* idx offset)))))
                   (range n))))
(defn binned [v]
  (let [odds (intervec v 0 1)
        evens (intervec v 1 1)]
  [(into [] odds) (into [] evens)]))

;;user=> (binned raw)
;;[[A B C] [D E F]]

[seems like vector strides/slices should be a common/core thing, as well as index-space ops; leverages both to great effect]


Here is my attempt:

(defn chumble [coll]                                                                                
  ((juxt (partial into [] (take-nth 2))                                                             
         (partial into [] (comp (drop 1) (take-nth 2))))                                            

awesome use of eduction! I still haven’t figured out how to work that function (and am generally weak with transducers overall)

Ah! I forgot about juxt! Nicely done, and without directly thinking about vector indices

It can be very useful…basically creates and abstract “reducible” thing that implements the recipe as if by comp (the comp is implicit). So you can define an object that represents a potential reduction, which in turn can be transduced/reduced/whatever. It won’t make intermediate collections, etc. Very useful for composing transducing stuff; blurs the line between seq composition and transducers.

1 Like

Since @joinr teed it up:

user> (require '[tech.v3.tensor :as dtt])
user> (require '[tech.v3.datatype :as dtype])
user> (def src '[A D B E C F])
user> (dtype/indexed-buffer [0 2 4 1 3 5] src)
[A B C D E F]
user> (-> (dtype/indexed-buffer [0 2 4 1 3 5] src)
          (dtt/reshape [2 3]))
#tech.v3.tensor<object>[2 3]
[[A B C]
 [D E F]]

Witness me :slight_smile:

;;I think this melange is no intermediate colls (except 1 tuple vec), sharing memory across buffers
(let [idxs (range (count src))]
  (-> [(dtt/select src (eduction (filter even?) idxs))
       (dtt/select src (eduction (filter odd?) idxs))]
      (dtt/reshape [2 3])))

;;#tech.v3.tensor<object>[2 3]
;;[[A B C]
;; [D E F]]

;;readers are similarly flexible

(let [n    (count src)
      half (/ n 2)]
  [(dtype/make-reader :object half (src (* idx 2)))
   (dtype/make-reader :object half (src (inc (* idx 2))))])
;;[[A B C] [D E F]]

Here are another couple examples I thought of last night:

user> (-> (dtt/reshape src [3 2])
          (dtt/transpose [1 0]))
#tech.v3.tensor<object>[2 3]
[[A B C]
 [D E F]]
user> (dtt/compute-tensor [2 3] (fn [^long y ^long x]
                                  (src (+ (* 2 x) y))))
#tech.v3.tensor<object>[2 3]
[[A B C]
 [D E F]]
1 Like

That’s great. These little toy problems are excellent for learning more about the api. reshape/transpose combo is slick.

1 Like

Extremely boring, but well, it does work:

(defn order-odd-even
  (loop [[a b & more] coll
         left         []
         right        []]
    (let [left  (conj left a)
          right (conj right b)]
      (if more
        (recur more left right)
        [left right]))))

And here is my version using eduction:

(defn order-odd-even-eduction
  (->> coll
       (eduction (map-indexed vector))
       (reduce (fn [[l r] [idx item]]
                 (if (even? idx)
                   [(conj l item) r]
                   [l (conj r item)]))
               [[] []])))

I had absolutely no idea you could pass eduction a lazy-sequence like you have …

… wait a minute: @joinr I think you may have made a small code-typo: shouldn’t that (range n) be outside of the (map ,,,) form in intervec? When I copied and pasted into my editor it appears as if you are just passing a lazy-sequence returned by map to the eduction.

This is still faster.

let out = [[],[]];
let input = ["A","D","B","E","C","F"];
for(let i = 0; i < input.length; ++i){
  let e = input[i];
  out[i % 2].push(e);

or in pseudo lisp:

(var out [[] []])                                                                                                           
(var input ["A" "D" "B" "E" "C" "F"])                                                                                       
(for:array [[i e] input]
  (arr-push (. out [(mod i 2)]) e)))
1 Like

Yeah, typo (now fixed). eduction still works with lazy seqs, it will just fall back to a reduce over the seq (and in the case of the original code I posted, the lazy map will generate an intermediate chunked seq). The intended way is to shift one paren and keep the map isolated, so the eduction is applied to a range, which is both seqable and reducible, where the reducible form uses no intermediate collections.

similar idea with transduce directly.

(->> '[A D B E C F]
     (transduce (map-indexed vector)
                 (fn [[l r] [idx item]]
                   (if (even? idx) [(conj l item) r] [l (conj r item)])))
     [[] []]))

Something I should have mentioned is that the actual number of items in the coll is unknown; only that it is even is known. It looks like this solution is hard-coded expecting 6 items, right?

That’s some cool Javascript!

I have never seen completing before, so looked up completing - clojure.core | ClojureDocs - Community-Powered Clojure Documentation and Examples . Now I am more confused than ever…

Pro Tip - You can also do mutation by using a vector in an atom in order to be fully clojure compliant.

Regarding complecting, eduction, etc… It’s much easier to read the source rather than try to intuit what the words mean for most. of the transducer stuff.

You’ll also find that iterators do about 150% of what transducers want to do.