The first argument to NestedLoops is the list of loops so

    [
        # First loop: all item indices
        [ 0..$#items ],

        # @items-1 subsequent loops:
        ( sub {
            # If we need more items:
            $sum[@_] < $target
                # then get more (unique) item indices
                ? [ ($_+1)..$#items ]
                # else don't get more items
                : []
        } ) x $#items,
    ],
[download]

becomes the equivalent of

for $_ (  0..$#items  ) {
    # ...
    for $_ (  @{ $sum[@_] < $target
        ? [ ($_+1)..$#items ] : [] }
    ) {
        # ...
        for $_ (  @{ $sum[@_] < $target
            ? [ ($_+1)..$#items ] : [] }
        ) {
            # ...
        }
    }
}
[download]

The sub { ... } in the original code is required to delay the running of the loop computation code instead of running it before NestedLoops is called (at which point $_ and other variables wouldn't contain the rigth values).

The list of items computed by the nested loops is passed to the subs as @_ and the currently innermost loop's variable is also put into $_ so you can use that as short-hand for $_[-1].

And this bit

        OnlyWhen => sub {
            # Compute sum of selected items as
            # sum of @_-1 items plus last item:
            $sum[@_]= $sum[$#_] + $items[$_[-1]];

            # Return subsets that match desired sum:
            return $sum[@_] == $target;
        },
[download]

just declares a sub that gets called to determine which lists to return. We'll pretend it is named when() below. And we'll replace the @_ in each $sum[@_] with a hard-coded value to simplify our 'translation' which becomes something close to:

@_= ();
for $_ (  0..$#items  ) {
    push @_, $_;
    push @return, [ @_ ]   if  when( @_ );
    for $_ (  @{ $sum[1] < $target
        ? [ ($_+1)..$#items ] : [] }
    ) {
        push @_, $_;
        push @return, [ @_ ]   if  when( @_ );
        for $_ (  @{ $sum[2] < $target
            ? [ ($_+1)..$#items ] : [] }
        ) {
            push @_, $_;
            push @return, [ @_ ]   if  when( @_ );
            # ...
            pop @_;
        }
        pop @_;
    }
    pop @_;
}
[download]

But instead of pushing each selected list into @return, each call to $iter->() returns the next list that would be pushed.

Note that we loop over indices so we can use ($_+1)..$#items to only loop over indices that we haven't already looped over.

Let's simplify the inner loops. The point of

$sum[@_] < $target ? [ ($_+1)..$#items ] : []
[download]

is to avoid looping any deeper if we don't need more items to add up (because we've already reached our desired total). Which can be more clearly written in our translation as

    next   if  $target <= $sum[@_];
[download]

(if we do our pops in continue blocks) so we can clarify our example to

@_= ();
for $_ (  0..$#items  ) {
    push @_, $_;
    push @return, [ @_ ]   if  when( @_ );
    next   if  $target <= $sum[1];
    for $_ (  ($_+1)..$#items  ) {
        push @_, $_;
        push @return, [ @_ ]   if  when( @_ );
        next   if  $target <= $sum[2];
        for $_ (  ($_+1)..$#items  ) {
            push @_, $_;
            push @return, [ @_ ]   if  when( @_ );
            # ...
        } continue {
            pop @_;
        }
    } continue {
        pop @_;
    }
} continue {
    pop @_;
}
[download]

Of course, we can't finish this translation because you can't write loops that nest to some arbitrary depth.

Fiinally, we use the iterator to get each desired set of indices. We use an array slice to convert the list of indices into a list of iitems:

while(  my @list= @items[ $iter->() ]  ) {
    warn "$target = sum( @list )\n";
}
[download]

I hope that helps explain how this works.

Thanks. It'll probably take a few more readings to take that all in, but on the surface it makes (more) sense to me now. I think I was part way there with understanding the calling syntax and general methodology of the algorithm, but this clarifies it.

The main problem I was commenting upon though is subtly different from understanding how to use NestedLoops. It's more a case of wrapping my brain around how to apply it to any given problem. I guess it is really no more complicated that coding a recursive routine and remembering that each piece of code will be run at all levels, but I've been doing recursion long enough that it has become second nature to think that way. This is like recursion, but different; and without the overhead.

The subtly seems to be to the $sum[ @_ ] = ... bit. It took this post for me to realise that @sum isn't really an array in terms of the algorithm (the absence of the postfix 's' would be a clue if you normally hold to that convention). It's really a stack of autovivified, level-specific, persistant 'local' storage. (I think!).

I stuck a print "@sum\n"; before the return in the OnlyWhen routine and it's interesting to watch the values iterate.

This definitely requires a good "cookbook" article (or book?) to stimulate exploration of it's uses and algorithms. If you have the time TPJ were asking for authors:)

---

Examine what is said, not who speaks.

"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail

The main problem I was commenting upon though is subtly different from understanding how to use NestedLoops.

Yes. I'd hoped my explanation might still help with the other problem (and help others understand the code)...

It's more a case of wrapping my brain around how to apply it to any given problem. I guess it is really no more complicated that coding a recursive routine and remembering [...]

Yeah, that certainly sounds like a difficult way to go about it. Instead, think of writing foreach loops. Does that help much? I could elaborate but I'd rather do that based on your response. I could go into how to write foreach loops but maybe that isn't something you need elaboration on. (:

- tye        

I knew tye's approach was based on a closure as an iterator. Allright, I understand that, so I'll take what I understand and try to build it up to what NestedLoops() does...