Perl: the Markov chain saw PerlMonks

### Re: Hamming Sequences and Lazy Lists

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

in reply to Hamming Sequences and Lazy Lists

Here is a lazy-list example of merge, with one of its arguments being a finite list, and the other an infinite list. I may not get around to figuring out the Hamming generator, but I think the techniques I've employed here tell you how it can be done.
```use strict;
use warnings;

# Merge takes two iterators, which can be called
# with no arguments, in which case they iterate, returning
# their next value; or with a string 'peek', which will
# yield the next value without effectively shifting it.
# Exhausted iterators return undef on all subsequent calls
#
# Merge itself is an iterator, returning the next element in
# the merged series, plus a continuation coderef
sub merge {
my (\$a, \$b) = @_;
my (\$car_a, \$car_b) = (\$a->('peek'), \$b->('peek'));
# Base case: if one of them is empty, return the other
defined \$car_a or return (\$b->(), sub {merge(\$a, \$b)});
defined \$car_b or return (\$a->(), sub {merge(\$a, \$b)});

# Pull off lesser (both if equal) first element(s)
my \$low_car;
if (\$car_a <= \$car_b) { \$low_car = \$a->() }
if (\$car_b <= \$car_a) { \$low_car = \$b->() }

return (\$low_car, sub {merge(\$a, \$b)} );
}

my \$I1 = do {
my @arr = (1..10);
sub {
if (@arr == 0) {
return undef;
}
elsif (@_) { # should be peek, but any other arg works (undocu
+mented)
return \$arr[0];
}
else {
return shift @arr;
}
}
};

my \$I2 = do {
my \$i = 2;
sub {
if (@_) {
return \$i;
} else {
my \$i_was = \$i; \$i += 2; return \$i_was;
}
}
};

my \$iterations_to_print = 30;
for ( my (\$elem, \$cont) = merge(\$I1, \$I2);
\$iterations_to_print-- > 0;
(\$elem, \$cont) = \$cont->()
) {
print "<\$elem>\n";
}

Caution: Contents may have been coded under pressure.

Replies are listed 'Best First'.
Re^2: Hamming Sequences and Lazy Lists
by Limbic~Region (Chancellor) on Mar 17, 2005 at 16:55 UTC
Roy Johnson,
I don't think this is right. It is my understanding that the results should be the multiples of the factors merged minus duplicates. If you change \$iterations_to_print = 23 and @arr = (2,3,5), where is 15 in the results for instance? See Re: Hamming Sequences and Lazy Lists for my understanding and implementation of the problem.

Cheers - L~R

I did not implement Hamming here; only merging of two list iterators. But I have just posted a lazy Hamming solution.

Caution: Contents may have been coded under pressure.
Roy Johnson,
Ok - my mistake. In fact, I completely missed the boat on the entire problem. I was so focused on lazy evaluation that I misunderstood "how do you generate the series of numbers composed of a given list of prime factors, where each can be used an unlimited number of times?" To me, that any positive multiple of any factor was valid.

Cheers - L~R

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

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (6)
As of 2017-11-20 23:17 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In order to be able to say "I know Perl", you must have:

Results (294 votes). Check out past polls.

Notices?