Functional List in C++ [closed]

Question

This is rather toy example of immutable datatype in C++. I've tried to follow functional languages like Scheme, Racket - making list as a cons cell: list is list or is empty.

/*
 * Abstract class
 */ 
template <class T>
class ImmutableList {

public:
~ImmutableList() {std::cout << "base class destructor";}
virtual bool is_empty() = 0;
virtual T head() = 0;
virtual ImmutableList<T> * tail() = 0; 
virtual int length() = 0;
};

/*
 * class non empty List
 */

template <class T>
class List: public ImmutableList<T> {

int size = 1;
T first;
ImmutableList<T> * rest;
public:

List(T _first, ImmutableList<T> * _tail){
    first = _first;
    rest = _tail;
    size += _tail->length();
}
~List() {std::cout << "List class destructor";}
bool is_empty() { return false; }

T head(){
    return first;
}

ImmutableList<T>* tail(){
    return  rest;
}

int length() {return size;}
};

/*
 * class empty list
 */
template <class T>
class Nil: public ImmutableList<T> {
    public:
    ~Nil();
    bool is_empty() {return true;}
    int length() {return 0;}
    T head() {
        throw std::logic_error("Head of empty list!");
    }
    ImmutableList<T> * tail() {
        throw std::logic_error("Tail of empty list!");
    }
};

There is more functions, like a reverse, there is also cons function - constructs a list.
Do this really need destructors? Will be better to use smart pointers?

Answer 1

Overview

The trouble here is ownership. Who owns the tail?

In C++ ownership is a very important topic and defines who is responsible for who should destroy an object. The problem with C like pointers is there are no explicit ownership semantics. So as part of the documentation you need to define who the owner (and people read documentation is the problem here) is otherwise things go wrong and the wrong person will delete the object or it will never get deleted.

This is why in modern C++ it is very uncommon to see C-pointers. Because there is no ownership defined. You can use smart pointers to explicitly define the owner of a pointer or you can use references to show that you are retaining ownership.

Note: Inside a class it's OK to use a pointer as you control everything inside a class. The problems happen when you leak a pointer through a public interface.

You don't show how you expect your class to be used, but given the interface it is easy to use it with pointers and leak object all over the place. Given the current interface I would expect the following to be standard usage:

 ImmutableList<int>* data = new List<int>(1, new List<int>(2, new List<int>(3, new Nil<int>())));

 // Do stuff.

 delete data;

This leads to all but the first element from being leaked (because the destructor does not delete the chain).

Now you can't just add a delete into the destructor as you can retrieve the tail and place it another object.

ImmutableList<int>* data1 = new List<int>(1, new Nil<int>());
ImmutableList<int>* data2 = new List<int>(2, data1->tail());

In this situation simply deleting the tail is not going to work as both data1 and data1 share the same tail. So you need some form of shared ownership semantics. Now you can do this yourself but if you try and implement your own ownership semantics then you need to define the copy and move operators for your class.

// Copy Operators
List& List::List(List const&);
List& List::operator=(List const&);

// Move Operators
List& List::List(List&&);
List& List::operator=(List&&);

This becomes exceedingly not trivial when you have shared objects. So really you need to use std::shared_ptr.

Code Review

If you have a base class with virtual methods then you your destructor should also be virtual:

template <class T>
class ImmutableList {
    public: 
       // Destructor should be declared virtual
       ~ImmutableList() {std::cout << "base class destructor";}
       ...
}

This is because you are likely to use delete on a base class pointer that points at a derived type. If the destructor is not virtual you call the wrong destructor.

Your code is not const correct.

virtual bool is_empty() = 0;
virtual T head() = 0;
virtual ImmutableList<T> * tail() = 0; 

All the above methods are const (as your class is Immutable). So you can change the object just query it.

virtual bool              is_empty() const = 0;
virtual T                 head()     const = 0;
virtual ImmutableList<T>* tail()     const = 0; 
virtual int               length()   const = 0;
                                  // ^^^^^

You return the head by value. This causes a copy of the object. Now for int and other simple types this is not a problem. But for complex types (like vector) a copy may be much more expensive.

So normally you return by reference. Not because the class in Immutable you should return a const reference.

virtual const& T head()                 const = 0;
    //  ^^^^^^

Now you return a reference to the object (allowing it to be queried). If you actually want a copy you can assign it to a variable and it will be copied.

T val = data1->head();