develooper Front page | perl.perl6.language.data | Postings from August 2000

RFC 90 (v2) Builtins: merge() and demerge()

From:
Perl6 RFC Librarian
Date:
August 29, 2000 18:22
Subject:
RFC 90 (v2) Builtins: merge() and demerge()
Message ID:
20000830012240.14846.qmail@tmtowtdi.perl.org
This and other RFCs are available on the web at
  http://dev.perl.org/rfc/

=head1 TITLE

Builtins: merge() and demerge()

=head1 VERSION

  Maintainer: Jeremy Howard <j@howard.fm>
  Date: 10 August 2000
  Last modified: 29 August 2000
  Mailing List: perl6-language-data@perl.org
  Version: 2
  Number: 90
  Status: Developing

=head1 ABSTRACT

It is proposed that two new functions, C<merge>, and C<demerge>, be added
to Perl. C<merge(@list1, @list2, ...)> would return a list that
interleaved its arguments. C<demerge($num_lists, @list)> would reverse
this operation.

=head1 CHANGES

=head2 Since v1

=over 4

=item *

Moved list to perl6-language-data@perl.org

=item *

Changed name from zip/unzip

=item *

Pass lists directly in examples, not references

=item *

Change 2nd argument from $list_size to $num_lists

=back

=head1 DESCRIPTION

It is proposed that Perl implement a function called C<merge> that
interleaves the arguments of arrays together, and is evaluated lazily.
For instance:

  @a = (1,3,5);
  @b = (2,4,6);
  @merged_list = merge(@a,@b);   # (1,2,3,4,5,6)

This makes it easy to operate on multiple lists using flexible reduction
functions:

  $sum_xy = sub {reduce ^last+^x*^y, merge($_[0], $_[1])};
  print $sum_xy->(@a, @b);   # Prints '44', i.e. 1*2+3*4+5*6

In order to reverse this operation we need an C<demerge> function:

  @merged_list = merge(@a,@b);   # (1,2,3,4,5,6)
  @demerged_list = demerge(2, @merged_list);   # ([1,3,5], [2,4,6])

The second argument to C<demerge> is the number of lists that are to be
created (i.e. the number of lists that would have been C<merge>d for this
to reverse the operation).

If the list to be demerged is not an exact multiple of the partition size,
the final list references are not padded--their length is one less than
the list size. For example:

  @list = (1..7);
  @demerged_list2 = demerge(3, @list);   # ([1,4,7], [2,5], [3,6])
  
=head1 IMPLEMENTATION

The C<merge> and C<demerge> functions should be evaluated lazily.

Effectively, C<merge> creates an iterator over multiple lists. If used as
part of a reduction, the actual interleaved list need never be created.
For instance:

  $sum_xy = sub {reduce ^last+^x*^y, merge($_[0], $_[1])};
  $answer = $sum_xy->(@a, @b);
  
should be evaluated as if it read:

  $answer = 0;
  $answer += $a[$_] * $b[$_] for (0..$#a-1));
  
which does not need to create an intermediate list.

=head1 REFERENCES

RFC 23: Higher order functions

RFC 76: Builtin: reduce

RFC 91: Builtin: partition




nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About