[% setvar title Builtin: reduce %]

This file is part of the Perl 6 Archive

Note: these documents may be out of date. Do not use as reference!

To see what is currently happening visit http://www.perl6.org/


Builtin: reduce


  Maintainer: Damian Conway <damian@conway.org>
  Date: 10 August 2000
  Last Modified: 20 Sep 2000
  Mailing List: perl6-language@perl.org
  Number: 76
  Version: 4
  Status: Frozen
  Frozen since: v2
  Note: Really Really Frozen this time


This RFC proposes a built-in reduce function, modelled after Graham Barr's reduce subroutine from the List::Utils module (a.k.a. The Module Formerly Known As builtin.pm).


A new built-in -- reduce -- is proposed.

This function would take an block, subroutine reference, or curried function (hereafter referred to as the reduction subroutine), and call it repeatedly to reduce the remaining arguments (hereafter, referred to as the list).

If the reduction subroutine has a prototype, that prototype determines how many items are reduced at a time. If the reduction subroutine is a block or has no prototype, two items are reduced each time.

The first call to the reduction subroutine will be passed the first N elements of the list, and subsequent calls will be passed the result of the previous call and the next N-1 elements in the list, until no more elements remain in the list. All calls to the reduction subroutine are made in a scalar context.

If fewer than N-1 elements would be available for the final reduction call, a exception is thrown, unless the reduction subroutine's parameter list specifies the missing data as being optional. For example:

	sub reducer1 ($sum,$n,$k) { $sum + $n**$k }
	sub reducer2 ($sum,$n;$k) { $sum + $n**($k||0) }

	@data = (1..9);

	$result = reduce \&reducer1, 0, @data;	# die (no $k for last reduction)
	$result = reduce \&reducer2, 0, @data;	# okay (final $k is undef)

Note that this exception could be thrown before the reduction begins (assuming reduce and the other list ops aren't made lazy in Perl 6), by determining the total number of elements to be reduced (E), the maximal number of elements that may be procesed on each reduction step (R), and the minimal number of elements that may be processed on each step (r), and then testing whether:

                            ___  ___
                           | E+1-2R |
        r  >  E - R - (R-1)| ------ |
                           |   R-1  |

is true (in which case an exception is required as there will be insufficient elements to pass to the final reduction step).

If the original list has no elements, reduce immediately throws an exception. If the original list has a single element, that element is immediately returned (without ever calling the reduction subroutine). Otherwise, in a scalar context, the result of the final reduction call is the result returned by reduce. In a list context, a list of all the interim values, plus the final value, would be returned.



        $sum = reduce {$_[0]+$_[1]}     0, @numbers;
        $sum = reduce sub{$_[0]+$_[1]}, 0, @numbers;
        $sum = reduce ^_+^_,            0, @numbers;

Note that the first element of the list -- zero in this case, 1 in the next example -- represents the default value if the list is empty.


        $prod = reduce {$_[0]*$_[1]}     1, @numbers;
        $prod = reduce sub{$_[0]*$_[1]}, 1, @numbers;
        $prod = reduce ^_*^_,            1, @numbers;


        $min = reduce ^x <= ^y ? ^x : ^y,  @numbers
        $min = reduce ^x le ^y ? ^x : ^y,  @strings

Minimization to zero:

        $min = reduce any(^x,^y)<0 ? 0 : ^x<^y ? ^x : ^y,  @numbers


        @triples = @{ reduce sub($;$$$){ [@{shift},[@_]] }, [], @singles };


        $sorted = reduce { push @{$_[0][$_[1]%2]}, $_[1]; $_[0] }

        # or, more cleanly:

        $sorted = reduce { push @{^0->[ ^1 % 2 ]},^1; ^0 }, [[],[]], @numbers;

Accumulative sequence generation:

        @increase = reduce ^value + ^delta, $original, @bonuses;

        @growth = reduce ^value * ^rate, $principal, @annual_interest_rates;


Extend Graham's List::Util, I'd imagine.


The List::Util module

RFC 23: Higher order functions

RFC 128: Subroutines: Extend subroutine contexts to include named parameters and lazy arguments

RFC 199: Short-circuiting built-in functions and user-defined subroutines