Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
Here's a pretty general solution, I think. Full code below.
my @first_200 = take(200, gen_hamm(2, 3, 5)); print "@first_200\n";
yields
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 60 +64 72 75 80 81 90 96 100 108 120 125 128 135 144 150 160 162 180 192 +200 216 225 240 243 250 256 270 288 300 320 324 360 375 384 400 405 4 +32 450 480 486 500 512 540 576 600 625 640 648 675 720 729 750 768 80 +0 810 864 900 960 972 1000 1024 1080 1125 1152 1200 1215 1250 1280 12 +96 1350 1440 1458 1500 1536 1600 1620 1728 1800 1875 1920 1944 2000 2 +025 2048 2160 2187 2250 2304 2400 2430 2500 2560 2592 2700 2880 2916 +3000 3072 3125 3200 3240 3375 3456 3600 3645 3750 3840 3888 4000 4050 + 4096 4320 4374 4500 4608 4800 4860 5000 5120 5184 5400 5625 5760 583 +2 6000 6075 6144 6250 6400 6480 6561 6750 6912 7200 7290 7500 7680 77 +76 8000 8100 8192 8640 8748 9000 9216 9375 9600 9720 10000 10125 1024 +0 10368 10800 10935 11250 11520 11664 12000 12150 12288 12500 12800 1 +2960 13122 13500 13824 14400 14580 15000 15360 15552 15625 16000 1620 +0
This output came out instantenously. The merge and gen_hamm procedures have similar forms as the originals in Haskell, although they're nowhere nearly as streamlined:
sub gen_hamm { return [] unless @_; my $x = shift; my $out; $out = merge( ll_new( 1, memoize( sub { ll_map( sub { $x * $_[ 0 ] }, $out ); } ) ), gen_hamm( @_ ) ); return $out; } sub merge { my ( $x, $y ) = @_; return $y if ll_null_p( $x ); return $x if ll_null_p( $y ); my ( $x0, $y0 ) = map head( $_ ), ( $x, $y ); if ( $x0 < $y0 ) { return ll_new( $x0, memoize( sub { merge( tail( $x ), $y ) } ) ); } elsif ( $y0 < $x0 ) { return ll_new( $y0, memoize( sub { merge( $x, tail( $y ) ) } ) ); } else { return ll_new( $x0, memoize( sub { merge( tail( $x ), tail( $y ) ); } ) ); } }
This implementation is general beyond the Hamming problem. For example, we can define a Fibonacci lazy list like this:
my $fibs; $fibs = ll_new(0, memoize(sub { ll_new(1, memoize(sub { ll_add(tail($fibs), $fibs); })) })); my @first_100 = take( 100, $fibs ); print "@first_100\n";
The output of the above came out instantaneously:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 1 +0946 17711 28657 46368 75025 121393 196418 317811 514229 832040 13462 +69 2178309 3524578 5702887 9227465 14930352 24157817 39088169 6324598 +6 102334155 165580141 267914296 433494437 701408733 1134903170 183631 +1903 2971215073 4807526976 7778742049 12586269025 20365011074 3295128 +0099 53316291173 86267571272 139583862445 225851433717 365435296162 5 +91286729879 956722026041 1548008755920 2504730781961 4052739537881 65 +57470319842 10610209857723 17167680177565 27777890035288 449455702128 +53 72723460248141 117669030460994 190392490709135 308061521170129 498 +454011879264 806515533049393 1.30496954492866e+15 2.11148507797805e+1 +5 3.41645462290671e+15 5.52793970088476e+15 8.94439432379146e+15 1.44 +723340246762e+16 2.34167283484677e+16 3.78890623731439e+16 6.13057907 +216116e+16 9.91948530947555e+16 1.60500643816367e+17 2.59695496911123 +e+17 4.2019614072749e+17 6.79891637638612e+17 1.1000877783661e+18 1.7 +7997941600471e+18 2.88006719437082e+18 4.66004661037553e+18 7.5401138 +0474635e+18 1.22001604151219e+19 1.97402742198682e+19 3.1940434634990 +1e+19 5.16807088548583e+19 8.36211434898484e+19 1.35301852344707e+20 +2.18922995834555e+20

the lowliest monk


sub gen_hamm { return [] unless @_; my $x = shift; my $out; $out = merge( ll_new( 1, memoize( sub { ll_map( sub { $x * $_[ 0 ] }, $out ); } ) ), gen_hamm( @_ ) ); return $out; } sub merge { my ( $x, $y ) = @_; return $y if ll_null_p( $x ); return $x if ll_null_p( $y ); my ( $x0, $y0 ) = map head( $_ ), ( $x, $y ); if ( $x0 < $y0 ) { return ll_new( $x0, memoize( sub { merge( tail( $x ), $y ) } ) ); } elsif ( $y0 < $x0 ) { return ll_new( $y0, memoize( sub { merge( $x, tail( $y ) ) } ) ); } else { return ll_new( $x0, memoize( sub { merge( tail( $x ), tail( $y ) ); } ) ); } } sub ll_map { my $proc = shift; my $s = shift; if ( ll_null_p( $s ) ) { return []; } else { ll_new( $proc->( head( $s ) ), memoize( sub { ll_map( $proc, tail( $s ) ) } ) ); } } sub take { my $n = shift; my $s = shift; return $n < 1 ? () : ( head( $s ), take( $n - 1, tail( $s ) ) ); } sub memoize (&) { my $proc = shift; my $already_run = 0; my $result; return sub { return $result if $already_run; $already_run = 1; return $result = $proc->(); } } sub ll_new { [ @_[ 0, 1 ] ]; } sub force { my $sub = shift; $sub->(); } sub head { shift->[ 0 ]; } sub tail { force( shift->[ 1 ] ); } sub ll_null_p { !@{ $_[ 0 ] }; } sub element_wise { my $op = shift; my ( $s1, $s2 ) = @_; ll_new( $op->( head( $s1 ), head( $s2 ) ), memoize( sub { element_wise( $op, tail( $s1 ), tail( $s2 ) ); } ) ); } sub ll_add { element_wise( sub { $_[ 0 ] + $_[ 1 ] }, @_ ); }

In reply to Re: Hamming Sequences and Lazy Lists by tlm
in thread Hamming Sequences and Lazy Lists by tall_man

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others scrutinizing the Monastery: (5)
    As of 2014-12-19 03:19 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      Is guessing a good strategy for surviving in the IT business?





      Results (70 votes), past polls