Skip to content

Instantly share code, notes, and snippets.

@okaram
Created October 13, 2012 04:42
Show Gist options
  • Save okaram/3883253 to your computer and use it in GitHub Desktop.
Save okaram/3883253 to your computer and use it in GitHub Desktop.
cons lists in C++
template<typename T>
struct ConsNode {
public:
ConsNode(T car=T(), ConsList<T> cdr=ConsList<T>()):_car(car),_cdr(cdr) {}
private:
T _car;
ConsList<T> _cdr;
friend T car<>(const ConsList<T> &l);
friend const ConsList<T>& cdr<>(const ConsList<T> &l);
};
template <typename T>
using ConsList= std::shared_ptr<ConsNode <T> >;
template<typename T>
ConsList<T> cons(T car, const ConsList<T>& cdr=ConsList<T>()) {
return std::make_shared<ConsNode<T> > (car,cdr);
}
template<typename T>
T car(const ConsList<T>&l)
{
return l->_car;
}
template<typename T>
const ConsList<T>& cdr(const ConsList<T>&l)
{
return l->_cdr;
}
template<class T>
bool isEmpty(const ConsList<T>&l)
{
return !l;
}
int main(void)
{
ConsList<int> l=cons(3,cons(4,cons(7)));
ConsList<int> l2=cons(9,cons(5,l)); // l2 shares the last 3 elements with l
ConsList<int> l3=cons(11,cdr(l2)); // l3 shares with l2, and also with l
cout << car(l) << " " << car(cdr(l)) << endl;
cout << len(l2) << " " << sum(l2) << endl;
cout << l2 << endl;
cout << l3 << endl;
}
template<class T>
std::ostream& operator<<(std::ostream& o, const ConsList<T>&l)
{
if(!isEmpty(l))
o << car(l) << " " << cdr(l);
return o;
}
template<class T>
std::ostream& operator<<(std::ostream& o, const ConsList<T>&l)
{
if(l)
o << car(l) << " " << cdr(l);
return o;
}
template<typename T>
unsigned len(const ConsList<T>&l)
{
if(!isEmpty(l))
return 0;
return 1+len(cdr(l));
}
template<typename T>
T sum(const ConsList<T>& l)
{
if(isEmpty(l))
return 0;
return car(l)+sum(cdr(l));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment