Recursive lazy lists?

[Mark J. Reed]

Sorry if this has come up before and I missed it, but I just came across
this Haskell function to convert from Gray code back to normal binary (as
lists of 1s and 0s; full code at
http://rosettacode.org/mw/index.php/Gray_code#Haskell):

gray2bin [] = []
gray2bin (x:xs) = bin
  where bin = x : zipWith

xor2 xs bin


Notice how the definition of 'bin' is recursive.  Does Perl6's variety of
laziness support this sort of definition?
It's not an infinite list; zipWith stops zipping as soon as either list is
empty.  But the self-reference in the definition means it still has to be
computed lazily.

--
Mark J. Reed 

Re: Recursive lazy lists?

[Bruce Gray]

On Jul 30, 2011, at 8:30 AM, Mark J. Reed wrote:

--snip--
Does Perl6's variety of
laziness support this sort of definition?
It's not an infinite list; zipWith stops zipping as soon as either  
list is
empty.  But the self-reference in the definition means it still has  
to be

computed lazily.


Yes, Perl 6 does support laziness in this sort of definition, via "run- 
time binding".

I was delighted to find that it already works in Rakudo!
(We also support Haskell's cool pictogram-style declarations.)

Here is a quick conversion of the Haskell solution into Perl 6; its  
output

(when run in Rakudo) exactly matches the output of my iterative Perl 6
solution (http://rosettacode.org/mw/index.php/Gray_code#Perl_6):

our multi sub infix: ( $x, $y ) { ( $x + $y ) % 2 };

multi bin_to_gray ( [] ) { [] }
multi bin_to_gray ( [$head, *@tail] ) {
   return [ $head, ( @tail Zxor2 ($head, @tail) ) ];
}

multi gray_to_bin ( [] ) { [] }
multi gray_to_bin ( [$head, *@tail] ) {
   my @bin := $head, (@tail Zxor2 @bin); # Note the recursive  
definition via bound array

   return @bin.flat;
}

for ^32 -> $n {
   my @b = $n.fmt('%b').comb;
   my $g = bin_to_gray( @b );
   my $d = gray_to_bin( $g );
   printf "%2d: %5b => %5s => %5s: %2d\n", $n, $n, $g.join, $d.join, : 
2($d.join);

   die if :2($d.join) != $n;
}

--
Hope this helps,
Bruce Gray (Util of PerlMonks)

Re: Recursive lazy lists?

[Mark J. Reed]

On Sat, Jul 30, 2011 at 6:02 PM, Bruce Gray  wrote:

>
> Yes, Perl 6 does support laziness in this sort of definition, via "run-time
> binding".
>

Very cool. Thanks!


> Here is a quick conversion of the Haskell solution into Perl 6; its output
> (when run in Rakudo) exactly matches the output of my iterative Perl 6
> solution 
> (http://rosettacode.org/mw/**index.php/Gray_code#Perl_6
> ):
>
> our multi sub infix: ( $x, $y ) { ( $x + $y ) % 2 };
>

Why did you need to define this yourself instead of just using +^ ?


-- 
Mark J. Reed 

Re: Recursive lazy lists?

[Bruce Gray]

On Jul 30, 2011, at 6:40 PM, Mark J. Reed wrote:

On Sat, Jul 30, 2011 at 6:02 PM, Bruce Gray   
wrote:

--snip--

our multi sub infix: ( $x, $y ) { ( $x + $y ) % 2 };


Why did you need to define this yourself instead of just using +^ ?


Umm, because that is what was done in the Haskell code I was  
translating?
That is my only excuse for my oversight. You are correct; in fact,  
Solomon
Foster already pointed this out to me, and I have already posted the  
revised

version on RC as a second solution:
http://rosettacode.org/wiki/Gray_code#Perl_6

--
Hope this helps,
Bruce Gray (Util of PerlMonks)