Functional List in C++











up vote
0
down vote

favorite












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?










share|improve this question






















  • If you have reverse and cons functions, you should the code for them in the question.
    – 200_success
    7 hours ago















up vote
0
down vote

favorite












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?










share|improve this question






















  • If you have reverse and cons functions, you should the code for them in the question.
    – 200_success
    7 hours ago













up vote
0
down vote

favorite









up vote
0
down vote

favorite











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?










share|improve this 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?







c++ functional-programming interface






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked 2 days ago









Robert Hanigan

11010




11010












  • If you have reverse and cons functions, you should the code for them in the question.
    – 200_success
    7 hours ago


















  • If you have reverse and cons functions, you should the code for them in the question.
    – 200_success
    7 hours ago
















If you have reverse and cons functions, you should the code for them in the question.
– 200_success
7 hours ago




If you have reverse and cons functions, you should the code for them in the question.
– 200_success
7 hours ago










1 Answer
1






active

oldest

votes

















up vote
1
down vote



accepted










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();





share|improve this answer





















    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
    });
    });
    }, "mathjax-editing");

    StackExchange.ifUsing("editor", function () {
    StackExchange.using("externalEditor", function () {
    StackExchange.using("snippets", function () {
    StackExchange.snippets.init();
    });
    });
    }, "code-snippets");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "196"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    convertImagesToLinks: false,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














     

    draft saved


    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f208357%2ffunctional-list-in-c%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes








    up vote
    1
    down vote



    accepted










    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();





    share|improve this answer

























      up vote
      1
      down vote



      accepted










      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();





      share|improve this answer























        up vote
        1
        down vote



        accepted







        up vote
        1
        down vote



        accepted






        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();





        share|improve this answer












        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();






        share|improve this answer












        share|improve this answer



        share|improve this answer










        answered yesterday









        Martin York

        72k481254




        72k481254






























             

            draft saved


            draft discarded



















































             


            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f208357%2ffunctional-list-in-c%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            Ellipse (mathématiques)

            Quarter-circle Tiles

            Mont Emei