Move `v0` to an `init` keyword argument for `reduce`, etc #27711

andyferris · 2018-06-21T11:41:21Z

The initial value v0 has been moved to a keyword argument init in reduce, mapreduce, foldl, mapfoldl, foldr and mapfoldr.

See related discussions at #27704 and refs within. In particular, this will allow the future addition of multiple input iterators to mapreduce just like we allow for map. We will need to let the deprecations expire before implementing all of #27704. We wouldn't have considered this as practical before because keyword arguments weren't type stable.

To facilitate the optional keyword argument, I introduced a new singleton called NoInit. It seemed unsafe to use nothing as the default value to indicate no specified value, because nothing is beginning to mean something in certain situations and I wanted this to be as generic as possible.

ararslan · 2018-06-21T23:52:17Z

base/abstractset.jl

@@ -59,7 +59,7 @@ julia> a
 Set([7, 4, 3, 5, 1])
 ```
 """
-union!(s::AbstractSet, sets...) = foldl(union!, s, sets)
+union!(s::AbstractSet, sets...) = foldl(union!, sets; init = s)


Generally we don't use spaces around = for keyword arguments.

ararslan · 2018-06-21T23:53:36Z

base/reduce.jl

+Singleton used for the purpose of indicating to the [`reduce`](@ref) family of functions
+that no initial value has been specified for the reduction.
+"""
+struct NoInit; end


I must say I'm not a fan of this. This feels like a slippery slope to singletons for every possible situation. Instead I think it makes sense to use nothing here, which has become pretty conventional. If someone wants to actually have nothing as their initial value, they should use Some(nothing).

Yeah - I'm definitely in two minds about it!

Though, were you suggesting we unwrap Something here?

Yeah. So init=nothing would mean "no initial value provided," whereas init=Some(nothing) would mean "the initial value is provided and is nothing." That's pretty much the use case for Some. 🙂

OK - bear with me, I'm trying to get my head around this pattern. If init = Some(1) do we use 1 or Some(1) for the inital value? How do I provide Some(nothing) as the initial element if I need to do that? I'll also need to find the best place to handle the unwrapping elegantly. Do we have a convenience function for unwrapping zero or one Somes?

You really only ever need to worry about wrapping with Some if you're dealing explicitly with nothings, which should be an incredibly uncommon case.

While I'm not going to express any preference towards using kwargs or not for this, if we do this, let's do without any special magic constants. Here's pseudo code for it (assuming I approximately get the definition of mapfoldl right):

function mapfoldl(f, op, itr; init...) if length(init) == 1 v = init.init init = NamedTuple() end isempty(init) || throw(ArgumentError("incorrect kwarg")) # MethodError? for x in itr x = f(x) if @isdefined v v = op(v, x) else v = x end end return v end

Thanks Jameson, I like it!

It's kind of weird that we can do this variadic keyword args but not standard ones. Maybe that's fine but it feels kind of messy.

Yes, it will be a slightly messier implementation but it’s simpler for end users, which is what gains my vote here.

It does make me wonder if the “pattern” could be supported in a more straightforward way by the language.

andyferris · 2018-06-22T06:32:46Z

test/reduce.jl

@@ -118,12 +118,12 @@ sum2(itr) = invoke(sum, Tuple{Any}, itr)
 plus(x,y) = x + y
 sum3(A) = reduce(plus, A)
 sum4(itr) = invoke(reduce, Tuple{Function, Any}, plus, itr)
-sum5(A) = reduce(plus, 0, A)
+sum5(A) = reduce(plus, A; int=0)
 sum6(itr) = invoke(reduce, Tuple{Function, Int, Any}, plus, 0, itr)


Can someone help me with this? What's the form for invoke with keyword arguments?

I believe you have to use the gensym'd name, i.e. Symbol("#kw##reduce"), then specify the keyword arguments' types with a NamedTuple type. See for example how functions with keyword arguments are precompiled in base/precompile.jl.

OK, it took me a while to grok but I think I've got this sorted now. :)

Does this not work? invoke(reduce, Tuple{Function, Any}, plus, itr, init=0)

andyferris · 2018-06-22T06:33:13Z

test/reduce.jl

-sum9(A) = mapreduce(x->x, plus, 0, A)
-sum10(itr) = invoke(mapreduce, Tuple{Function, Function, Int, Any}, x->x,plus,0,itr)
+sum9(A) = mapreduce(x->x, plus, A; init=0)
+sum10(itr) = invoke(mapreduce, Tuple{Function, Function, Int, Any}, x->x,plus, 0, itr)


Similarly here, invoke with keywords?

andyferris · 2018-06-25T12:15:28Z

OK, I've fixed some tests in the first commit.

In the second commit I broke everything again. Here I'm trying to get rid of NoInit using a varargs form of keyword arguments. I've just realized that my implementation is busted because I forgot about Pairs being inserted (I really still don't like this decision).

nalimilan · 2018-06-25T13:43:06Z

base/reduce.jl

-Like [`reduce`](@ref), but with guaranteed left associativity. `v0` will be used
-exactly once.
+"""
+ mapfoldl(f, op, itr; [init])


I don't think we use brackets to signal that keyword arguments are optional, see e.g. sum. I'm not sure whether we should or not, but better be consistent about it.

I was following the examples in titlecase, replace, replace! (and I think some others). Let's discuss and deal with whatever is the best documentation pattern here separately.

martinholters · 2018-06-26T07:31:42Z

Would it make sense to also add an init keyword to the specialized reductions, e.g. sum and prod? (Maybe not so much for giving another value than 0 or 1, respectively, but giving that value with the desired type for the empty case, ref. #27766 (comment)).

andyferris · 2018-06-26T11:59:53Z

@StefanKarpinski is it likely we will be able to get this into v0.7-final? (Otherwise it's v2.0)

andyferris · 2018-06-26T12:33:13Z

Would it make sense to also add an init keyword to the specialized reductions, e.g. sum and prod?

Seems like a decent idea. Though, lets see if we can merge this quickly and go from there (also, that's potential 1.x material).

StefanKarpinski · 2018-06-26T13:04:26Z

Seems like a good idea to me.

KristofferC · 2018-06-26T13:09:17Z

@nanosoldier runbenchmarks(ALL, vs = ":master")

ararslan · 2018-06-26T17:30:52Z

Had to restart the server. @nanosoldier runbenchmarks(ALL, vs=":master")

nanosoldier · 2018-06-27T04:09:13Z

Your benchmark job has completed - possible performance regressions were detected. A full report can be found here. cc @ararslan

andyferris · 2018-06-27T08:37:53Z

The large regressions shown by nanosoldier are all caused by deprecations affecting BaseBenchmarks.jl. We can fix that separately, but I'm not sure how to use two different versions of BaseBenchmarks on the one nanosoldier comparison job? I have checked performance of mapreduce before and after this PR and I did't observe any regression if you use the new syntax.

(Actually, to me that highlights a design issue with our CI... if the tests we use to check PRs aren't in the same repo (or a git submodule) then how can a single github PR possibly be self-contained?)

The initial value `v0` has been moved to a keyword argument `init` in `reduce`, `mapreduce`, `foldl`, `mapfoldl`, `foldr` and `mapfoldr`. (This will allow the future addition of multiple input iterators like we allow for `map`).

andyferris · 2018-06-28T12:26:47Z

Fingers crossed for CI this time.

Hack utilizes varargs form of keyword arguments.

andyferris · 2018-06-28T22:39:52Z

All checks passed. I will merge.

We'll need to update BaseBenchmarks.jl to reflect these deprecations.

andyferris · 2018-06-29T00:08:58Z

I forgot about accumulate... (I haven't used v0 there before). I guess that'll be another PR.

andyferris added domain:collections Data structures holding multiple items, e.g. sets keyword arguments f(x; keyword=arguments) status:triage This should be discussed on a triage call needs nanosoldier run This PR should have benchmarks run on it labels Jun 21, 2018

andyferris force-pushed the ajf/reduce-init-keyword branch from 1a47867 to 42389c2 Compare June 21, 2018 22:51

ararslan reviewed Jun 21, 2018

View reviewed changes

andyferris force-pushed the ajf/reduce-init-keyword branch from 42389c2 to f1bafe7 Compare June 22, 2018 06:31

andyferris commented Jun 22, 2018

View reviewed changes

andyferris force-pushed the ajf/reduce-init-keyword branch 2 times, most recently from 96dda6f to 8598a5e Compare June 24, 2018 23:58

andyferris mentioned this pull request Jun 25, 2018

delete for NamedTuples #27725

Closed

andyferris force-pushed the ajf/reduce-init-keyword branch from 8598a5e to d37d5e9 Compare June 25, 2018 11:46

nalimilan reviewed Jun 25, 2018

View reviewed changes

nalimilan mentioned this pull request Jun 25, 2018

reduce and reducedim have inconsistent signature #23064

Closed

martinholters mentioned this pull request Jun 26, 2018

sum(i for i in Vector{Int}()) does not return 0 #27766

Closed

andyferris force-pushed the ajf/reduce-init-keyword branch from 18c449f to afacec9 Compare June 26, 2018 11:38

StefanKarpinski added this to the 0.7 milestone Jun 26, 2018

andyferris force-pushed the ajf/reduce-init-keyword branch from afacec9 to b943e6f Compare June 27, 2018 03:47

andyferris removed the status:triage This should be discussed on a triage call label Jun 27, 2018

andyferris force-pushed the ajf/reduce-init-keyword branch from b943e6f to 9f6bef6 Compare June 27, 2018 08:40

Move v0 to an init keyword argument for reduce, etc

981b341

The initial value `v0` has been moved to a keyword argument `init` in `reduce`, `mapreduce`, `foldl`, `mapfoldl`, `foldr` and `mapfoldr`. (This will allow the future addition of multiple input iterators like we allow for `map`).

andyferris force-pushed the ajf/reduce-init-keyword branch from 9f6bef6 to 1a582a3 Compare June 28, 2018 12:26

Remove NoInit() and use optional keyword argument

037ca79

Hack utilizes varargs form of keyword arguments.

andyferris force-pushed the ajf/reduce-init-keyword branch from 1a582a3 to 037ca79 Compare June 28, 2018 12:28

andyferris merged commit c670739 into master Jun 28, 2018

andyferris deleted the ajf/reduce-init-keyword branch June 28, 2018 22:40

This was referenced Jun 29, 2018

accumulate should get init keyword like reduce #27854

Closed

Deprecate v0 in accumulate in favor of init keyword #27859

Merged

Adapt to new init keyword for reduce family of functions JuliaCI/BaseBenchmarks.jl#215

Merged

This was referenced Jun 29, 2018

bug in deprecated.jl:mapreduce #27871

Closed

fixes for nightly: Statistics stdlib JuliaLang/Compat.jl#583

Merged

ssz66666 mentioned this pull request Aug 21, 2018

Fix Base.mapreduce to match the new signature in 0.7/1.0 JuliaGPU/GPUArrays.jl#145

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Move `v0` to an `init` keyword argument for `reduce`, etc #27711

Move `v0` to an `init` keyword argument for `reduce`, etc #27711

andyferris commented Jun 21, 2018 •

edited

Loading

ararslan Jun 21, 2018

andyferris Jun 22, 2018

ararslan Jun 21, 2018

andyferris Jun 22, 2018

andyferris Jun 22, 2018

ararslan Jun 22, 2018 •

edited

Loading

andyferris Jun 22, 2018

ararslan Jun 22, 2018

vtjnash Jun 22, 2018

andyferris Jun 22, 2018

StefanKarpinski Jun 22, 2018

andyferris Jun 23, 2018

andyferris Jun 22, 2018

ararslan Jun 22, 2018 •

edited

Loading

andyferris Jun 24, 2018

GregPlowman Jun 25, 2018

andyferris Jun 22, 2018

andyferris commented Jun 25, 2018 •

edited

Loading

nalimilan Jun 25, 2018

andyferris Jun 27, 2018

martinholters commented Jun 26, 2018

andyferris commented Jun 26, 2018

andyferris commented Jun 26, 2018

StefanKarpinski commented Jun 26, 2018

KristofferC commented Jun 26, 2018

ararslan commented Jun 26, 2018

nanosoldier commented Jun 27, 2018

andyferris commented Jun 27, 2018

andyferris commented Jun 28, 2018

andyferris commented Jun 28, 2018

andyferris commented Jun 29, 2018

Move v0 to an init keyword argument for reduce, etc #27711

Move v0 to an init keyword argument for reduce, etc #27711

Conversation

andyferris commented Jun 21, 2018 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ararslan Jun 22, 2018 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ararslan Jun 22, 2018 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

andyferris commented Jun 25, 2018 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

martinholters commented Jun 26, 2018

andyferris commented Jun 26, 2018

andyferris commented Jun 26, 2018

StefanKarpinski commented Jun 26, 2018

KristofferC commented Jun 26, 2018

ararslan commented Jun 26, 2018

nanosoldier commented Jun 27, 2018

andyferris commented Jun 27, 2018

andyferris commented Jun 28, 2018

andyferris commented Jun 28, 2018

andyferris commented Jun 29, 2018

Move `v0` to an `init` keyword argument for `reduce`, etc #27711

Move `v0` to an `init` keyword argument for `reduce`, etc #27711

andyferris commented Jun 21, 2018 •

edited

Loading

ararslan Jun 22, 2018 •

edited

Loading

ararslan Jun 22, 2018 •

edited

Loading

andyferris commented Jun 25, 2018 •

edited

Loading