Laziness in a more consistent way

[tilly]

Here is a more general solution to the problem. In this solution my iterators all indicate that they are done by returning an empty list, and when called next will restart. I didn't use i_grep, but I included it to show how you would do it.

Note that despite the length, the code is more straightforward than the original recursive code. And if this was part of a longer program, you would be reusing the bulk of this code.

use strict;

my $iter = i_map(
  sub {print "@_\n"},
  comb_iter(
    list_iter(1..2), list_iter('a'..'c'), list_iter(3..5)
  )
);

1 while $iter->();

###################################################################
# The program proper ends here.  These are utility functions that #
# you could reuse                                                 #
###################################################################

# Takes a list of iterators that are "restartable"
# Returns a restartable iterator that iterates over all combinations
# of outputs of the input iterators, creating a flat list of combinati
+ons
# of the inputs.  (The output only makes sense in array context.)
sub comb_iter {
  if (0 == @_) {
    return sub {()}; # Stupid case needed for generality.
  }
  elsif (1 == @_) {
    return shift;
  }
  else {
    my $outer_iter = shift;
    my $inner_iter = comb_iter(@_);
    my @last_outer;
    return sub {
      if (@last_outer) {
        my @ret = $inner_iter->();
        if (@ret) {
          return (@last_outer, @ret);
        }
        else {
          @last_outer = $outer_iter->();
          if (@last_outer) {
            return (@last_outer, $inner_iter->());
          }
          else {
            return ();
          }
        }
      }
      else {
        @last_outer = $outer_iter->();
        return (@last_outer, $inner_iter->());
      }
    };
  }
}


# Takes a function and an iterator, returns an iterator that uses that
# function to filter the output.
sub i_grep {
  my ($filter, $iter) = @_;
  my @last_ret = qw(just an initialization value);
  sub {
    while (@last_ret) {
      @last_ret = $iter->();
      if ($filter->(@last_ret)) {
        return wantarray ? @last_ret : $last_ret[0];
      }
    }
    return ();
  };
}


# Takes a function and an iterator, returns an iterator that applies t
+hat
# function to the returns of the iterator.
sub i_map {
  my ($filter, $iter) = @_;
  sub {
    my @ret = $iter->();
    return @ret ? $filter->(@ret) : ();
  };
}

# Takes a list and turns it into an iterator over that list
sub list_iter {
  my @vals = @_;
  my $i = 0;
  sub {
    if ($i < @vals) {
      return $vals[$i++];
    }
    else {
      $i = 0;
      return ();
    }
  };
}

Note that the specific problem in the original question can now be solved as the author wanted using i_grep, or you can produce more efficient iterator as follows:

my $genome_iter = i_map(
  sub {join '', @_},
  join_iter(
    map {
      comb_iter(
        map {
          list_iter(qw(a c g n t));
        } 1..$_
      )
    } 2..3
  )
);

while (my $string = $genome_iter->()) {
  print "$string\n";
}



# Takes a list of iterators, and returns an iterator that iterates
# over each in turn
sub join_iter {
  my @iter = @_;
  my $i = 0;
  return sub {
    while ($i < @iter) {
      my @ret = $iter[$i]->();
      if (@ret) {
        return wantarray ? @ret : $ret[0];
      }
      else {
        $i++;
      }
    }
    $i = 0;
    return ();
  };
}

Alternately if you want to turn the output into a list you can just create an easy method:

# Takes an iterator and returns a list of results
sub iter2list {
  my $iter = shift;
  my @out;
  while (my @ret = $iter->()) {
    push @out, @ret;
  }
  return @out;
}

Note that most of the length here is because I am having to build my iterator interface from scratch. That is a lot of work! And some of the code looks more complex because what we are used to seeing in a few nested loops our minds balk at when you see it as a similar number of nested calls.