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`, `transduce`, and `sequence`, all ignore their given transducers
when constructing the seed value… but that does mean that one can’t corrupt
the seed value… of course you are still free to return any heinous value
you like in the other arities if you so choose…
Ok, I better leave it there…
Dan
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
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 [email protected].
For more options, visit https://groups.google.com/d/optout.
