[GAP Forum] Iteration Over Lists of Lists

[Frank Lübeck]

Dear Robert, dear Forum,

Burkhard already pointed out that the "fast" loop in Robert's example
did some unnecessary checks that made it slower than necessary. 

The timing comparison with a loop over IteratorOfCartesianProduct(lol) is
not quite fair, because running over this iterator really produces each 
element of the Cartesian product as a new GAP object.
(that is List([1..n], i-> lol[i][base[i]]) in the notation of Robert's loop).

So, if you are not really interested in these tuples as separate objects 
but just want to look at them in your loop, then using the iterator produces
a lot of unnecessary garbage for GAP's memory manager.

Robert's question reminded me that I have written a small utility
function 'IteratedFor' which does an iterated for-loop. A function fun(tup)
is applied to all elements tup of the Cartesian product of a list of lists
(or other objects over which GAP can iterate).
Note that here entries of tup are accessed by 'tup[i]' which is more
efficent than 'lol[i][base[i]]'.

I append this utility below together with some usage examples. (Maybe this
should go into the GAP library?)

With best regards, 
  Frank

###########################################################################
##  
#F  IteratedFor( lol, fun ) . . . . . . . . . . . . . iterated 'for'-loop
##  
##  lol:  a list of lists
##  fun( tup ):  a function to be called for all tup running through the 
##               Cartesian product of the lists in lol in alphabetical order
##  
##  fun must return a value, when it returns 'false' the iterated loops
##  are stopped (so, this is like a 'break' for all nested loops).
##  
##  The argument tup is the same GAP object in all calls of fun, the entries
##  of tup are changed during the loop. This means that you should never change 
##  tup within fun. And if you want to store tup somewhere then make a 
##  ShallowCopy of it.
##  
IteratedForInternal := function(lol, fun, tup, i, lenlol)
  local loli, x, n;
  for x in lol[i] do
    tup[i] := x;
    if i = lenlol then
      if fun(tup) = false then
        return false;
      fi;
    else
      if IteratedForInternal(lol, fun, tup, i+1, lenlol) = false then
        return false;
      fi;
    fi;
  od;
  return true;
end;
IteratedFor := function(lol, fun)
  local tup, n;
  tup := EmptyPlist(Length(lol));
  IteratedForInternal(lol, fun, tup, 1, Length(lol));
end;

###############     EXAMPLES    ##########################################

IteratedFor([[1..2],[1..3],[1..4]], 
  function(tup) 
    Print(tup,"\n"); 
    return true;
  end);

# Robert's benchmark example
n := 6;
k := 9;
lol := List([1..n], i-> [1..k]);
a := 0;
IteratedFor(lol, 
  function(tup) 
    ##  do this if you want to change or store tup:
    #tup := ShallowCopy(tup);
    a := a+1; 
    return true; 
  end); time;

# and here with a 'break'
IteratedFor(lol, 
  function(tup) 
    a := a+1; 
    if tup[3] = 7 then 
      Print(tup); 
      return false; 
    else 
      return true; 
    fi; 
  end);

-- 
///  Dr. Frank Lübeck, Lehrstuhl D für Mathematik, Templergraben 64,
\\\                    52062 Aachen, Germany
///  E-mail: Frank.Luebeck at Math.RWTH-Aachen.De
\\\  WWW:    http://www.math.rwth-aachen.de/~Frank.Luebeck/