Perl Monk, Perl Meditation PerlMonks

### Re: Hamming Sequences and Lazy Lists

by Roy Johnson (Monsignor)
 on Mar 21, 2005 at 17:45 UTC ( #441248=note: print w/replies, xml ) Need Help??

in reply to Hamming Sequences and Lazy Lists

This solution is extremely similar to the Haskell one in both structure and technique -- as much of a direct translation as I could manage. I had to roll a couple of tools, but they are elegantly in keeping with functional programming style.

I was really pleased with how this all came together.

```use strict;
use warnings;

# A stream is an array ref, in which the first element is an ordinary
# value, and the second element is a continuation: a sub that yields
# a stream. In other words, a lazy list.

# Takes an ordinary list and turns it into a stream
sub stream_up {
my (\$x, @rest) = @_;
return [ \$x, sub { @rest ? stream_up(@rest) : [] } ];
}

# Yields the first N elements from a stream
sub take {
my (\$N, \$x_xs) = @_;
\$N > 0 or return ();
if (!@\$x_xs) { return () }
my (\$x, \$xs) = @\$x_xs;
return(\$x, take(\$N-1, \$xs->()));
}

# merge takes two streams, and returns one
sub merge {
my (\$x_xs, \$y_ys) = @_;
if (!@\$x_xs)  { return \$y_ys }
if (!@\$y_ys)  { return \$x_xs }
my (\$x, \$xs) = @\$x_xs;
my (\$y, \$ys) = @\$y_ys;
if (\$x < \$y)  { return [\$x, sub { merge(\$xs->(), \$y_ys)  } ] }
if (\$x > \$y)  { return [\$y, sub { merge(\$x_xs  , \$ys->())} ] }
if (\$x == \$y) { return [\$x, sub { merge(\$xs->(), \$ys->())} ] }
}

# Like map, but applies coderef to stream, returning a stream
sub stream_map {
my (\$coderef, \$x_xs) = @_;
if (!@\$x_xs) { return \$x_xs }
my (\$x, \$xs) = @\$x_xs;
local \$_ = \$x;
return [\$coderef->(\$x), sub { stream_map(\$coderef, \$xs->()) }];
}

# genHam takes a stream and returns a stream
sub genHam {
my (\$x_xs) = @_;
if (!@\$x_xs)  { return \$x_xs }
my (\$x, \$xs) = @\$x_xs;
my \$out;
\$out = merge([1, sub {stream_map(sub{\$_ * \$x}, \$out)}], genHam(\$xs
+->()));
}

print "\$_\n" for take 20, genHam stream_up(2,3,5);

Caution: Contents may have been coded under pressure.

Create A New User
Node Status?
node history
Node Type: note [id://441248]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (5)
As of 2018-03-20 08:35 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (248 votes). Check out past polls.

Notices?