(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)))))
(def xform (comp
(map inc)
(complete-with 10)
(map inc)
(init-with 100)
(map inc)
(dupl)))
(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
;=> [37 101 101 3 3 4 4 5 5 6 6 7 7 12 12]
;=> 313
;=> 313
;=> 276
(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))
(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)))))
(defn alt-into
[to xform from]
(alt-transduce xform conj to from))
(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
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@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+u...@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+u...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
(def identity
(fn [rf]
([] (rf))
([input] (rf input))))
(def identity
(fn [rf]
([] (rf))
([result] (rf result))
([result input] (rf result input))))
[...]
In my proposal above, nothing is changing about the fact that transducers transform reducing functions to new reducing functions. The simple change is to use the reducing function that is produced by a transformation stack to seed the initial value of the reduction, rather than using the input reducing function (or explicit input seed value, in the second arity of transduce).
This is a change I am interested in as well. Just yesterday I was bitten by the fact that in
the 3-arity case the init value of transduce defaults to (f) instead of ((xform f)):
While experimenting I was trying to splice a group-by-style transducer into an existing
(comp ...) chain. This step works on a map valued accumulator, and needs an initial value
of {} irregardless of what (f) would provide.
-- Michael
(fn [rf]
([] {})
...)
type Reducer a r = r -> a -> r
type Transducer a b = forall r . Reducer a r -> Reducer b r
type SomethingElse a b r = Reducer a r -> Reducer b PersistentMap
(into [] xform (range 5))
(transduce xform + 0 (range 5))
(defn init-with
[x]
(fn [rf]
(fn
([] (rf (rf) x))
...)))
([] (rf))
([] (rf (rf) x))
([] (rf (rf (rf) x) x))
...
([]
(let [r1 (rf)
r2 (rf r1 x)]
(rf r1 x)))
Hi Michael,I’m glad you are in favor of this change; however, and with tongue firmly in cheek, you’ve taken a beautiful thing and corrupted it, which I can’t condone. ;)Let me offer an explanation as to why I half-jokingly say this.From what you’ve said, your “group-by-style transducer” is going to have the following form:
(fn [rf]
([] {})
...)Irrespective of the rest of its implementation, it’s a function that transforms a reducing function into another reducing function, but it is most certainly *not* a transducer—a necessary, but not a sufficient condition.Before I make an appeal to types, let me build some intuition by borrowing the analogy that Rich Hickey made in his talk at Strange Loop. He was saying that he wanted to give instructions to the baggage handlers about how to handle the baggage, without having to say anything about whether the baggage arrived on a trolley or by conveyor belt. By returning {} in the 0-arity, you are effectively saying, “No, it’s definitely going to be on a trolley!”.
(defn group-by-xf [f]
(fn [rf]
(let [init (rf)]
(fn
([] {})
([result]
(reduce-kv (fn [acc k v] (assoc acc k (rf v)))
{} result))
([result input]
(let [k (f input)
group-result (get result k init)]
(assoc result k (rf group-result input))))))))
If I call
(into [] xform (range 5))
(transduce xform + 0 (range 5))I expect a vector and an integer to pop out, respectively, and I’m going to be sorely disappointed if a map pops out instead!
By the way, please, please, don’t read this as a polemic. I just want to be precise about the issue, and I am certainly sympathetic to “While experimenting I…”!
In this case you might prefer to write something like (transduce xform (comp group-by-xf +) ...) instead
of (transduce (comp xform group-by-xf) + ...) . [...]
type Transducer a b = forall r . Reducer a r -> Reducer b r
type SomethingElse a b r = Reducer a r -> Reducer b PersistentMap
If I call
(into [] xform (range 5))
(transduce xform + 0 (range 5))I expect a vector and an integer to pop out, respectively, and I’m going to be sorely disappointed if a map pops out instead!
In this case you might prefer to write something like (transduce xform (comp group-by-xf +) ...) instead
of (transduce (comp xform group-by-xf) + ...) . If I had used the first variant, then I would not have stumbled
over the default init value of transduce at all. Mh. Seen this way, I only have to adjust my code accordingly and can
continue to use the default init as it is. Thank you for this insight!
By the way, please, please, don’t read this as a polemic. I just want to be precise about the issue, and I am certainly sympathetic to “While experimenting I…”!
No offense taken. I do understand that beauty is always in the eye of the beholder.
Using the grouping function above I was able to take a gnarly aggregation function (basically a multi
level update-in plus a transformation on the leaves when done) and turn it into a sequence of
group-by-xf plus a much simpler reducing fn. This is very beautiful to me ;-)
-- Michael
Hi Michael,As I said above, while this is certainly a function that transforms one reducing function into another, you should not call this a transducer. It is something else, with a distinct type.Compare
type Transducer a b = forall r . Reducer a r -> Reducer b rwith
type SomethingElse a b r = Reducer a r -> Reducer b PersistentMapThe baggage handler analogy is getting at the idea that you really shouldn’t have to know anything about the conveyance, the `r` here. The rank-2 polymorphic type neatly enforces that a valid implementation *can’t* know. Your function does know, because it has removed the polymorphism and always reduces on maps—you’ve dictated that you are using map trolleys.
I think you may have missed my point here.Your group-by-xf function only makes sense in a specific interpretation of `transduce`, again indicating that it is not a valid transducer.If `into` was changed to reflect my proposal, you would find it would blown up with your group-by-xf:(into [1 2 3] (group-by-xf odd?) (range 100))A map would be returned not a vector! Similarly, if you used it with `sequence`, you’d get a map, not a sequence; or with core.async channels, you’d corrupt the channel by replacing its buffer with a map.
[...]
Your function is good for use with `reduce`, but only that. I hope I’ve helped build an intuition for why it’s actually impossible to implement ‘group by’ as a transducer.
On Oct 17, 2014 9:21 AM, "Michael van Acken" <michael....@gmail.com> wrote:
>
> This is correct. Unlike you, I am exclusively talking about the reduce case: transformations on reducing
> functions, and the general init-reduce-complete cycle represented by the 0/2/1-arities of the reducing
> functions. My use case is a reduce using the reducing function (xform f), but by default transduce
> does not pick this reducing function's 0-arity for its init value, but rather uses (f) instead.
Great, Michael, I think we're both on the same page.
After all that, I was ultimately arguing that it is technically incorrect to say:
“… trying to splice a group-by-style *transducer* into an existing
(comp ...) chain.”
(emphasis mine)
As you can tell, I come to transducers with type-theory in mind, but I'm actually equally interested in the the algebraic properties of transducers, if not more so. Why? Because these can be formulated as property-based tests (using test check, for example) and then used to search for counter examples against functions that claim to be transducers. I also feel that these, along with types, would be helpful in characterizing the boundaries of what can and can't be expressed as a transducer.
Dan
[...]
Great, Michael, I think we're both on the same page.
After all that, I was ultimately arguing that it is technically incorrect to say:
“… trying to splice a group-by-style *transducer* into an existing
(comp ...) chain.”
(emphasis mine)As you can tell, I come to transducers with type-theory in mind, but I'm actually equally interested in the the algebraic properties of transducers, if not more so.
;; transducer signature (whatever, input -> whatever) -> (whatever, input -> whatever)
In my point of view, this is a general formulation that covers the composition of reducing functions both in a
process and a reduce scenario.
-- Michael
Ah, understood. I am using the term as in http://clojure.org/transducers, where it is defined asA transducer (sometimes referred to as xform or xf) is a transformation from one reducing function to another:
;; transducer signature (whatever, input -> whatever) -> (whatever, input -> whatever)In my point of view, this is a general formulation that covers the composition of reducing functions both in a
process and a reduce scenario.