Hi All,
I’d like to offer an alternative implementation of clojure.core/transduce.
(I’ve done some searching, and I didn’t find any evidence that this has
been raised before, but my apologies if I missed anything.)
This alternative is best motivated by example. Consider the following
transducers:
(defn init-with
[x]
(fn [rf]
(fn
([] (rf (rf) x))
([result] (rf result))
([result input]
(rf result input)))))
(defn complete-with
[x]
(fn [rf]
(fn
([] (rf))
([result]
(rf (rf result x)))
([result input]
(rf result input)))))
(defn dupl
[]
(fn [rf]
(fn
([] (rf))
([result] (rf result))
([result input]
(rf (rf result input)
input)))))
I have selected these as each illustrate something ‘interesting’ occurring
in each of the three arities of the reducing functions produced.
Now consider the following transducer, which transforms numeric reducing
functions.
(def xform (comp
(map inc)
(complete-with 10)
(map inc)
(init-with 100)
(map inc)
(dupl)))
The current behavior of transduce (and into, for illustration purposes) is:
(into [37] xform (range 5))
;=> [37 3 3 4 4 5 5 6 6 7 7 12 12]
(transduce xform + 37 (range 5))
;=> 111
(reduce + (into [37] xform (range 5)))
;=> 111
(transduce xform + (range 5))
;=> 74
So the dupl and complete-with transducers work as I expected, but the
init-with does not.
What I was hoping for was:
;=> [37 101 101 3 3 4 4 5 5 6 6 7 7 12 12]
;=> 313
;=> 313
;=> 276
This is because transduce and into are currently implemented as something
equivalent to the following:
(defn curr-transduce
([xform f coll]
(transduce xform f (f) coll))
([xform f init coll]
(let [rf (xform f)]
(rf (reduce rf init coll)))))
(defn curr-into
[to xform from]
(curr-transduce xform conj to from))
In the first arity of transduce, the initial value is taken from the
reducing function f, not the reducing function produced by (xform f).
And in the second arity, the supplied initial value is supplied directly to
the reduction.
These both bypass the transducer xform entirely, so the zeroth-arity is
never invoked and no transformation occurs.
I would like to propose the following alternative implementation:
(defn alt-transduce
([xform f coll]
(let [rf (xform f)]
(rf (reduce rf (rf) coll))))
([xform f init coll]
(let [rf (xform
(fn
([] init)
([result] (f result))
([result input] (f result input))))]
(rf (reduce rf (rf) coll)))))
In the first arity, the initial value is drawn from the transformed
reducing function, rather than the supplied reducing function.
In the second arity, a reducing function is constructed from f and init to
be f in arity 1 and 2, but return init in arity 0.
Both cases ensure that the transducer is used to transform all three
components of the reduction: init, step, and completion.
Because of the way that the second arity is implemented, into doesn’t need
to change:
(defn alt-into
[to xform from]
(alt-transduce xform conj to from))
The effect is that the reducing function passed to xform is conj, except in
arity 0, where the `to` collection is returned.
These return the results I was originally expecting:
(alt-into [37] xform (range 5))
;=> [37 101 101 3 3 4 4 5 5 6 6 7 7 12 12]
(reduce + (alt-into [37] xform (range 5)))
;=> 313
(alt-transduce xform + 37 (range 5))
;=> 313
(alt-transduce xform + (range 5))
;=> 276
I went though the list of transducers currently provided in clojure.core
and none of them do anything ‘interesting’ in zeroth-arity init component,
so the alternate implementation would not change their observable behavior.
This only affects transducers that do something other than the trivial
implementation of the zero-arity. The discussion
https://groups.google.com/d/topic/clojure/M-13lRPfguc/discussion was the
only related one I could find.
Thanks,
Dan
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
