A better explanation of the Perl6 code might help somewhat.

If you look at Re: Challenge: Perl 5: lazy sameFringe()? (threads::Gather Configurably truely lazy or semi-lazy), you see a Perl5 implementation that more closely mirrors the Haskell variant.

It uses a home brewed implementation of take & gather that uses a thread and a queue under the covers to provide a truly lazy process.

That homebrew take/gather looks like this:

#! perl -slw
package threads::Gather;
use strict;
use Exporter;
use threads;
use threads::Q;

our @ISA = qw[ Exporter threads::Q ];
our @EXPORT = qw[ take gather ];

sub take;

sub gather (&$@) {
    no strict 'refs';# no warnings 'redefine';
    my( $code, $Qsize ) = ( shift, shift );
    my $Q = threads::Q->new( $Qsize );
    my $caller = caller;
    local *{ "$caller\:\:take" } = sub (_) { $Q->nq( @_ ); };
    local $^R = $code;
    async( sub{ &$code; $Q->nq( undef ); }, @_ )->detach;
    return sub { $Q->dq; };
}

return 1 if caller;
[download]

The take() sub is only available within the gather code block, and simple pushes its argument(s) onto a queue.

The code block itself is run in a separate thread; and the return of the gather sub is an iterator that simply dequeues values from the queue.

If teh size of the queue is set to 1, then each it take() will block the queue until the value it pushed is popped off using the iterator.

Not efficient -- a thread swap for every leaf -- but truly lazy.

If you supply a bigger queue size than one -- on the call to gather(), then gather block will be able to take() that many values before blocking and a thread swap is forces; thus you get a 'batching' behaviour which is more efficient.

This is (I suspect) the intent of the perl6 take/gather "at some future point in time", but currently it take is simply a push to a hidden array and once all the values have been collected, the gather subroutine iterates over that array popping them off as it goes. (See Perl6::Gather for a crude Perl5 implementation.)

But, as of yet -- and if I am any judge, for the foreseeable future -- that "at some future point in time" is unlikely to ever arrive.

Not that threading is the only way a lazy take/gather could be implemented. It could be done today in Perl5 using Coro if that runs where you live.

It could also be done using green (user space) threading; or continuations; or go-style goroutines. And if you believe the P6 specs, it intends to support all of those and more.

But, when (to my knowledge) there has been no (ZERO) attempt to provide and flavour of multitasking in any of the p6-ish interpreters, it doesn't look likely. YOU cannot add this stuff successfully as an after thought; you have to architect it in from the ground up or you end up with iThreads or similar.

And it is actually quite easy to do, if you do it from the start. As soon as the run-loop/dispatcher is capable of executing any single opcode, it should be possible to start two copies each in its own thread and dispatch them concurrently.

Heck the all fringe($a) Z=== fringe($b) alone is crazy enough to require two pages of explanation.

I'm far from expert in P6, but I don't have a problem with that line. The Z=== looks a bit weird, (but so did <=> and =~ etc. when I first came to perl5), but its obviously some form of comparison operator.

all is like the function of the same name in List::MoreUtils. Only true if all the arguments are true, and short-circuiting as soon as the first one is false.

So, if all the fringes of $a are equal to all the fringes of $b, the trees are equivalent. Seems clear enough, even if I'd have to look up the details. (I had to do that for the Haskell code; and I often have to do the same for C-runtime routines and the more obscure Perl built-ins.)