Lazy list implementation in C++

lazylist.cpp

// Lazy List in C++
// Usage: 
//    make a thunk:    LazyList<T>(new Thunk<T>( function, *args )) 
//    make empty list: LazyList<T>(new Nil<T>())
//    make cons:       LazyList<T>(new Cons<T>( car, *cdr ))

//    list empty:      list.Empty()
//    list's head:     list.Head()
//    zipWith:         LazyList<T>::ZipWith(function, a, b)
//    take:            list.Take(n)
//    print:           list.Print()

//    you don't need to Force() anything yourself, it is done
//    when you try to access anything unevaluated

#include <cstdlib>
#include <iostream>
using namespace std;

// throw a fit
void throwFit(string fit) {
    cerr << "WAAAH: " << fit << "\n";
    exit (255);
}

template<typename T>class Node;
template<typename T>class LazyList;

// this is a thunk
// basically it stores a function and some args for later running

template<typename T>class Thunk {
    typedef LazyList <T> * (*Function) (void*);
    Thunk<T>::Function function;
public:
    void *arguments;
    Thunk( Thunk<T>::Function func, void *args ) {
        function = func;
        arguments = args;
    }
    
    Thunk( Thunk<T>::Function func ) {
        function = func;
        arguments = NULL;
    }
    
    LazyList<T> *go() { return function(arguments); }
};

// base class for lazy list
template<typename T> class Node {
public: 
    virtual bool Empty() = 0;
    virtual T Head() = 0;
    virtual LazyList <T> *Tail() = 0;
    virtual void ConnectToList() = 0;
};

// nil class
template<typename T>class Nil : public Node<T> {
public:
    Nil() {  }
    bool Empty() { return true; }
    T Head() { throwFit("Accessing empty list"); return (T)NULL; }
    LazyList<T>* Tail() { throwFit("Accessing empty list"); return (LazyList<T>*)NULL;}
    void ConnectToList() { throwFit("Accessing empty list"); }
};


// cons class
template<typename T>class Cons : public Node<T> {
    T car;
    LazyList<T> *cdr;
public:
    ~Cons() { delete cdr; }
    
    Cons(T car_, LazyList<T> *cdr_) {
        car=car_;
        cdr=cdr_;
    }
    Cons(T car_) {
        
        car=car_;
        cdr=new LazyList<T>(new Nil<T>());
    }
    
    void ConnectToList(LazyList<T> *cdr_) {
        cdr = cdr_;
    }
    
    bool Empty() { return false; }
    T Head() { return car; }
    LazyList<T>* Tail() { return cdr; }
    
};

// zipWith is just a special thunk, so these are some definitions
// used by zipWith
// it would be neater to put these in the LazyList class
// but that's not possible

template<typename T>struct zipWith_args {
    LazyList<T> *a;
    LazyList<T> *b;
    T(*function)(T, T);
};

template<typename T> LazyList<T>* zipWith_thunkf(void *vargs) {
    struct zipWith_args<T> *args = (struct zipWith_args<T>*) vargs;
    
    // first check if some of the lists are empty
    if (args->a->Empty() || args->b->Empty()) {
        // then return an empty list
        return new LazyList<T>(new Nil<T>());
    }
    
    // make new values
    T firstval = args->a->Head();
    T secondval = args->b->Head();
    T ourval = (args->function)(firstval, secondval);
    
    // make new arguments
    struct zipWith_args<T> *newargs = (struct zipWith_args<T>*)malloc(sizeof(zipWith_args<T>));
    newargs->a = args->a->Tail();
    newargs->b = args->b->Tail();
    newargs->function = args->function;
    
    // free old arguments
    free(args);
    
    // return a cons with the args and a new thunk
    LazyList<T> *thethunk = new LazyList<T>(new Thunk<T>(zipWith_thunkf, newargs));
    LazyList<T> *ourlist = new LazyList<T>(new Cons<T>(ourval, thethunk));
    
    return ourlist;
};

// lazy list class -- contains either a node or a Thunk
// will replace the Thunk by a node if asked for the Thunk's values

template<typename T>class LazyList {
    struct {
        union {
            Thunk<T> *thunk;
            Node<T> *node;
        } data;
        bool containsThunk;
    } contents;
    
    // 
    
    // runs the thunk if necessary
    void force() {
        if (! contents.containsThunk) return; // no thunk
        
        LazyList<T> *replacement = contents.data.thunk -> go();
        contents = replacement -> contents;
        
    }
public:
    // zipWith
    static LazyList<T> *ZipWith( T(*function)(T,T), LazyList<T> *a, LazyList<T> *b ) {
        struct zipWith_args<T> *zwargs = (struct zipWith_args<T>*) malloc(sizeof(zipWith_args<T>));
        zwargs -> a = a;
        zwargs -> b = b;
        zwargs -> function = function;
        return new LazyList<T>(new Thunk<T>(zipWith_thunkf, zwargs));
    }
    
    LazyList(Nil<T> *n) {
        contents.data.node = n;       
        contents.containsThunk = false;
    }
    LazyList(Cons<T> *n) {
        contents.data.node = n;
        contents.containsThunk = false;
    }
    
    LazyList(Thunk<T> *t) {
        contents.data.thunk = t;
        contents.containsThunk = true;
    }
    
    Node<T> *GetNode() {
        while (contents.containsThunk) force();
        return contents.data.node;
    }
    
    // connect this list to another list
    void ConnectToList( LazyList<T> *list ) {
        ((Cons<T>*) this->GetNode()) -> ConnectToList(list);
    }
    
    // data accessors
    bool Empty() {
        while (contents.containsThunk) force();

        return contents.data.node -> Empty();
    }
    
    T Head() {
        while (contents.containsThunk) force();
        return contents.data.node -> Head();
    }
    
    LazyList<T> *Tail() {
        while (contents.containsThunk) force();
        return contents.data.node -> Tail();
    }
    
    T* Take(int n) {
        T *data = new T[n];
        LazyList<T> *list = this;
        for (int i = 0; i < n; i++) {
            data[i] = list -> Head();
            list = list -> Tail();
        }
        return data;
    }
    
    // output all data
    void Print() {
        LazyList<T> *list = this;
        while (! list -> Empty() ) {
           
            cout << list -> Head() << " ";
            list = list -> Tail();
        }
    }
};

////-----LOGIC STARTS HERE------//////

int add(int a, int b) {
    return a + b;
}

int main(int argc, char **argv) {
    int numFib = 15; // amount of fibonacci numbers we'll print
    if (argc == 2) {
        numFib = atoi(argv[1]);
    }
    
    // list that starts off 1, 1...
    LazyList<int> fibo = LazyList<int>(new Cons<int>(1,
                     new LazyList<int>(new Cons<int>(1))));
    // zip the list with its own tail
    LazyList<int> *fiboZip = LazyList<int>::ZipWith(add, &fibo, fibo.Tail());
    // connect the begin list to the zipped list
    fibo.Tail() -> ConnectToList(fiboZip);
                                                 
    // print fibonacci numbers
    int *fibonums = fibo.Take(numFib);    
    for (int i=0; i<numFib; i++) cout << fibonums[i] << " ";
    
    cout<<endl;
    
    return 0;
}