Patch: support higher arity in reduce()

[p6rt]

Migrated from rt.perl.org#78626 (status was 'rejected')

Searchable as RT78626$

[p6rt]

From smosher_@hotmail.com

Hi,

Attached is a diff against rakudo/src/core/Any-list.pm which adds support to reduce() for higher-arity functions. It ensures arity-list agreement and is generally safe. Other than the test, the functionality was already present... it needed two lines commented out, two uncommented. Since tests passed and there were no explanatory comments in the file, jnthn suggested I mail in a diff. Here it is.

I was considering including another patch to support functions that reduce to more than a single term, but as it turns out this is best handled by using a [list] item instead.

Note​: if the supplied function _does_ return more than a single term, reduce() will not produce a correct result (neither this version nor the original), but it will terminate assuming a finite list.

Regards, Stephen

 

[p6rt]

From smosher_@hotmail.com

Any-list.pm.diff

```diff --- Any-list.pm 2010-10-18 21:41:03.000000000 -0400 +++ Any-list.morearity.pm 2010-10-18 21:42:08.000000000 -0400 @@ -218,15 +218,15 @@ my $arity = $expression.?count || 2; # second half is a CHEAT fail('Cannot reduce() using a unary or nullary function.') if $arity < 2; - fail('Can only reduce() using a binary function for now.') - if $arity > 2; + warn('Arity must agree with list length in reduce().') + unless (@.elems -1) %% ($arity -1); my @args = (); for @.list { @args.push($_); if (@args == $arity) { - my $res = $expression.(@args[0], @args[1]); - # my $res = $expression.(|@args); + # my $res = $expression.(@args[0], @args[1]); + my $res = $expression.(|@args); @args = ($res); } } @@ -237,8 +237,8 @@ if @args < $expression.arity { warn (@args -1) ~ " trailing item(s) in reduce"; } else { - return $( $expression.(@args[0], @args[1]) ); - # return $( $expression.(|@args) ); + # return $( $expression.(@args[0], @args[1]) ); + return $( $expression.(|@args) ); } } return @args[0]; ```

[p6rt]

From @duncand

Stephen Mosher (via RT) wrote​:

Attached is a diff against rakudo/src/core/Any-list.pm which adds support to reduce() for higher-arity functions. It ensures arity-list agreement and is generally safe. Other than the test, the functionality was already present... it needed two lines commented out, two uncommented. Since tests passed and there were no explanatory comments in the file, jnthn suggested I mail in a diff. Here it is.

What is a common or fundamentally important example of an N-adic function whose base operation takes 3 or more operands, such that reduce() would be useful?

I suppose that something like ??!! might conceivably fit the bill since it can be arbitrarily chained and is self-similar, but probably not, considering that it isn't commutative or associative, but rather just recursive, so I'm not sure that reduce() applies here.

-- Darren Duncan

[p6rt]

The RT System itself - Status changed from 'new' to 'open'

[p6rt]

From @pmichaud

On Wed, Oct 27, 2010 at 08​:55​:36PM -0700, Darren Duncan wrote​:

Stephen Mosher (via RT) wrote​:

Attached is a diff against rakudo/src/core/Any-list.pm which adds support to reduce() for higher-arity functions. It ensures arity-list agreement and is generally safe. Other than the test, the functionality was already present... it needed two lines commented out, two uncommented. Since tests passed and there were no explanatory comments in the file, jnthn suggested I mail in a diff. Here it is.

What is a common or fundamentally important example of an N-adic function whose base operation takes 3 or more operands, such that reduce() would be useful?

At one point we had the higher-arity capability in reduce(), and then took it out because it didn't seem to make much sense. So, I agree with Darren that we need to see a use case or example (or otherwise some "approval" in the spec) before we restore this capability.

Pm

[p6rt]

From @duncand

Patrick R. Michaud wrote​:

On Wed, Oct 27, 2010 at 08​:55​:36PM -0700, Darren Duncan wrote​:

Stephen Mosher (via RT) wrote​:

Attached is a diff against rakudo/src/core/Any-list.pm which adds support to reduce() for higher-arity functions. It ensures arity-list agreement and is generally safe. Other than the test, the functionality was already present... it needed two lines commented out, two uncommented. Since tests passed and there were no explanatory comments in the file, jnthn suggested I mail in a diff. Here it is. What is a common or fundamentally important example of an N-adic function whose base operation takes 3 or more operands, such that reduce() would be useful?

At one point we had the higher-arity capability in reduce(), and then took it out because it didn't seem to make much sense. So, I agree with Darren that we need to see a use case or example (or otherwise some "approval" in the spec) before we restore this capability.

I can say that if the desire is to have reduce() wrap a function with 2 main parameters (which the elements of the input list go to) plus 1..N extra configuration parameters, then that can be handily dealt with by using a curried version of the base function that supplies the config params, so that then there are just 2 params left for reduce() to work with as usual.

While I throw that out there, I'm assuming that the higher-arity subject here is about taking 3 or more elements of the input list at once to feed the function, and its not about config params.

Do any meta-operator syntaxes let you define the base function inline such as if it would be a closure, or do they rightly only work for pre-defined symbols and you'd have to use a foo() format version of reduce for anything more complicated?

-- Darren Duncan

[p6rt]

From smosher_@hotmail.com

Subject​: Re​: [perl #​78626] Patch​: support higher arity in reduce() From​: perl6-bugs-followup@​perl.org To​: smosher_@​hotmail.com Date​: Thu, 28 Oct 2010 12​:10​:30 -0700

Patrick R. Michaud wrote​:

On Wed, Oct 27, 2010 at 08​:55​:36PM -0700, Darren Duncan wrote​:

Stephen Mosher (via RT) wrote​:

Attached is a diff against rakudo/src/core/Any-list.pm which adds support to reduce() for higher-arity functions. It ensures arity-list agreement and is generally safe. Other than the test, the functionality was already present... it needed two lines commented out, two uncommented. Since tests passed and there were no explanatory comments in the file, jnthn suggested I mail in a diff. Here it is. What is a common or fundamentally important example of an N-adic function whose base operation takes 3 or more operands, such that reduce() would be useful?

At one point we had the higher-arity capability in reduce(), and then took it out because it didn't seem to make much sense. So, I agree with Darren that we need to see a use case or example (or otherwise some "approval" in the spec) before we restore this capability.

I can say that if the desire is to have reduce() wrap a function with 2 main parameters (which the elements of the input list go to) plus 1..N extra configuration parameters, then that can be handily dealt with by using a curried version of the base function that supplies the config params, so that then there are just 2 params left for reduce() to work with as usual.

While I throw that out there, I'm assuming that the higher-arity subject here is about taking 3 or more elements of the input list at once to feed the function, and its not about config params.

Do any meta-operator syntaxes let you define the base function inline such as if it would be a closure, or do they rightly only work for pre-defined symbols and you'd have to use a foo() format version of reduce for anything more complicated?

-- Darren Duncan

Hi,

I was using it for a continued fraction reduction... something like (@​array,0).reverse.reduce({$^c/($^b+$^a)}); where the fraction is not in ...+1/x form. I would expect to run into other cases too.

Regards, Stephen

 

[p6rt]

From @coke

On Wed Oct 27 00​:22​:05 2010, smosher wrote​:

Hi,

Attached is a diff against rakudo/src/core/Any-list.pm which adds support to reduce() for higher-arity functions. It ensures arity- list agreement and is generally safe. Other than the test, the functionality was already present... it needed two lines commented out, two uncommented. Since tests passed and there were no explanatory comments in the file, jnthn suggested I mail in a diff. Here it is.

I was considering including another patch to support functions that reduce to more than a single term, but as it turns out this is best handled by using a [list] item instead.

Note​: if the supplied function _does_ return more than a single term, reduce() will not produce a correct result (neither this version nor the original), but it will terminate assuming a finite list.

Regards, Stephen

Unfortunately, this patch no longer applies against rakudo master, so I'm rejecting the ticket.

Thanks for trying to make rakudo more awesome!

-- Will "Coke" Coleda

[p6rt]

@coke - Status changed from 'open' to 'rejected'

[p6rt]

From smosher@loveandhotsauce.net

Hi,

That's fine, I think it was already shot down owing to the supposedly
dubious utility of supporting higher arities in .reduce()

By the way, I submitted the patch because the error message had (and
still has) the "for now" wording when you try any other arity. But
after I submitted the patch I was asked to defend non-binary reduce.
After scratching my head I might have replied with some mumblings
about continued fractions or something, but I don't understand why I
was asked while that particular wording is still in place—either it's
binary only or it isn't, or perhaps it's just not specced.

I can appreciate the added complication in checking when a non-binary
reduce should actually terminate, and other concerns. If I knew that
the functionality was desired, I'd be happy to submit another patch.
At the moment a change in the wording in src/core/List.pm might be
advisable, line 296​: "fail('can only reduce with arity 2 for now')",
dropping the "for now" if the functionality is not in fact desired.

Anyway, thanks for following up!

Best Regards, Stephen Mosher

Quoting Will Coleda via RT \perl6\-bugs\-followup@&#8203;perl\.org​:

On Wed Oct 27 00​:22​:05 2010, smosher wrote​:

Hi,

Attached is a diff against rakudo/src/core/Any-list.pm which adds support to reduce() for higher-arity functions. It ensures arity- list agreement and is generally safe. Other than the test, the functionality was already present... it needed two lines commented out, two uncommented. Since tests passed and there were no explanatory comments in the file, jnthn suggested I mail in a diff. Here it is.

I was considering including another patch to support functions that reduce to more than a single term, but as it turns out this is best handled by using a [list] item instead.

Note​: if the supplied function _does_ return more than a single term, reduce() will not produce a correct result (neither this version nor the original), but it will terminate assuming a finite list.

Regards, Stephen

Unfortunately, this patch no longer applies against rakudo master,
so I'm rejecting the ticket.

Thanks for trying to make rakudo more awesome!

-- Will "Coke" Coleda

[p6rt]

From @moritz

Am 13.10.2011 06​:01, schrieb smosher@​loveandhotsauce.net​:

That's fine, I think it was already shot down owing to the supposedly dubious utility of supporting higher arities in .reduce()

By the way, I submitted the patch because the error message had (and still has) the "for now" wording when you try any other arity. But after I submitted the patch I was asked to defend non-binary reduce. After scratching my head I might have replied with some mumblings about continued fractions or something, but I don't understand why I was asked while that particular wording is still in place—either it's binary only or it isn't, or perhaps it's just not specced.

I can appreciate the added complication in checking when a non-binary reduce should actually terminate, and other concerns. If I knew that the functionality was desired, I'd be happy to submit another patch. At the moment a change in the wording in src/core/List.pm might be advisable, line 296​: "fail('can only reduce with arity 2 for now')", dropping the "for now" if the functionality is not in fact desired.

Let me provide some context for the "for now" here. I'm not defending that phrase (and will remove it), just want to provide some food for thought.

Back when you wrote the patch, we did find higher arity reduce desirable, and I think some of us are still emotionally attached to the idea.

The problem is that the complexity of signatures makes it basically impossible to figure out which candidate to call if the reducer is a multi, and thus to decide how many arguments to pass.

The idea back then was to somhow specific a mechanism for supplying a (possibly lazy) stream of arguments to a set of multi candidates, and have the call eat up an apropriate amount of arguments. Such a mechansim would be useful in other places as well (such as 'for' and 'map' with blocks of higher arity), and it would be a very nice anaolgy to regexes. And like the famous "longest token matching" [1] in regexes, we'd expect such a mechanism to be mostly greedy, ie the candidate that binds the most arguments wins, unless other circumstances prevent that from happening (you see, it's rather vague).

I have no idea how feasible such a mechanism is, and if it will be included in Perl 6 at all. But I'm sure that if it will be defined, it will be on a much lower level than reduce -- probably in the multi dispatcher directly.

Up to now such a spec hasn't happened, but the idea keeps simmering in the back of the minds of several Perl 6 hackers.

Cheers, Moritz

[p6rt]

From smosher_@hotmail.com

Hi Moritz,

Thanks for the explanation, I appreciate it and I can certainly appreciate the difficulty.

(Sorry for not getting back sooner, I missed your email until now.) It's a bit of a shame since I expect most of the time .reduce will be called with a closure. If the general solution can be had, that is mighty impressive. I sort of oppose the notion that you can't provide a useful feature because the rarely more useful general case is too difficult to implement right now (if it was my task I'd be rejecting multis—forever) but I write a lot of Perl 5 too, and I don't feel regret when I have to use a utility module to make up for something that doesn't suit me and I'm happy to do the same in this case in Perl 6 for as long as is necessary.

Best Regards, Stephen

P. S. Thanks for all your work on Perl 6—that goes for everyone involved. It's a great language whichever way you slice it.

Subject​: Re​: [perl #​78626] Patch​: support higher arity in reduce() From​: perl6-bugs-followup@​perl.org To​: smosher_@​hotmail.com Date​: Thu, 13 Oct 2011 02​:02​:28 -0700

Am 13.10.2011 06​:01, schrieb smosher@​loveandhotsauce.net​:

That's fine, I think it was already shot down owing to the supposedly dubious utility of supporting higher arities in .reduce()

By the way, I submitted the patch because the error message had (and still has) the "for now" wording when you try any other arity. But after I submitted the patch I was asked to defend non-binary reduce. After scratching my head I might have replied with some mumblings about continued fractions or something, but I don't understand why I was asked while that particular wording is still in place—either it's binary only or it isn't, or perhaps it's just not specced.

I can appreciate the added complication in checking when a non-binary reduce should actually terminate, and other concerns. If I knew that the functionality was desired, I'd be happy to submit another patch. At the moment a change in the wording in src/core/List.pm might be advisable, line 296​: "fail('can only reduce with arity 2 for now')", dropping the "for now" if the functionality is not in fact desired.

Let me provide some context for the "for now" here. I'm not defending that phrase (and will remove it), just want to provide some food for thought.

Back when you wrote the patch, we did find higher arity reduce desirable, and I think some of us are still emotionally attached to the idea.

The problem is that the complexity of signatures makes it basically impossible to figure out which candidate to call if the reducer is a multi, and thus to decide how many arguments to pass.

The idea back then was to somhow specific a mechanism for supplying a (possibly lazy) stream of arguments to a set of multi candidates, and have the call eat up an apropriate amount of arguments. Such a mechansim would be useful in other places as well (such as 'for' and 'map' with blocks of higher arity), and it would be a very nice anaolgy to regexes. And like the famous "longest token matching" [1] in regexes, we'd expect such a mechanism to be mostly greedy, ie the candidate that binds the most arguments wins, unless other circumstances prevent that from happening (you see, it's rather vague).

I have no idea how feasible such a mechanism is, and if it will be included in Perl 6 at all. But I'm sure that if it will be defined, it will be on a much lower level than reduce -- probably in the multi dispatcher directly.

Up to now such a spec hasn't happened, but the idea keeps simmering in the back of the minds of several Perl 6 hackers.

Cheers, Moritz