Thread: iterator int template class

I am trying to create a Haskell-like list. So I wrapped a normal C++ list. I have a problem though declaring an iterator:

Code:

template <class T>
class hList
{
	list<T> data;
public:	
	hList<T> head() {
		hList<T>* tail = new hList<T>;
		if (this->data.size() == 0) return *tail;
		tail->data.push_back(*(this->data.begin()));
		data.pop_front();
		return *tail;
	}
	hList<T> operator+(hList<T>& l) {
		data.insert(data.end(), l.data.begin(), l.data.end());
		return *this;
	}
	hList<T> sel(hList<T>& l, bool (*fun)(const hList<T>&,  const hList<T>&)){	
		list<T>::iterator it;        // <============= error
	}		
};

I assume you cannot declare an iterator since the T class isn't known?
In any case what should I do? I wan to iterate through all the elements of list<T> data.

My goal is to do this:

Code:

template <class T>
hList<T> qsortH(hList<T>& l)
{
	hList<T> h = l.head();
	if (h.data.size() == 0) return l;
	return qsort(l.sel(l,lesser) + h + qsort(l.sel(l,greater)));
}

to simulate this example showing how simple and easy read Haskell can be:

Code:

qsort1 []     = []
qsort1 (p:xs) = qsort1 lesser ++ [p] ++ qsort1 greater

Any other suggestions are welcome

hList doesn't contain an iterator type. How do you expect to declare a variable of that type?

If you want list's iterator, you need to know that the type is "dependent" - it could depend on the template parameter whether it's a type or an object. Thus, you need the typename keyword to disambiguate:

Code:

typename list<T>::iterator it;

For the rest of your code:

1)Shouldn't head return a value of type T, the value returned being the first element.
2)Unlike Haskell, your functions arn't pure. If you are trying to write Haskell functions in C++, then all your functions should be pure, implying that they take const references (or copies) as arguments, and are all methods are const.
3) Unlike Haskell, C++ does not have lazy evaluation. To order to implement lazy evaluation in C++, your functions should not return their result. Instead, they must return the sequence of steps to reach those results, including the sequence of steps resulting from function they call. Only functions like show actually force the evaluation of functions in Haskell. Not that you necessarily want to go to that length, but that is what it would toke to translate that function into C++.

Ok, not to create a new topic, I updated the code. I have the return statement unfinished, because I get errors. I will finish it tomorrow. Though, can someone look at the code and give me some opinions? I want to do things as noted in the first post. Any ideas welcomed...

Code:

#include <iostream>
#include <vector>
#include <list>
using namespace std;

template <class T>
class hList
{
public:
	list<T> data;
	typename list<T>::iterator it;
	hList<T>* head() {
		hList<T>* tail = new hList<T>;
		if (this->data.size() == 0) return tail;
		tail->data.push_back(*(this->data.begin()));
		data.pop_front();
		return tail;
	}
	hList<T>& operator+(hList<T>& l) {
		data.insert(data.end(),l.data.begin(),l.data.end());
		return *this;
	}
	hList<T>& filter(const T c, bool (*fun)(const T&, const T)){
		hList<T>& result = new hList<T>;
		for (it = data.begin(); it != data.end(); ++it)
			if(fun(*it, c))
				result.data.push_back(*it);
		return result;
	}
};

bool lesser(const int i, const int c)
{
	if (i < c) return true;
	else return false;
}

bool greater(const int i, const int c)
{
	if (i > c) return true;
	else return false;
}

template <class T>
hList<T>& qsortL(hList<T>& l)
{
	hList<T> h = *l.head();
	if (h.data.size() == 0) return l;
	return ;
}

The objection about the return type of head still applies.
The name of cmp is poorly chosen. The name implies that the function compares something to something else, and returns a boolean, or possibly a tri-state relation (less, equal, greater). The correct name for this function is filter.
Passing function pointers is so C. In C++, that should be a member template that takes a proper comparison predicate. This would allow you to take not only std::less<T> etc., but even binders and lambda expressions. It would also be more efficient than function pointers, since functors can be inlined.

Originally Posted by C_ntua

1) Well, I just made it return a hList, because that is how it is handled, as a list with one element. Otherwise I could use the overloaded operator + for example with it. I would have to make another one, so it matches this case also. I will eventually...

Why not make a hList constructor takes one element. Or a cons function that prepends an element to a list.

2) Yeah, that is how it was in the beginning. But wouldn't that make it ineffective? It would make a lot of copies. Haskell knows how to handle its own language, but doing the same with C++ would mean a lot of copying and memory slowing things down. It would make thinks a lot easier though. But I would prefer to stick with something that has some performance. But anyhow, I want to simulate the list not everything in Haskell!

Basically I just want the features of filtering (yeah, much better name ) a list and separating the head from the tail so you can do things easily using recursion. And of course being able to use some operators. Like +. I will also overload - and probably []. That is basically it.

Here's how to do these things with std::list :
the features of filtering
Use std::list::remove_if.

separating the head from the tail
To get the head, you just return the first element. To get the tail you remove the first element, and return the list.

Like +
Use std::copy() with a back inserter as the target.

I will also overload -
What do you want - to do?

It's not inefficient as long as you use those functions. Except that recursion will by it's nature be inefficient.

and probably [].
Would this do list indexing, or do you just want a function to return an empty list? You can't overload [] to take no arguments. List indexing is inherently inefficient.

Since I want my list to be functional I will make them an option.

When you need random access, you shouldn't have used list in the first place.

Can you show me a sample code how can this be done without a function pointer?

Code:

template <typename T>
class hList
{
...
  template <typename UnaryPred>
  hList<T> filter(UnaryPred p) {
    hList<T> target;
    for(typename list<T>::iterator it = data.begin(); it != data.end(); ++it) {
      if(p(*it)) target.data.push_back(*it);
    }
    return target;
  }
};

Usage with std::tr1::bind:

Code:

#include <tr1/functional>

hList<int> l = ...;
hList<int> l2 = l.filter(std::tr1::bind(std::less<int>(), std::tr1::_1, 4));

Usage with boost::lambda:

Code:

#include <boost/lambda.hpp>

l2 = l.filter(boost::lambda::_1 < 4);

By the way, your usage of references and new is not only syntactically invalid, but also very likely a memory leak.

Originally Posted by C_ntua

Can you show me a sample code how can this be done without a function pointer?

Basically, all you would have to do is create a template type parameter:

Code:

template<typename T>

And then just use that type as-is in the function parameter list:

Code:

hList<T> filter(T p)

Now, all types that match the interface, whether it's a function pointer or some custom class with properly overloaded operators will work.
It's a technique usually known as static polymorphism and is very powerful.