ETOOBUSY 🚀 minimal blogging for the impatient
A simplified recursive implementation of NestedLoops
TL;DR
Let’s look at a simplified implementation for what
NestedLoopsdoes.
In the previous post about Algorithm::Loops we took a look at
NestedLoops, a fine sub that allows building nested iterations
over a variable number of dimensions.
A possible implementation that is compatible in interface but only offers a subset of the functionalities is the following:
NestedLoopsRecursive.pm
862 B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#!/usr/bin/env perl
package NestedLoopsRecursive;
use strict;
use warnings;
use Exporter 'import';
our @EXPORT_OK = ('nested_loops_recursive');
exit sub {
nested_loops_recursive(
[
[ 'A' .. 'F' ],
[ 2, 3, 5, 7 ],
[ qw< foo bar baz > ],
],
sub { print join('-', @_), "\n" },
);
return 0;
}->(@ARGV) unless caller;
sub nested_loops_recursive {
my ($dims, $opts, $cb, $accumulator) = @_;
($opts, $cb) = ($cb, $opts) if ref($opts) eq 'CODE';
$accumulator = [] unless defined $accumulator;
my $level = @{$accumulator};
if ($level == @{$dims}) { # fire callback!
$cb->(@{$accumulator});
return;
}
for my $item (@{$dims->[$level]}) {
push @{$accumulator}, $item;
nested_loops_recursive($dims, $opts, $cb, $accumulator);
pop @{$accumulator};
}
return;
}
1;It’s coded recursively, which in my opinion simplifies the implementation and figuring out what’s going on. Basically:
- lines 8 to 18 implment the modulino trick
- line 25 tests whether there are still new levels to iterate to, if not then the callback is called in line 26 and the call returns;
- oterhwise, lines 29 to 33 implement one of the nested loops for the
specifi level, then recurse (line 31). The recursive call has
$accumulatorwith all elements currently generated at the available levels.
The implementation is simplified in the sense that:
- hash reference
$optsis supported in the interface but ignored - the iteration only accounts for arrays of items and does not support code references
- there is no support for returning an iterator.