package HOP::Stream;
use warnings;
use strict;
use base 'Exporter';
our @EXPORT_OK = qw(
cutsort
drop
filter
head
insert
is_node
iterator_to_stream
list_to_stream
append
merge
node
promise
show
tail
transform
upto
upfrom
);
our %EXPORT_TAGS = ( 'all' => \@EXPORT_OK );
=head1 NAME
HOP::Stream - "Higher Order Perl" streams
=head1 VERSION
Version 0.03
=cut
our $VERSION = '0.03';
=head1 SYNOPSIS
=head1 DESCRIPTION
This package is based on the Stream.pm code from the book "Higher Order Perl",
by Mark Jason Dominus.
A stream is conceptually similar to a linked list. However, we may have an
infinite stream. As infinite amounts of data are frequently taxing to the
memory of most systems, the tail of the list may be a I<promise>. A promise,
in this context, is merely a promise that the code will compute the rest of
the list if necessary. Thus, the rest of the list does not exist until
actually needed.
The documentation here is not complete. See "Higher Order Perl" by Mark
Dominus for a full explanation. Further, this is B<ALPHA> code. Patches
and suggestions welcome.
=head1 EXPORT
The following functions may be exported upon demand. ":all" may be specified
if you wish everything exported.
=over 4
=item * cutsort
=item * drop
=item * filter
=item * head
=item * insert
=item * iterator_to_stream
=item * list_to_stream
=item * append
=item * merge
=item * node
=item * promise
=item * show
=item * tail
=item * transform
=item * upto
=item * upfrom
=back
=head1 FUNCTIONS
=head2 node
my $node = node( $head, $tail );
Returns a node for a stream.
The tail of the node may be a I<promise> to compute the actual tail when
needed.
=cut
sub node {
my ( $h, $t ) = @_;
bless [ $h, $t ], __PACKAGE__;
}
##############################################################################
=head2 head
my $head = head( $node );
This function returns the head of a stream.
=cut
sub head {
my ($s) = @_;
return undef unless is_node($s);
$s->[0];
}
##############################################################################
=head2 tail
my $tail = tail( $stream );
Returns the I<tail> of a stream.
=cut
sub tail {
my ($s) = @_;
return undef unless is_node($s);
if ( is_promise( $s->[1] ) ) {
$s->[1] = $s->[1]->();
}
$s->[1];
}
##############################################################################
=head2 is_node
if ( is_node($tail) ) {
...
}
Returns true if the tail of a node is a node. Generally this function is
used internally.
=cut
sub is_node {
# Note that this is *not* bad code. Nodes aren't really objects. They're
# merely being blessed to ensure that we can disambiguate them from array
# references.
UNIVERSAL::isa( $_[0], __PACKAGE__ );
}
##############################################################################
=head2 is_promise
if ( is_promise($tail) ) {
...
}
Returns true if the tail of a node is a promise. Generally this function is
used internally.
=cut
sub is_promise {
UNIVERSAL::isa( $_[0], 'CODE' );
}
##############################################################################
=head2 promise
my $promise = promise { ... };
A utility function with a code prototype (C<< sub promise(&); >>) allowing one
to specify a coderef with curly braces and omit the C<sub> keyword.
=cut
sub promise (&) { $_[0] }
##############################################################################
=head2 show
show( $stream, [ $number_of_nodes ] );
This is a debugging function that will return a text representation of
C<$number_of_nodes> of the stream C<$stream>.
Omitting the second argument will print all elements of the stream. This is
not recommended for infinite streams (duh).
The elements of the stream will be separated by the current value of C<$">.
=cut
sub show {
my ( $s, $n ) = @_;
my $show = '';
while ( $s && ( !defined $n || $n-- > 0 ) ) {
$show .= head($s) . $";
$s = tail($s);
}
return $show;
}
##############################################################################
=head2 drop
my $head = drop( $stream );
This is the C<shift> function for streams. It returns the head of the stream
and and modifies the stream in-place to be the tail of the stream.
=cut
sub drop {
my $h = head( $_[0] );
$_[0] = tail( $_[0] );
return $h;
}
##############################################################################
=head2 transform
my $new_stream = transform { $_[0] * 2 } $old_stream;
This is the C<map> function for streams. It returns a new stream.
=cut
sub transform (&$) {
my $f = shift;
my $s = shift;
return unless $s;
node( $f->( head($s) ), promise { transform ( $f, tail($s) ) } );
}
##############################################################################
=head2 filter
my $new_stream = filter { $_[0] % 2 } $old_stream;
This is the C<grep> function for streams. It returns a new stream.
=cut
sub filter (&$) {
my $f = shift;
my $s = shift;
until ( !$s || $f->( head($s) ) ) {
drop($s);
}
return if !$s;
node( head($s), promise { filter ( $f, tail($s) ) } );
}
##############################################################################
=head2 merge
my $merged_stream = merge( $stream1, $stream2 );
This function takes two streams assumed to be in sorted order and merges them
into a new stream, also in sorted order.
=cut
sub merge {
my ( $S, $T ) = @_;
return $T unless $S;
return $S unless $T;
my ( $s, $t ) = ( head($S), head($T) );
if ( $s > $t ) {
node( $t, promise { merge( $S, tail($T) ) } );
}
elsif ( $s < $t ) {
node( $s, promise { merge( tail($S), $T ) } );
}
else {
node( $s, promise { merge( tail($S), tail($T) ) } );
}
}
##############################################################################
=head2 append
my $merged_stream = append( $stream1, $stream2 );
This function takes a list of streams and attaches them together head-to-tail
into a new stream.
=cut
sub append {
my (@streams) = @_;
while (@streams) {
my $h = drop( $streams[0] );
return node( $h, promise { append(@streams) } ) if defined($h);
shift @streams;
}
return undef;
}
##############################################################################
=head2 list_to_stream
my $stream = list_to_stream(@list);
Converts a list into a stream. The final item of C<list> should be a promise
or another stream. Thus, to generate the numbers one through ten, one could
do this:
my $stream = list_to_stream( 1 .. 9, node(10, undef) );
# or
my $stream = list_to_stream( 1 .. 9, node(10) );
=cut
sub list_to_stream {
my $node = pop;
$node = node($node) unless is_node($node);
while (@_) {
my $item = pop;
$node = node( $item, $node );
}
$node;
}
##############################################################################
=head2 iterator_to_stream
my $stream = iterator_to_stream($iterator);
Converts an iterator into a stream. An iterator is merely a code reference
which, when called, keeps returning elements until there are no more elements,
at which point it returns "undef".
=cut
sub iterator_to_stream {
my $it = shift;
my $v = $it->();
return unless defined $v;
node( $v, sub { iterator_to_stream($it) } );
}
##############################################################################
=head2 upto
my $stream = upto($from_num, $to_num);
Given two numbers, C<$from_num> and C<$to_num>, returns an iterator which will
return all of the numbers between C<$from_num> and C<$to_num>, inclusive.
=cut
sub upto {
my ( $m, $n ) = @_;
return if $m > $n;
node( $m, promise { upto( $m + 1, $n ) } );
}
##############################################################################
=head2 upfrom
my $stream = upfrom($num);
Similar to C<upto>, this function returns a stream which will generate an
infinite list of numbers starting from C<$num>.
=cut
sub upfrom {
my ($m) = @_;
node( $m, promise { upfrom( $m + 1 ) } );
}
sub insert (\@$$);
sub cutsort {
my ( $s, $cmp, $cut, @pending ) = @_;
my @emit;
while ($s) {
while ( @pending && $cut->( $pending[0], head($s) ) ) {
push @emit, shift @pending;
}
if (@emit) {
return list_to_stream( @emit,
promise { cutsort( $s, $cmp, $cut, @pending ) } );
}
else {
insert( @pending, head($s), $cmp );
$s = tail($s);
}
}
return list_to_stream( @pending, undef );
}
sub insert (\@$$) {
my ( $a, $e, $cmp ) = @_;
my ( $lo, $hi ) = ( 0, scalar(@$a) );
while ( $lo < $hi ) {
my $med = int( ( $lo + $hi ) / 2 );
my $d = $cmp->( $a->[$med], $e );
if ( $d <= 0 ) {
$lo = $med + 1;
}
else {
$hi = $med;
}
}
splice( @$a, $lo, 0, $e );
}
=head1 AUTHOR
Mark Dominus, maintained by Curtis "Ovid" Poe, C<< <ovid@cpan.org> >>
=head1 BUGS
Please report any bugs or feature requests to
C<bug-hop-stream@rt.cpan.org>, or through the web interface at
L<http://rt.cpan.org/NoAuth/ReportBug.html?Queue=HOP-Stream>.
I will be notified, and then you'll automatically be notified of progress on
your bug as I make changes.
=head1 ACKNOWLEDGEMENTS
Many thanks to Mark Dominus and Elsevier, Inc. for allowing this work to be
republished.
=head1 COPYRIGHT & LICENSE
Code derived from the book "Higher-Order Perl" by Mark Dominus, published by
Morgan Kaufmann Publishers, Copyright 2005 by Elsevier Inc.
=head1 ABOUT THE SOFTWARE
All Software (code listings) presented in the book can be found on the
companion website for the book (http://perl.plover.com/hop/) and is
subject to the License agreements below.
=head1 LATEST VERSION
You can download the latest versions of these modules at
L<http://github.com/Ovid/hop/>. Feel free to fork and make changes.
=head1 ELSEVIER SOFTWARE LICENSE AGREEMENT
Please read the following agreement carefully before using this Software. This
Software is licensed under the terms contained in this Software license
agreement ("agreement"). By using this Software product, you, an individual,
or entity including employees, agents and representatives ("you" or "your"),
acknowledge that you have read this agreement, that you understand it, and
that you agree to be bound by the terms and conditions of this agreement.
Elsevier inc. ("Elsevier") expressly does not agree to license this Software
product to you unless you assent to this agreement. If you do not agree with
any of the following terms, do not use the Software.
=head1 LIMITED WARRANTY AND LIMITATION OF LIABILITY
YOUR USE OF THIS SOFTWARE IS AT YOUR OWN RISK. NEITHER ELSEVIER NOR ITS
LICENSORS REPRESENT OR WARRANT THAT THE SOFTWARE PRODUCT WILL MEET YOUR
REQUIREMENTS OR THAT ITS OPERATION WILL BE UNINTERRUPTED OR ERROR-FREE. WE
EXCLUDE AND EXPRESSLY DISCLAIM ALL EXPRESS AND IMPLIED WARRANTIES NOT STATED
HEREIN, INCLUDING THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
PARTICULAR PURPOSE. IN ADDITION, NEITHER ELSEVIER NOR ITS LICENSORS MAKE ANY
REPRESENTATIONS OR WARRANTIES, EITHER EXPRESS OR IMPLIED, REGARDING THE
PERFORMANCE OF YOUR NETWORK OR COMPUTER SYSTEM WHEN USED IN CONJUNCTION WITH
THE SOFTWARE PRODUCT. WE SHALL NOT BE LIABLE FOR ANY DAMAGE OR LOSS OF ANY
KIND ARISING OUT OF OR RESULTING FROM YOUR POSSESSION OR USE OF THE SOFTWARE
PRODUCT CAUSED BY ERRORS OR OMISSIONS, DATA LOSS OR CORRUPTION, ERRORS OR
OMISSIONS IN THE PROPRIETARY MATERIAL, REGARDLESS OF WHETHER SUCH LIABILITY IS
BASED IN TORT, CONTRACT OR OTHERWISE AND INCLUDING, BUT NOT LIMITED TO,
ACTUAL, SPECIAL, INDIRECT, INCIDENTAL OR CONSEQUENTIAL DAMAGES. IF THE
FOREGOING LIMITATION IS HELD TO BE UNENFORCEABLE, OUR MAXIMUM LIABILITY TO YOU
SHALL NOT EXCEED THE AMOUNT OF THE PURCHASE PRICE PAID BY YOU FOR THE SOFTWARE
PRODUCT. THE REMEDIES AVAILABLE TO YOU AGAINST US AND THE LICENSORS OF
MATERIALS INCLUDED IN THE SOFTWARE PRODUCT ARE EXCLUSIVE.
YOU UNDERSTAND THAT ELSEVIER, ITS AFFILIATES, LICENSORS, SUPPLIERS AND AGENTS,
MAKE NO WARRANTIES, EXPRESSED OR IMPLIED, WITH RESPECT TO THE SOFTWARE
PRODUCT, INCLUDING, WITHOUT LIMITATION THE PROPRIETARY MATERIAL, AND
SPECIFICALLY DISCLAIM ANY WARRANTY OF MERCHANTABILITY OR FITNESS FOR A
PARTICULAR PURPOSE.
IN NO EVENT WILL ELSEVIER, ITS AFFILIATES, LICENSORS, SUPPLIERS OR AGENTS, BE
LIABLE TO YOU FOR ANY DAMAGES, INCLUDING, WITHOUT LIMITATION, ANY LOST
PROFITS, LOST SAVINGS OR OTHER INCIDENTAL OR CONSEQUENTIAL DAMAGES, ARISING
OUT OF YOUR USE OR INABILITY TO USE THE SOFTWARE PRODUCT REGARDLESS OF WHETHER
SUCH DAMAGES ARE FORESEEABLE OR WHETHER SUCH DAMAGES ARE DEEMED TO RESULT FROM
THE FAILURE OR INADEQUACY OF ANY EXCLUSIVE OR OTHER REMEDY.
=head1 SOFTWARE LICENSE AGREEMENT
This Software License Agreement is a legal agreement between the Author and
any person or legal entity using or accepting any Software governed by this
Agreement. The Software is available on the companion website
(http://perl.plover.com/hop/) for the Book, Higher-Order Perl, which is
published by Morgan Kaufmann Publishers. "The Software" is comprised of all
code (fragments and pseudocode) presented in the book.
By installing, copying, or otherwise using the Software, you agree to be bound
by the terms of this Agreement.
The parties agree as follows:
=over 4
=item 1 Grant of License
We grant you a nonexclusive license to use the Software for any purpose,
commercial or non-commercial, as long as the following credit is included
identifying the original source of the Software: "from Higher-Order Perl by
Mark Dominus, published by Morgan Kaufmann Publishers, Copyright 2005 by
Elsevier Inc".
=item 2 Disclaimer of Warranty.
We make no warranties at all. The Software is transferred to you on an "as is"
basis. You use the Software at your own peril. You assume all risk of loss for
all claims or controversies, now existing or hereafter, arising out of use of
the Software. We shall have no liability based on a claim that your use or
combination of the Software with products or data not supplied by us infringes
any patent, copyright, or proprietary right. All other warranties, expressed
or implied, including, without limitation, any warranty of merchantability or
fitness for a particular purpose are hereby excluded.
=item 3 Limitation of Liability.
We will have no liability for special, incidental, or consequential damages
even if advised of the possibility of such damages. We will not be liable for
any other damages or loss in any way connected with the Software.
=back
=cut
1; # End of HOP::Stream