% $Id: generators.tex,v 1.1.1.8 2005/01/26 13:42:24 nthiery Exp $
\begin{Mhelppage}{generators}{F.~Hivert and N.~Thiéry}
  [ImplState=stable,TestState=stable,DocState=stable]
\Mproofread{hivert}{10/2003}{proofread}

\begin{MInfo}
  \eng{generators}
\end{MInfo}

\begin{MIntro}
  \eng{The library \Mthis{} provides functions for producing and
    manipulating generators.}
\end{MIntro}

\MKeywords{combinatorics,generator}

\begin{MDetails}
  \eng{A \emph{generator} is a device that allows for iterating over a
    large or even infinite quantity of objects, without having to
    produce and store all of them at once. This is typically very
    handy in combinatorics.}
  
  \eng{ In principle a generator is any \mupad\ object \Mex{g} such
    that the function call \Mex{g()} is defined. Each call \Mex{g()}
    returns either the next object, or FAIL if no more objects are
    available. The effect of calling \Mex{g()} after the FAIL value
    has been returned is undefined (i.e. possibly disastrous).}
\end{MDetails}

\begin{MDomEntries}
  \MDomEntry{empty}
  \eng{The empty generator, iterating over the empty set}
\end{MDomEntries}

\begin{MMethodDetails}{count}
  \infoEng{number of elements generated by a generator}
  \call{\Mtype{generator} g}
  \eng{Returns the number of elements generated by \Mpar{g}.}
\end{MMethodDetails}

\begin{MMethodDetails}{accumulate}
  \infoEng{accumulate the elements generated by a generator}
  \call{\Mtype{generator} g}
  \eng{Returns the sum of the elements generated by \par{g}.}
  \call{\Mtype{generator} g\Mopt{, start, \Mtype{function} accumulator}}%
  
  \eng{Starts from \Mex{r:=start}, and accumulate each element \Mex{e}
    generated by \Mpar{g} with \Mex{r := accumulator(r,e)}. Finally,
    returns \Mex{r}.}
\end{MMethodDetails}

\begin{MMethodDetails}{toList}
  \infoEng{list of the elements generated by a generator}
  \call{\Mtype{generator} g}
  \eng{Returns the list of the elements generated by \Mpar{g}.}
  \eng{See also \Mup{combinat::generators::fromList}.}
\end{MMethodDetails}

\begin{MMethodDetails}{repeater}
  \infoEng{generator repeating a value}
  \call{value}
  \eng{Returns a generator repeating \Mpar{value} forever.}
  \call{value, \Mtype{nonnegative integer} n}
  \eng{Returns a generator repeating \Mpar{value} \Mpar{n} times.}
\end{MMethodDetails}

\begin{MMethodDetails}{fromRange}
  \infoEng{generator from range}%
  \call{\Mtype{range} i..j}%
  \eng{Returns a generator iterating over the elements in the range
    \Mex{i..j}.}
\end{MMethodDetails}

\begin{MMethodDetails}{fromList}
  \infoEng{generator from list}
  \call{\Mtype{list} l}
  \eng{Returns a generator iterating over the elements of the list
  \Mpar{l}.}
  \eng{See also \Mup{combinat::generators::toList}.}
\end{MMethodDetails}

\begin{MMethodDetails}{fromNext}
  \infoEng{generator from first value and next operation}
  \call{first, \Mtype{function} next}%
  \eng{Returns a generator iterating over the sequence \Mex{first,
      next(first)},\\ \Mseq{next(next(first))} The function \Mex{next} must
      return \Mex{FAIL} if there is no next object.}
\end{MMethodDetails}

\begin{MMethodDetails}{fromUnrank}
  \infoEng{generator from unrank function}
  \call{\Mtype{unrank fonction} f, \Mopt{options}}%
  \eng{\begin{sloppypar}
      Returns a generator iterating over the sequence\ \Mex{f(1, options),
      f(2, options)}, \Mseq{f(3, options)} If \Mex{f(r, options)} is not
      defined for large \Mex{r} the function \Mex{f} must return \Mex{FAIL}
      for such \Mex{r}.
      \end{sloppypar}}
\end{MMethodDetails}

\begin{MMethodDetails}{map}
  \infoEng{application of a function on a generator}
  \call{\Mtype{generator} g, \Mtype{function} f}%
  \eng{Returns a generator iterating over the images by \Mpar{f} of
    the elements generated by \Mpar{g}.}
\end{MMethodDetails}

\begin{MMethodDetails}{compose}
  \infoEng{composition of a generator and a function}
  \call{\Mtype{function} f, \Mtype{generator} g}%
  \eng{Returns a generator iterating over the images by \Mpar{f} of
    the elements generated by \Mpar{g} (deprecated; please use the
    equivalent function \Mup{combinat::generators::map}).}
\end{MMethodDetails}

\begin{MMethodDetails}{select}
  \infoEng{generator filter}
  \call{\Mtype{generator} g, \Mtype{predicate} f, \Mopt{options}}%
  \eng{Returns a generator iterating over the elements \Mex{e}
    generated by \Mpar{g} which satisfy the criterion
    \Mex{f(e, options)}.}
\end{MMethodDetails}

\begin{MMethodDetails}{concat}
  \infoEng{concatenation of generators}
  \call{\Mopt{\Mtype{generator} g1} \Mopt{, \Mtype{generator} g2}
    \Mopt{, ..., \Mtype{generator} gk}}%
  \eng{Returns a generator iterating over the elements generated
    successively by the generators \Mex{g1, g2, ..., gk}.}
\end{MMethodDetails}

\begin{MMethodDetails}{cartesian}
  \infoEng{cartesian product of generators}
  \call{\Mopt{\Mtype{generator} g1} \Mopt{, \Mtype{generator} g2}
    \Mopt{, ..., \Mtype{generator} gk}}%
  \eng{Returns a generator iterating over the lists
    \Mpar{[e1,e2,...,ek]} where \Mex{e1,e2,...,ek} are elements
    generated respectively by \Mex{g1,g2,...,gk}.}
\end{MMethodDetails}

\begin{MMethodDetails}{cartesianPower}
  \infoEng{cartesian power product of a generator}
  \call{\Mtype{generator} g, \Mtype{non negative integer} k}%
  \eng{Returns a generator iterating over the lists
    \Mpar{[e1,e2,...,ek]} of $k$ elements generated by \Mex{g}.}
\end{MMethodDetails}

\begin{MMethodDetails}{multiset}
  \infoEng{multiset of a generator}
  \call{\Mtype{generator} g, \Mtype{non negative integer} k}%
  \eng{Returns a generator iterating over the multisets
    \Mpar{\{\{e1,e2,...,ek\}\}} of elements generated by \Mex{g}.}
\end{MMethodDetails}

\begin{MMethodDetails}{powerset}
  \infoEng{powerset of a generator}
  \call{\Mtype{generator} g, \Mtype{non negative integer} k}%
  \eng{Returns a generator iterating over the sets
    \Mpar{\{e1,e2,...,ek\}} of elements generated by \Mex{g}.}
\end{MMethodDetails}

\begin{MMethodDetails}{pipe}
  \infoEng{composition of a generators and a generator constructor}
  \call{\Mtype{generator} g, \Mtype{generator constructor} construct
    \Mopt{, options}}%
  \eng{Returns the concatenation of the generators constructed by
    successive calls of \Mex{construct(g(), options)}.}
\end{MMethodDetails}

\begin{MMethodDetails}{copy}
  \infoEng{copy of a generator}
  \call{\Mtype{generator} g}%
  \eng{Returns a copy of the generator \Mex{g}. The copy is a generator which
    gives the same result as \Mex{g}, but is independent (no reference
    effect). Calling \Mex{g} does not affect the copy and conversely.}
\end{MMethodDetails}


\begin{MExample}{ex-constructors}
  \eng{We demonstrate how to construct simple generators. The empty
    generator iterates over the empty set, and thus returns \Mup{FAIL}
    immediately:}
  \begin{Mexin}
g := combinat::generators::empty:
g()
  \end{Mexin}
  \begin{Mexout}
                             FAIL
  \end{Mexout}

  \eng{The following generator repeats \Mex{a} forever:}
  \begin{Mexin}
g := combinat::generators::repeater(a):
g(), g(), g(), g(), g()
  \end{Mexin}
  \begin{Mexout}
                         a, a, a, a, a
  \end{Mexout}
  
  \eng{This one repeats \Mex{a} three times:}
  \begin{Mexin}
g := combinat::generators::repeater(a, 3):
g(), g(), g(), g()
  \end{Mexin}
  \begin{Mexout}
                         a, a, a, FAIL
  \end{Mexout}
  
  \eng{We build a generator which iterates over the elements of the
    list \Mex{[a,b,c]}:}
  \begin{Mexin}
g := combinat::generators::fromList([a,b,c]):
g(), g(), g(), g()
  \end{Mexin}
  \begin{Mexout}
                         a, b, c, FAIL
  \end{Mexout}
  
  \eng{Here is a generator iterating over the range \Mex{-1..2}:}
  \begin{Mexin}
g := combinat::generators::fromRange(-1..2):
g(), g(), g(), g(), g()
  \end{Mexin}
  \begin{Mexout}
                       -1, 0, 1, 2, FAIL
  \end{Mexout}
  
  \eng{We build a generator using the natural recursive definition of
    nonnegative integers:}
  \begin{Mexin}
g := combinat::generators::fromNext(0, n->n+1):
g(), g(), g(), g(), g(), g()
  \end{Mexin}
  \begin{Mexout}
                       0, 1, 2, 3, 4, 5
  \end{Mexout}

  \eng{Another way to do that is to use an unranking function:}
  \begin{Mexin}
g := combinat::generators::fromUnrank((n)->n-1):
g(), g(), g(), g(), g(), g()
  \end{Mexin}
  \begin{Mexout}
                       0, 1, 2, 3, 4, 5
  \end{Mexout}
  \eng{Here is a way to define a generator for lists of length $n$ with $n-1$
  zeros and only one $1$.}
  \begin{Mexin}
n := 5:
g := combinat::generators::fromUnrank(
     (x, len) -> if x <= len then [0$(x-1), 1, 0$(len-x)] 
		 	     else FAIL end_if, n):
g(), g(), g(), g(), g(), g()
  \end{Mexin}
  \begin{Mexout}
[1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0],

   [0, 0, 0, 1, 0], [0, 0, 0, 0, 1], FAIL
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex-modifiers}
  \eng{\begin{sloppypar}
    Generators can be modified in different ways. With
    \Mup{combinat::generators::map} one can apply a function on
    the elements generated. Here is a generator for the squares of
    nonnegative integers:
       \end{sloppypar}}
  \begin{Mexin}
g := combinat::generators::map(
        combinat::generators::fromNext(0, n->n+1),
        n->n^2
        ):
g(), g(), g(), g(), g(), g()
  \end{Mexin}
  \begin{Mexout}
                      0, 1, 4, 9, 16, 25
  \end{Mexout}
  
  \eng{\Mup{combinat::generators::select} is handy to pick out the
    elements generated which satisfy a criterion. Here is a
    brute-force generator for prime numbers:}
  \begin{Mexin}
g := combinat::generators::select(
        combinat::generators::fromNext(0, n->n+1),
        isprime):
g(), g(), g(), g(), g(), g()
  \end{Mexin}
  \begin{Mexout}
                      2, 3, 5, 7, 11, 13
  \end{Mexout}
  
  \eng{\Mwarn{Beware of infinite loops when selecting elements out of
      an infinite generator. Here is a brain-dead generator for the
      positive integers less or equal to $5$:}}
  \begin{Mexin}
g := combinat::generators::select(
        combinat::generators::fromNext(1, n->n+1),
        _leequal, 5):
g(), g(), g(), g(), g()
  \end{Mexin}
  \begin{Mexout}
                         1, 2, 3, 4, 5
  \end{Mexout}
  \eng{Calling \Mex{g()} once more would not terminate!}
\end{MExample}

\begin{MExample}{ex-operators}
  \eng{Generators can be combined together. This is a generator for
    the union of the ranges \Mex{1..3} and \Mex{7..8}:}
  \begin{Mexin}
g := combinat::generators::concat(
        combinat::generators::fromRange(1..3),
        combinat::generators::fromRange(7..8)):
g(), g(), g(), g(), g(), g()
  \end{Mexin}
  \begin{Mexout}
                      1, 2, 3, 7, 8, FAIL
  \end{Mexout}
  
  \eng{This is a generator for the cartesian product of the ranges
    \Mex{1..3} and \Mex{7..8}:}
  \begin{Mexin}
g := combinat::generators::cartesian(
        combinat::generators::fromRange(1..3),
        combinat::generators::fromRange(7..8)):
g(), g(), g(), g(), g(), g(), g()
  \end{Mexin}
  \begin{Mexout}
     [1, 7], [1, 8], [2, 7], [2, 8], [3, 7], [3, 8], FAIL
  \end{Mexout}
  
  \eng{\Mup{combinat::generators::pipe} allows for concatenating a
    series of similar generators which are constructed on the fly from
    the successive result of another generator. Here is a generator
    for the sequence \Mex{1,2,2,3,3,3,...}:}
  \begin{Mexin}
g := combinat::generators::pipe(
        combinat::generators::fromNext(0, n->n+1),
        n->combinat::generators::repeater(n,n)):
g(), g(), g(), g(), g(), g(), g(), g(), g(), g(), g()
  \end{Mexin}
  \begin{Mexout}
                1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5
  \end{Mexout}
  
  \eng{Typically, this can be used for building a generator for all
    integer partitions, size by size:}
  \begin{Mexin}
g := combinat::generators::pipe(
        combinat::generators::fromNext(0, n->n+1),
        combinat::partitions::generator):
g(), g(), g(), g(), g(), g(), g(), g(), g(), g(), g(), g(), g(), g()
  \end{Mexin}
  \begin{Mexout}
[], [1], [2], [1, 1], [3], [2, 1], [1, 1, 1], [4], [3, 1],

   [2, 2], [2, 1, 1], [1, 1, 1, 1], [5], [4, 1]
  \end{Mexout}
\end{MExample}  

\begin{MExample}{ex-advanced}
  \eng{We demonstrate how to construct your own generators.  To define a
    non-constant generator \Mex{g}, we need to modify the internal state of
    the object \Mex{g}. Due to the default copy-semantic of \mupad\ (no
    reference effect, see \Mup{copyClosure}), this is impractical with most
    objects. The only exceptions to this rule are closures, domains (not
    domain elements!), and objects defined in dynamic modules.}
  % Give a nice example!!!!
  
  \eng{The easiest way to define a generator in \mupad\ is to use
    closures. Here is a generator for the sequence
    \Mex{1^3,2^3,3^3,4^3}:}
  \begin{Mexin}
power_generator :=
proc(k)
    local i;
    option escape;
begin
    i := 0;
    proc() begin i := i+1; i^k; end_proc
end_proc:

g := power_generator(3):
g(), g(), g(), g(), g()
  \end{Mexin}
  \begin{Mexout}
                       1, 8, 27, 64, 125
  \end{Mexout}
  \eng{What happens here is that the variable \Mex{i} in the procedure
    \Mex{g} returned by \Mex{power_generator} is lexically bound to
    the context of \Mex{power_generator} (note the option
    \Mup{escape}). Hence, its value is persistent across successive
    calls of \Mex{g}.}
\end{MExample}  

\begin{MExample}{ex-reference}
  \eng{Generators, as all closures, display a reference effect:}
  \begin{Mexin}
g := combinat::generators::fromNext(1, n->n+1):
g(), g();
h := g:
g(), g();
h(), h();
g(), g()
  \end{Mexin}
  \begin{Mexout}
                             1, 2

                             3, 4

                             5, 6

                             7, 8
  \end{Mexout}
  
  \eng{This effect also appears when passing a generator as argument
    to a function:}
  \begin{Mexin}
g := combinat::generators::fromNext(1, n->n+1):
consume := proc(g) begin g(); end_proc:
g(), g();
consume(g), consume(g);
g(), g()
  \end{Mexin}
  \begin{Mexout}
                             1, 2

                             3, 4

                             5, 6
  \end{Mexout}
  
  \eng{This reference effect can be broken by making a full copy of
    the generator with the method \Mup{combinat::generators::copy}:}

  \begin{Mexin}
g := combinat::generators::fromNext(1, n->n+1):
g(), g();
h := combinat::generators::copy(g):
g(), g();
h(), h();
g(), g()
  \end{Mexin}
  \begin{Mexout}
                             1, 2

                             3, 4

                             3, 4

                             5, 6
  \end{Mexout}
  \eng{Note that this works not for all generators (see background):}
  \begin{Mexin}
g := combinat::generators::fromNext(1, n->n+1):
h := proc() begin  g(); g(); end_proc:
h(), h();
h2 := combinat::generators::copy(h):
h(), h();
h2(), h2();
h(), h()
  \end{Mexin}
  \begin{Mexout}
                             2, 4

                             6, 8

                            10, 12

                            14, 16
  \end{Mexout}
\end{MExample}


\begin{MBackground}
  \eng{In practice, most generators are closures, of type \Mex{DOM_PROC}.}
  
  \eng{\Mwarn{Most of the generators built with \mupad-combinat{} can
      be copied via \Mslot{copy}, including generators with embedded
      generators such as those constructed with
      \Mup{combinat::generators::cartesian}, \Mslot{select},
      \Mslot{compose}, \Mslot{concat}, \Mslot{cartesian}, \Mslot{map},
      and \Mslot{pipe}. Simple closures without embedded generator are
      readily copyable. There exists an undocumented tool to construct
      more complicated copyable generators; however the interface is
      still in design.}}
\end{MBackground}

\begin{MChanges}
  \version{2.5}%
  \eng[New library]{\Mthis{} is a new library}
\end{MChanges}

\end{Mhelppage}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: main
%%% End: 
