This and other RFCs are available on the web at http://dev.perl.org/rfc/ =head1 TITLE Builtin: reduce =head1 VERSION Maintainer: Damian Conway <[EMAIL PROTECTED]> Date: 10 August 2000 Last Modified: 20 Sep 2000 Mailing List: [EMAIL PROTECTED] Number: 76 Version: 4 Status: Frozen Frozen since: v2 Note: Really Really Frozen this time =head1 ABSTRACT This RFC proposes a built-in C<reduce> function, modelled after Graham Barr's C<reduce> subroutine from the List::Utils module (a.k.a. The Module Formerly Known As builtin.pm). =head1 DESCRIPTION A new built-in -- C<reduce> -- is proposed. This function would take an block, subroutine reference, or curried function (hereafter referred to as I<the reduction subroutine>), and call it repeatedly to reduce the remaining arguments (hereafter, referred to as C<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 I<before> the reduction begins (assuming C<reduce> and the other list ops aren't made lazy in Perl 6), by determining the total number of elements to be reduced (I<E>), the maximal number of elements that may be procesed on each reduction step (I<R>), and the minimal number of elements that may be processed on each step (I<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, C<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 C<reduce>. In a list context, a list of all the interim values, plus the final value, would be returned. =head1 EXAMPLES Summation: $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. Production: $prod = reduce {$_[0]*$_[1]} 1, @numbers; $prod = reduce sub{$_[0]*$_[1]}, 1, @numbers; $prod = reduce ^_*^_, 1, @numbers; Minimization: $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 Collection: @triples = @{ reduce sub($;$$$){ [@{shift},[@_]] }, [], @singles }; Separation: $sorted = reduce { push @{$_[0][$_[1]%2]}, $_[1]; $_[0] } [[],[]], @numbers; # 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; =head1 IMPLEMENTATION Extend Graham's List::Util, I'd imagine. =head1 REFERENCES 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
