performance tuning - Lazy form of Tuples/Outer to loop over list of lists

This is less a question and more asking if someone has implemented this already, with more skill.

I need to perform the Outer-like generalized outer product of a list of lists (also a form of Tuples). I need to do it in a lazy way because the lists will become very large (many tens of thousands of elements).

I am using a Module to hold state as iterate over the products

loopOver[list0_]:=Module[
  {len0,index,get,increment,isDoneQ,doneB},
  len0=Length[list0];
  Do[index[j]=1,{j,len0}];
  doneB=False;
  get[]:=Table[list0[[j,index[j]]],{j,len0}];
  increment[]:=Block[

    {stack,p},
    If[doneB,Return[]];
    stack={len0};
    While[Length[stack]>0,
     p=First@stack;
     stack=Rest@stack;
     index[p]=index[p]+1;
     If[index[p]>Length[list0[[p]]],
      (
       If[p===1,doneB=True;Return[]];

       index[p]=1;stack=Append[stack,p-1]
       )
      ]
     ]
    ];
  isDoneQ[]:=doneB;
  {
   "get"->get,
   "increment"->increment,
   "isDoneQ"->isDoneQ

   }
  ]

And you use it as such:

Block[
 {a, get, increment, isDoneQ},
 a = {
   {"11", "12", "13"},
   {"21", "22"},
   {"31"},

   {"41", "42"}
   };
 {get,increment,isDoneQ}=loopOver[a][[All,2]];
 While[!isDoneQ[],
  Print[get[]];
  increment[]
  ]
 ]

outputting the expected outer of 3*2*1*2=12 products:

{11,21,31,41}
{11,21,31,42}
{11,22,31,41}
{11,22,31,42}
{12,21,31,41}
{12,21,31,42}
{12,22,31,41}
{12,22,31,42}
{13,21,31,41}
{13,21,31,42}

{13,22,31,41}
{13,22,31,42}

Code review would be appreciated too. I hope my code is high on self documentation where it is low on performance and use of MMA functional coding style.

Answer

The implementation of lazy tuples here pretty much contains the solution to the lazy Outer problem. I will take the relevant parts from that code.

The following code constructs a function take, which would, given the start and end positions in the flat list of the resulting combinations, extract the elements:

ClearAll[next];
next[{left_, _}, dim_] := 
  {left - dim*(# - 1), #} &[IntegerPart[(left - 1)/dim] + 1];


ClearAll[multiDims];
multiDims[dims_] := Rest @ Reverse @ FoldList[Times, 1, Reverse @ dims];

ClearAll[multiIndex];
multiIndex[pos_, dims : {__Integer}] :=
   Rest@FoldList[next, {pos, 0}, multiDims@dims][[All, 2]]

ClearAll[take];
take[lists : {__List}, {start_, end_}] :=

  With[{rend = Min[end, Times @@ Map[Length, lists]]},
    Transpose @ MapThread[
        Part, 
        {lists, multiIndex[Range[start, rend], Length /@ lists]}
    ]
  ];

For example,

take[{{1, 2, 3}, {4, 5, 6}}, {3, 7}] == Tuples[{{1, 2, 3}, {4, 5, 6}}][[3 ;; 7]]


(* True *)

The difference is of course, that take only computes those elements that have been requested, so can be used as a basis for a lazy implementation.

Here is then an implementation of an iterator, that would return consecutive combinations in chunks of specified length:

ClearAll[makeTupleIterator];
makeTupleIterator[lists:{__List}, chunkSize_Integer?Positive]:=
  With[{len=Times @@ Length /@ lists},
    Module[{ctr = 0},          
      If[ctr >= len,
        {},

        (* else *)
        With[{taken = take[lists,{ctr+1, Min[ctr+chunkSize,len]}]},
          ctr += Length[taken];
          taken
        ]
      ]&
    ]
  ];

Here is an example: we construct an iterator with the chunk size of 10 elements:

iter = makeTupleIterator[{{"11", "12", "13"}, {"21", "22"}, {"31"}, {"41", "42"}}, 10];

Now we use it:

iter[]

(*
{        
    {"11","21","31","41"},
    {"11","21","31","42"},
    {"11","22","31","41"},

    {"11","22","31","42"},
    {"12","21","31","41"},
    {"12","21","31","42"},
    {"12","22","31","41"},
    {"12","22","31","42"},
    {"13","21","31","41"},
    {"13","21","31","42"}
}
*)


iter[]

(* {{"13", "22", "31", "41"}, {"13", "22", "31", "42"}} *)

iter[]

(* {} *)

When we get an empty list, this tells us that the iterator has been exhausted.

This basically implements lazy tuples, and therefore also lazy Outer, more or less. You gain efficiency by picking large enough chunks, since chunk extraction (take function) is pretty fast, compared to the top-level iteration that would be needed to extract element by element.