Re: A proposal for an alternative implementation of clojure.core/transduce
Am Freitag, 17. Oktober 2014 04:02:52 UTC+2 schrieb Daniel James:
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!”.
Hi Daniel,
I'm not quite sure if your trolley-analogy is viable here (but see below).
Please note that I'm working
within a reduce scenario: a conveyor belt is moving data to the reducing
function, and once the
conveyor stops a single value is left behind -- the final result of the
reducing fn.
The grouping I am using does two things within this metaphor: in the one
direction, it splits one conveyor
into n independent conveyors; in the other direction, it combines n reduced
results again into a single result.
In code it looks like this:
(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!
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
--
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.
Re: A proposal for an alternative implementation of clojure.core/transduce
Correction after actually trying it out: In this case you might prefer to write something like (transduce xform (comp group-by-xf +) ...) instead of (transduce (comp xform group-by-xf) + ...) . [...] The first variant must use a valid rf, and needs to be written as (transduce xform ((group-by-xf odd?) +) ...) In the second it should be e.g. (comp xform (group-by-xf odd?)) -- Michael -- 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.
Re: A proposal for an alternative implementation of clojure.core/transduce
On Friday, October 17, 2014 2:58:20 AM UTC-4, Michael van Acken wrote:
Am Freitag, 17. Oktober 2014 04:02:52 UTC+2 schrieb Daniel James:
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!”.
Hi Daniel,
I'm not quite sure if your trolley-analogy is viable here (but see
below). Please note that I'm working
within a reduce scenario: a conveyor belt is moving data to the
reducing function, and once the
conveyor stops a single value is left behind -- the final result of the
reducing fn.
The grouping I am using does two things within this metaphor: in the one
direction, it splits one conveyor
into n independent conveyors; in the other direction, it combines n
reduced results again into a single result.
In code it looks like this:
(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
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 r
with
type SomethingElse a b r = Reducer a r - Reducer b PersistentMap
The 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.
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!
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.
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
I agree that your group-by-xf is a nice formulation of a ‘group by’
operation. But I maintain that it should not be considered a valid
transducer. It should only be used with `reduce`.
I hope that helps with making my point clear.
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
Re: A proposal for an alternative implementation of clojure.core/transduce
Just a quick follow up to add some clarifications…
On Friday, October 17, 2014 7:11:12 AM UTC-4, Daniel James wrote:
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 r
with
type SomethingElse a b r = Reducer a r - Reducer b PersistentMap
The 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’ve been making some simplifications to abstract away from the unnecessary
details, but I think I was a bit too loose when I said “it has removed the
polymorphism”.
Your group-by-xf function has a type the can be characterized as the
following:
group-by-xf :: (a - k) - (forall. Reducer a r - Reducer a (Map k r))
You are still polymorphic in the type of values that are being reduced, as
well as in the type of the values of the map (you are using the input
reducing function to construct the values of the map). Nonetheless, it is
still remains something other than a legitimate transducer: you have
specialized `Reducer a r` to `Reducder a (Map k r)`. And that’s the bit
that counts.
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.
Let me rephrase. As you said in your first reply, `transduce` *already*
doesn’t jibe with your `group-by-xf`.
- transduce:
it doesn’t call your 0-arity, so it will give you `init`, but you require
it to be a map.
- into:
it doesn’t call your 0-arity, so it will give you the `to`, a collection,
but you require it to be a map.
- sequence:
it doesn’t call your 0-arity, so it will give you a lazy sequence, but
you require it to be a map.
- chan:
it doesn’t call your 0-arity, so it will give you a channel buffer, but
you require it to be a map.
*If*, these were all changed to call your 0-arity:
- transduce:
you replaced `init` with {}, so the reduction returns a map.
- into:
you throw away in output collection `to`, and return a map.
- sequence:
exception??? whatever machinery is handling the laziness will surely not
like being handed a map
- chan:
exception??? whatever machinery is handling the channel will surely not
like it when you replace the channel 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.
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.
Re: A proposal for an alternative implementation of clojure.core/transduce
Am Freitag, 17. Oktober 2014 15:01:51 UTC+2 schrieb Daniel James: [...] 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. 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. -- Michael -- 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.
Re: A proposal for an alternative implementation of clojure.core/transduce
On Oct 17, 2014 9:21 AM, Michael van Acken michael.van.ac...@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 -- 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.
Re: A proposal for an alternative implementation of clojure.core/transduce
Am Freitag, 17. Oktober 2014 15:52:49 UTC+2 schrieb Daniel James: [...] 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. Ah, understood. I am using the term as in http://clojure.org/transducers, where it is defined as A *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. -- Michael -- 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.
Re: A proposal for an alternative implementation of clojure.core/transduce
On Friday, October 17, 2014 10:24:32 AM UTC-4, Michael van Acken wrote: Ah, understood. I am using the term as in http://clojure.org/transducers, where it is defined as A *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. As I said before, this is a necessary, but not a sufficient condition. It does not tell the full story. That definition provides a useful introduction for building an intuition, but it is refined later in that document as well as in Rich Hickey’s talk at Strange Loop. The promise of transducers is that you can give me one and I am free to use everywhere in a *open* world of transducible processes, `transduce`, `into`, `sequence`, `chan`, being initial examples. There is no way to write a transformation on reducing functions that provides the ‘group by’ semantics you are looking for, without breaking that contract. Irrespective of whether you accept my claims about typing transducers[1], the very fact that your `group-by-xf` function does not operate correctly in this open world is the sufficient counter-example to show that it is not a ‘transducer’ in the precise sense. Dan [1] http://conscientiousprogrammer.com/blog/2014/08/07/understanding-cloure-transducers-through-types/#comment-1533318972 “The rank-2 type in particular captures an important property.” Rich Hickey -- 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.
Re: A proposal for an alternative implementation of clojure.core/transduce
Am Mittwoch, 15. Oktober 2014 18:34:39 UTC+2 schrieb Daniel James:
[...]
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
--
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.
Re: A proposal for an alternative implementation of clojure.core/transduce
On Thursday, October 16, 2014 1:54:03 AM UTC-4, Michael van Acken wrote:
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
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!”.
Transducers have a type. Borrowing the from the exposition in
http://conscientiousprogrammer.com/blog/2014/08/07/understanding-cloure-transducers-through-types/
to a first order of approximation (ignoring initialization, stateful
transducers, and early termination), but with no loss of generality with
respect to this discussion, transducers can be typed as follows:
type Reducer a r = r - a - r
type Transducer a b = forall r . Reducer a r - Reducer b r
Your reducing-function transformation effectively has the type:
type SomethingElse a b r = Reducer a r - Reducer b PersistentMap
No matter what reducing function comes in, a reducing function on
persistent maps is going to come out the other side.
The `Transducer` type says: for all means of baggage conveyance, you can
convey me some baggage, and I might transform it in some way, but no matter
what I give you back, it will be on *exactly* the same means of baggage
conveyance.
This is *extremely* important, and is the crux of what makes transducers
great.
You have to promise to give up the right to know the type of the
reduction—whether you are building a collection with `into`, or reducing
to, say, a number with `transduce`, or transforming what flows through a
channel—and in return your transducer can be used to transform values in
any and all of those processes.
The rank-2 polymorphism used in the type of `Transducer` above expresses
exactly this promise (the `forall r.` part).
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…”!
Note the 0-arity of my `init-with` transducer:
(defn init-with
[x]
(fn [rf]
(fn
([] (rf (rf) x))
...)))
I want to add an input `x`. I need to return some result, but the type of
the result is unknowable to me. The only way I can construct one of these
is with `rf`. The 2-arity of `rf` requires a value of this unknowable type
as a first argument, and again the only way I can construct one of these is
with `rf` (the 0-arity).
With just `x` and `rf` in scope, there are still an infinite number of
plausible and valid implementations:
([] (rf))
([] (rf (rf) x))
([] (rf (rf (rf) x) x))
...
etc., etc.
Actually, this is not quite the case. Consider,
([]
(let [r1 (rf)
r2 (rf r1 x)]
(rf r1 x)))
This will satisfy the rank-2 polymorphic type for `Transducer` above, but
this will *not* lead to a valid transducer.
Here we used `(rf)` to get a seed `r1` to the reduction, we then fed `r1`
and `x` into `rf` to get `r2`, but then we *discarded* `r2` and fed `r1` a
*second* time into `rf`. It should be rather obvious that skipping over
intermediate values of the reduction and letting them float off into the
ether is incorrect.
To express this property of transducers, one would need not only the rank-2
polymorphism, but also linear typing
http://en.wikipedia.org/wiki/Substructural_type_system#Linear_type_systems
which would then adequately express that values produced by the reduction
function supplied to a transducer must be used *exactly once*.
As it stands, the current implementation of the “transducible processes”
`into`,
A proposal for an alternative implementation of clojure.core/transduce
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.
Re: A proposal for an alternative implementation of clojure.core/transduce
Dan, I haven't read yours or Christophe Grand's articles thoroughly enough even to know whether your ideas are similar, but you may be interested to read this thread, and the blog posts written by Christophe, linked from his first message in this discussion thread: https://groups.google.com/forum/#!topic/clojure-dev/cWzMS_qqgcM On Wed, Oct 15, 2014 at 6:22 AM, Daniel James dwhja...@gmail.com wrote: 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
Re: A proposal for an alternative implementation of clojure.core/transduce
Hi Andy, Thanks for the reference. I had already read Christophe’s blog posts, and had seen some of the the discussion around them. I can attempt to offer a comparison of what is being proposed. Christophe is proposing changing the types. To illustrate this, in his formulation, the identity transducer would look like: (def identity (fn [rf] ([] (rf)) ([input] (rf input Transducers as they are in Clojure 1.7, the identity transducer is: (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). I hope that helps, Dan On Wednesday, October 15, 2014 10:23:37 AM UTC-4, Andy Fingerhut wrote: Dan, I haven't read yours or Christophe Grand's articles thoroughly enough even to know whether your ideas are similar, but you may be interested to read this thread, and the blog posts written by Christophe, linked from his first message in this discussion thread: https://groups.google.com/forum/#!topic/clojure-dev/cWzMS_qqgcM On Wed, Oct 15, 2014 at 6:22 AM, Daniel James dwhj...@gmail.com javascript: wrote: 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
