SICP streams in C++

To brush up on my C++ chops, I've implemented a toy version of "SICP Streams", which behave like lists with one twist: the first element of the list is always available, the rest of the list is stored as a "promise" to produce the rest of the list. Calling rest() forces its evaluation.

Following is my implementation of the general "EStream" along with a handful of specialized subclasses. But there are (at least) two areas that need attention:

• Both head() and rest() return immutable values. I have yet to get my head around the use of const to notify the compiler that this is the case. Guidance on the use of const (or references to good documentation) would be appreciated.

• As written, the behavior of a stream is split between the create() method and the rest() method. I'd like to find a way to restructure things all the logic for the each stream is embodied entirely either in the constructor or the rest() method, if that's possible.

(As an aside, I've created another version of EStream that uses lambdas to defer evaluation of the rest() -- it works fine, but it would be nice to not depend on c++11 constructs. Maybe that's a false concern.)

#include <string>


#define NULL_ESTREAM(T) ((EStream<T> *)0)

// (Abstract) Base Class
template <typename T> class EStream {
public:
  virtual T first() = 0;
  virtual EStream<T> *rest() = 0;
};

// ================================================================
// alphabetical below here

// ================
// Return elements of s0 followed by elements of s1
template <typename T> class AppendES : public EStream <T> {
public:

  static EStream<T> *create( EStream <T> *s0, EStream <T> *s1 ) {
    return (s0 == NULL_ESTREAM(T)) ? s1 : new AppendES<T>(s0, s1);
  }

  T first() {
    return s0_->first(); 
  }

  EStream<T> *rest() { 
    return AppendES::create(s0_->rest(), s1_);
  }

protected:
  AppendES( EStream<T> *s0, EStream<T> *s1) : s0_(s0), s1_(s1) {}
  EStream<T> *s0_;
  EStream<T> *s1_;
};

// ================
// Generate a stream of constant values
template <typename T> class ConstantES : public EStream <T> {
public:
  static ConstantES<T> *create(T value) { return new ConstantES<T>(value); }
  T first() { return value_; }
  ConstantES<T> *rest() { return this; }
protected:
  ConstantES(T value): value_ (value) {};
  T value_;
};

// ================
// Restart stream s when it is exhausted
template <typename T> class CycleES : public EStream <T> {
public:

  static EStream<T> *create( EStream <T> *s ) {
    return (s == NULL_ESTREAM(T)) ? s : new CycleES(s, s);
  }

  T first() {
    return s_->first(); 
  }

  EStream<T> *rest() { 
    EStream<T> *t = s_->rest();
    if (t == NULL_ESTREAM(T)) {
      return new CycleES(s_head_, s_head_);
    } else {
      return new CycleES(t, s_head_);
    }
  }

protected:
  CycleES( EStream<T> *s, EStream<T> *s_head) : s_(s), s_head_(s_head) {}
  EStream<T> *s_;
  EStream<T> *s_head_;
};

// ================
// Drop the first n elements of a stream
template <typename T> class DropES : public EStream <T> {
public:

  static EStream<T> *create( EStream <T> *s, int n) {
    while ((n > 0) && (s != NULL_ESTREAM(T))) {
      n -= 1;
      s = s->rest();
    }
    return s;
  }

  // these should never get called.
  T first() { return (T)0; }
  EStream<T> *rest() { return NULL_ESTREAM(T); }

protected:
  DropES() {}
};

// ================
// Generate a stream of integers, counting up from a starting value
class IntegerES : public EStream<int> {
public:
  static IntegerES *create(int initial) { return new IntegerES(initial); }
  int first() { return value_; }
  IntegerES *rest() { return IntegerES::create(value_ + 1); }
protected:
  IntegerES(int initial): value_ (initial) {}
  int value_;
};

// ================
// Return elements of s0, then s1, then s0.  If either stream is
// empty, emit the other stream.
template <typename T> class InterleaveES : public EStream <T> {
public:

  static EStream<T> *create( EStream <T> *s0, EStream <T> *s1 ) {
    return (s0 == NULL_ESTREAM(T)) ? s1 : new InterleaveES<T>(s0, s1);
  }

  T first() {
    return s0_->first(); 
  }

  EStream<T> *rest() { 
    return InterleaveES::create(s1_, s0_->rest());
  }

protected:
  InterleaveES( EStream<T> *s0, EStream<T> *s1) : s0_(s0), s1_(s1) {}
  EStream<T> *s0_;
  EStream<T> *s1_;
};

// ================
// Return the first n elements of a stream
template <typename T> class TakeES : public EStream <T> {
public:
  static EStream<T> *create(EStream<T> *s, int n) {
    return ((n <= 0) || (s == NULL_ESTREAM(T))) ? NULL_ESTREAM(T) : new TakeES<T>(s, n);
  }
  T first() { 
      return s_->first();
  }
  EStream<T> *rest() {
    return TakeES::create(s_->rest(), n_ - 1);
  }
protected:
  TakeES(EStream<T> *s, int n): s_ (s), n_ (n) {}

  EStream<T> *s_;
  int n_;
};