Directly-reducible PoC in Clojure

tree-seq.clj

(defn nth' [coll n]
  (transduce (drop n) (completing #(reduced %2)) nil coll))

(defn tree-seq'
  [branch? children root]
    (eduction (take-while some?) (map first)
      (iterate (fn [[node pair]]
                 (when-some [[[node' & r] cont] (if (branch? node)
                                                  (if-some [cs (not-empty (children node))]
                                                    [cs pair]
                                                    pair)
                                                  pair)]
                   (if (some? r)
                     [node' [r cont]]
                     [node' cont])))
        [root nil])))


;; Adapted from nth' because we now have an transducer and not a sequence.
(defn nth'' [xf coll n]
  (transduce (comp xf (drop n))
             (completing #(reduced %2))
             nil 
             coll))

;; My transducer implementation of `clojure.core.tree-seq`
(defn tree-seq''
  ([branch? children]
   (fn [rf]
     (fn xf
       ([] (rf))
       ([result] (rf result))
       ([result input]
        (let [result (rf result input)]
          (if (reduced? result) result
            (if (branch? input)
              (loop [r result
                     cs (children input)]
                (if (seq cs)
                  (let [r' (xf r (first cs))]
                    (if (reduced? r') r'
                      (recur r' (rest cs))))
                  result))
              result))))))))


(time (dotimes [x 10000] (nth' (tree-seq seq? identity (repeat 10 (repeat 100 [1 2 (repeat 100 3)]))) 1000)))
;; "Elapsed time: 6161.53902 msecs"
      
(time (dotimes [x 10000] (nth' (tree-seq' seq? identity (repeat 10 (repeat 100 [1 2 (repeat 100 3)]))) 1000)))     
;; "Elapsed time: 2830.583306 msecs"      

;; Please test on your CPU, it should be a lot faster.
;; About less than half the time above.
(time (dotimes [x 10000]
               (nth'' (tree-seq'' sequential? identity)
                      (repeat 10 (repeat 100 [1 2 (repeat 100 3)]))
                      1000)))

Thank you for your feedback. I too agree that the name has to be changed. It was named tree-seq'' here only for comparison between implementations.

This code will be re-worked a little bit and may be added to the xform library, let's move the conversation there.