c++boost.gif (8819 bytes)HomeLibrariesPeopleFAQMore

9. Lists and lazy evaluation

Table of Contents

9.1. Interface to list
9.2. Writing lazy list functoids
9.3. Other details about lazy evaluation

In Section 4, we showed examples of using FC++'s lazy list data structure:

   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, ...]
In this section, we discuss the interface to the list class, and show how to implement lazy list functions. We also discuss the general topic of lazy evaluation.

9.1. Interface to list

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.

9.2. Writing lazy list functoids

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.

9.3. Other details about lazy evaluation

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

  • Section 10 of [McN&Sma to appear], which describes caching in lists, as well as some other performance optimizations,
  • Section 11 of [McN&Sma to appear], which describes lists versus odd_lists and the efficient list interface, and
  • the FC++ web page [FC++], which has summary documentation on the topic.

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.

Last revised: October 03, 2003 at 23:27:22 GMTCopyright © 2000-2003 Brian McNamara and Yannis Smaragdakis