Transducer equivalent of tree-seq

[green-coder]

I implemented this transducer, I am wondering if you would be interested to include it in your library.

https://gist.github.com/green-coder/3adf11660b7b0ca83648c5be69de2a3b

[cgrand]

Thanks. However I’d rather not use sequences for children. Could you fix that? Le lun. 19 févr. 2018 à 19:14, Vincent Cantin <[email protected]> a écrit :

I implemented this transducer, I am wondering if you would be interested to include it in your library. https://gist.github.com/green-coder/3adf11660b7b0ca83648c5be69de2a3b — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#20>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAC3sdBuEaoHFTKBX0ccqtB78T8A9ztsks5tWbnlgaJpZM4SK8CV> .

-- On Clojure http://clj-me.cgrand.net/ Clojure Programming http://clojurebook.com Training, Consulting & Contracting http://lambdanext.eu/

[ghadishayban]

make sure to test your reduced? cases. unreduced or ensure-reduced are your friends here

[green-coder]

@cgrand I was not clear enough when I wrote my post this morning (at 2 am). Here is my second attempt:

I originally wanted to implement a transducer-only version of clojure.core.flatten, then someone pointed me to this gist which I found useful for bench-marking against other sequence-based implementations of clojure.core.tree-seq. Flatten relies on tree-seq so I went for a transducer-only version of tree-seq instead.

My function tree-seq'' is currently not using any sequence at all, the name is misleading. I use seq only to test if the children collection is empty. I could change (seq cs) into (empty? cs) but I am not sure if it is worth it as (empty? coll) is currently implemented as (not (seq coll)).

As suggested by @reborg, I need to change the name of the function. I am open to suggestions, but I will try to avoid name collision with some potential other tree-related transducers that I might add soon after. I am currently thinking to have one that only iterate on the tree leaves (i.e. the tree nodes that fail branch?), just like flatten.

@ghadishayban I will do additional tests, just in case. The function is not performing any early interruption of the transducing process, and it honors the next function rf if it does so. If you have some doubt or question about the implementation, please share them here.

[cgrand]

Your function uses `seq` `first` and `rest`. It’s going to allocate conses if children returns a vector for example. The whole `loop` containing them should be replaced by a `reduce` Le mar. 20 févr. 2018 à 07:37, Vincent Cantin <[email protected]> a écrit :

@cgrand <https://github.com/cgrand> I was not clear enough when I wrote my post this morning (at 2 am). Here is my second attempt: I originally wanted to implement a transducer-only version of clojure.core.flatten, then someone pointed me to this gist <https://gist.github.com/mfikes/cc1d1fac47e7dc112b0b9f4e3de11eae> which I found useful for bench-marking against other sequence-based implementations of clojure.core.tree-seq. Flatten relies on tree-seq so I went for a transducer-only version of tree-seq instead. My function tree-seq'' is currently not using any sequence at all, the name is misleading. I use seq only test if the children collection is empty. I could change (seq cs) into (empty? cs) but I am not sure if it is worth it as (empty? coll) is currently implemented <https://github.com/clojure/clojure/blob/clojure-1.9.0/src/clj/clojure/core.clj#L6126> as (not (seq coll)). As suggested by @reborg <https://github.com/reborg>, I need to change the name of the function. I am open to suggestions, but I will try to avoid name collision with some potential other tree-related transducers that I might add soon after. I am currently thinking to have one that only iterate on the tree leaves (i.e. the tree nodes that fail children?), just like flatten. @ghadishayban <https://github.com/ghadishayban> I will do additional tests, just in case. The function is not performing any early interruption of the transducing process, and it honors the next function rf if it does so. If you have some doubt or question about the implementation, please share them here. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#20 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAC3sdY-NseHU2nSH97rIp7Ksg_2yHtpks5tWmgcgaJpZM4SK8CV> .

-- On Clojure http://clj-me.cgrand.net/ Clojure Programming http://clojurebook.com Training, Consulting & Contracting http://lambdanext.eu/

[green-coder]

I made the change. The function is smaller and the benchmark is showing that it is twice faster. That was a good feedback, thank you.

What do you think about tree-nodes for the name? I would like to also submit the version that only returns the leaves as tree-leaves.

;; This is a private function defined in `clojure.core`.
(defn preserving-reduced
  [rf]
  #(let [ret (rf %1 %2)]
     (if (reduced? ret)
       (reduced ret)
       ret)))

(defn tree-nodes
  ([branch? children]
   (fn [rf]
     (fn xf
       ([] (rf))
       ([result] (rf result))
       ([result input]
        (let [result (rf result input)]
          (if (reduced? result) result
            (if (branch? input)
              (reduce (preserving-reduced xf)
                      result
                      (children input))
              result))))))))

[cgrand]

Getting close. Minor grip: (preserving-reduced xf) may be evaluated several times.
Also these ifs could be collapsed in a cond.
I considered the name tree-cat myself.
I think there are more to think about when it comes to trees and transducers.

[green-coder]

Coding style question: Would you prefer to have the (preserving-reduced xf) evaluated via a letfn before the level of the transducer or by simply having it expanded in-place?

I have no objection for tree-cat, but then how to call the leaf-only version? leaf-cat?

[cgrand]

Here's what I would do https://gist.github.com/cgrand/b5bf4851b0e5e3aeb438eba2298dacb9

(comp (tree-cat branch? children) (remove branch?)) is a good name for leaf-cat :-) except that branch? is going to be evaluated twice. We may find a way out by using key value pairs.

[scientific-coder]

Just came to say that I do think such a transducer would be useful. Am I wrong to believe that it could allow for elegant implementations of backtracking algorithms ? If I'm not mistaken, it could also be interesting to explore parallel execution as discussed in this great post about solving search problems with parallel depth first search in Clojure.