list<int> li = enum_from( 1 ); // li is infinite list [1, 2, 3, ...]
   li = map( add_self, li );      // li is infinite list [2, 4, 6, ...]

The main interface to the list class is provided by just a few functoids:

   list<int> li;       // empty list (default constructor)
   li = cons(2,li);    // cons adds an element to the front of a list
   li = cons(1,li);    // li is now the list [1,2]
   int x = head(li);   // x is 1, the front element
   li = tail(li);      // li is the list [2] (tail==everything except the head)
   bool b = null(li);  // b is false; null() tests for the empty list
   li = cat(li,li);    // li is now [2,2]; cat() concatenates two lists
   li = NIL;           // li is now empty; NIL is the empty list constant

This is the typical interface offered for singly-linked lists common to many functional languages.

In order to enable lazy evaluation, the list class has a special constructor which takes a thunk which returns a list. The second argument to cons() or cat() can also be a thunk-returning-a-list, rather than a list. For example, after

   list<int> li = thunk2(cons,2,NIL);
   list<int> li = thunk2(cons,1,li);

li is the list [1,2], except that none of the conses has been evaluated yet. This is not particularly interesting in itself, but now we can see how to write functions like enum_from(), which return infinite lists.

First, here is how we would write an eager (non-lazy) version of enum_from(), which goes into an infinite recursion when called. (For simplicity, we define it as a monomorphic functoid that works only on integers.)

   struct my_enum_from_type : public c_fun_type<int,list<int> > {
      list<int> operator()( int x ) const {
         return cons( x, my_enum_from_type()(x+1) );
      }
   } my_enum_from;

Now, all we have to do to make this function lazy is to "thunk" the recursive call like so:

   struct my_enum_from_type : public c_fun_type<int,list<int> > {
      list<int> operator()( int x ) const {
         return cons( x, thunk1( my_enum_from_type(), x+1 ) );
      }
   } my_enum_from;

This delays the recursive call so that it is stored in the "tail" portion of the cons, where it won't be evaluated until demanded. Here is an example that demonstrates the function being used:

   list<int> li = my_enum_from(1);
   for( int i=0; i<10; ++i ) {
      std::cout << head(li) << std::endl;
      li = tail(li);
   }

This prints out the first 10 positive integers. We could print out as many as we like, as the list li is effectively infinite; none of the cons cells representing the list are created until they are demanded.

The discussion here provides a simple overview of lazy evaluation as implemented in the FC++ list class. We have elided a number of interesting details which can impact the performance of lists, most notably, the existence of the odd_list class and the caching ability of lists. To learn more about these details, the reader is referred to

Lists provide perhaps the most common and convenient way to utilize lazy evaluation; representing a (possibly infinite) stream of data which is computed "on demand" is an oft-used pattern. Nevertheless, any computation can be lazified. The by_need monad (see Section 13 for info about monads) illustrates a more general mechanism for lazifying any computation.