Recursive call to templatized functions with new template arguments

Question

I am trying to implement some functional constructs in C ++. It is required to implement a function that aligns the list of lists with any number of levels down.

template<typename T, typename R> struct Fold{ typedef R(*func)(T, R); }; template<typename T> T head(std::list<T> const& list) { return list.front(); } template<typename T> std::list<T> tail(std::list<T> list) { list.pop_front(); return list; } template<typename T> std::list<T> cons(T head, std::list<T> tail){ tail.push_front(head); return tail; } template<typename T, typename ACCUM> ACCUM foldl(typename Fold<T, ACCUM>::func function, ACCUM accum, std::list<T> list) { if(list.empty()) return accum; return foldl(function, (*function)(head(list), accum), tail(list)); } template<typename T, typename ACCUM> ACCUM foldr(typename Fold<T, ACCUM>::func function, ACCUM accum, std::list<T> list) { if(list.empty()) return accum; return (*function)(head(list), foldr(function, accum, tail(list))); } template<typename T> std::list<T> reverse(std::list<T> list){ struct LAMBDA{ static std::list<T> reverse(T t, std::list<T> tList){ return cons(t, tList); } }; std::list<T> revTList; return foldl( static_cast<typename Fold<T, std::list<T>>::func>(&LAMBDA::reverse), revTList, list); } template<typename T> std::list<T> append(std::list<T> list1, std::list<T> list2) { struct LAMBDA{ static std::list<T> append_lambda(T t, std::list<T> list){ return cons(t, list);; } }; return foldl( static_cast<typename Fold<T, std::list<T>>::func>(&LAMBDA::append_lambda), list2, reverse(list1)); } template<typename T, typename Ty> struct Flattener{ static std::list<T> flatten(typename std::list<Ty> deepList){ struct LAMBDA{ static Ty flatten_lambda(Ty ty, Ty accum){ return append(ty, accum); } }; Ty ty; Ty flat = foldr( static_cast<typename Fold<Ty, Ty>::func>(&LAMBDA::flatten_lambda), ty, deepList); return Flattener::flatten(flat); } }; template<typename T> struct Flattener<T, T>{ static std::list<T> flatten(std::list<T> list){ return list; } }; 

The above code compiles fine, but when I try to call a function with

 std::list<int> emptyList; std::list<int> list1 = cons(1, cons(2, cons(3, cons(4, emptyList)))); std::list<int> list2 = cons(5, cons(6, cons(7, cons(8, emptyList)))); std::list<std::list<int>> emptyDeepList; std::list<std::list<int>> deepList = cons(list1, cons(list2, emptyDeepList)); Flattener<int, std::list<int>>::flatten(deepList); 

I get this huge error when compiling code:

 error C2664: 'Flattener<T,Ty>::flatten' : cannot convert parameter 1 from 'std::list<T>' to 'std::list<T>' with [ T=int, Ty=std::list<int> ] and [ T=int ] and [ T=std::list<int> ] No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called list.h(212) : while compiling class template member function 'std::list<T> Flattener<T,Ty>::flatten(std::list<std::list<T>>)' with [ T=int, Ty=std::list<int> ] main.cpp(67) : see reference to class template instantiation 'Flattener<T,Ty>' being compiled with [ T=int, Ty=std::list<int> ] 

If I remove the Flattener::flatten , the code compiles.

What am I doing wrong? (Since I am new to C ++ programming and template, some explanations will also be useful).

Edit:

Tried this one. The same mistake. I think I'm on something.

 template<typename T, typename L> struct Flattener{ static std::list<T> flatten(L list){ struct LAMBDA{ static std::list<T> flatten_lambda(typename L1 l1, std::list<T> tList){ return append(Flattener<T, L1>::flatten(l1), tList); } }; std::list<T> tList; return foldl(&LAMBDA::flatten_lambda, tList, list); } }; template<typename T> struct Flattener<T, typename std::list<T>>{ static std::list<T> flatten(std::list<T> list){ return list; } }; 

And here is the compiler error for this:

 error C2664: 'Flattener<T,L>::flatten' : cannot convert parameter 1 from 'std::list<T>' to 'std::list<T>' with [ T=int, L=std::list<std::list<int>> ] and [ T=std::list<std::list<int>> ] and [ T=std::list<int> ] No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called 

Answer 1

declytype saves the day.

 template<typename T> list<T> _flattenOneLevel(list<list<T>> listOfTList) { auto lambda = [](list<T> tList, list<T> accumList) { return reverse(tList, accumList); }; return reverse(foldl(lambda, empty_list<T>(), listOfTList)); } template<typename T, typename _DeepList> struct _Flattener { static list<T> flatten(_DeepList deepList) { auto oneLevelDown = _flattenOneLevel(deepList); return _Flattener<T, decltype(oneLevelDown)>::flatten(oneLevelDown); } }; template<typename T> struct _Flattener<T, list<T>> { static list<T> flatten(list<T> list) { return list; } }; template<typename T, typename _DeepList> list<T> flatten(_DeepList deepList) { return _Flattener<T, _DeepList>::flatten(deepList); } 

More on type subtraction in recursive patterns: What are some uses of decltype (auto)?

Answer 2

AS @tMJ pointed out that writing Flattener<T, T> will lead to a compilation error, but the Flattener::flatten will be able to smooth only two levels of the deep list (in fact, the error will return when you try to smooth the m-nested list, where m >= 3 , since we will again have type mismatch).

To make this work for a list with m levels std::list<std::list<...<std::list<int>...>> , we need to find a way to type the element of the current container Ty . For example, if Ty = std::list<std::list<std::list<int>>> , then the current type of the Ty element is actually std::list<std::list<int>> . And this is the type of Ty, which should be installed in the next step of the recursion.

Fortunately, C ++ containers, such as std :: list, have a static value_type property, which is a synonym for the container's Type template parameter (in simple terms, it returns the type of the elements of this container). Knowing this, we can solve your problem as follows:

 template<typename T, typename Ty> struct Flattener { static std::list<T> flatten(typename std::list<Ty> deepList) { struct LAMBDA { static Ty flatten_lambda(Ty ty, Ty accum) { return append(ty, accum); } }; Ty ty; Ty flat = foldr(static_cast<typename Fold<Ty, Ty>::func>(&LAMBDA::flatten_lambda), ty, deepList); return Flattener<T, Ty::value_type>::flatten(flat); } }; template<typename T> struct Flattener<T, T> { static std::list<T> flatten(std::list<T> list) { return list; } }; 

The recursion will stop once T becomes equal to Ty::value_type , and this will happen when Ty becomes std::list<int> . At this point, Flattener<T, T>::flatten() will be executed, and it will give the final result.

I tested the solution with triple nested std::list :

 std::list<std::list<std::list<int>>> triple_empty_list; std::list<std::list<std::list<int>>> triple_list = cons(deepList, cons(deepList, triple_empty_list)); std::list<int> result = Flattener<int, std::list<std::list<int>>>::flatten(triple_list); 

PS To clarify, there is no recursion. Each call to Flattener<T,Ty>::flatten() calls a static method of different specialization of the Flattener class Flattener .

Answer 3

Your approach seems rather complicated to me. So let me share my decision, and I hope that it suits you. If you really need a code correction, not a solution to your problem, this is not an appropriate answer. All the code that I shared was tested with visual 2015 with 3 levels of recursion, but it should work on any compiler with any level of recursion.

So, let's start with the first problem. Your decision requires you to specify a data type, but that type is already known. So how to restore it automatically? We will use the structure for this:

 template <typename T> struct NestedListType { using type = T; }; 

Given the type, it gives only the same type. To specify a type inside a list, we need to specialize it:

 template <typename T> struct NestedListType<std::list<T> > { using type = typename NestedListType<T>::type; }; 

Now, if our type is a list, it will be value_type std::list , and therefore will be recursive until the type is std::list . Thus, it can work with several std::list layers.

Used like this:

 using DataType = typename NestedListType<std::list<std::list<int>>>::type; // DataType will be int 

Next we need to define our function. We need a function that will put each list of a nested type inside one big list. To avoid unnecessary copies, we will also pass our resulting list into the parameter of our function, so we need the first function to do this:

 // if you do not want to modify the original list, this is here where you should remove the reference and make a copy // T could be itself an std::list, no problem with that template <typename T> std::list<typename NestedListType<T>::type> flatten(std::list<T> & list) { // obtain a std::list with the appropriate type std::list<typename NestedListType<T>::type> result; flatten(list, result); return result; } 

And finally, we need to do a real job. We need two functions: one that receives a list of lists and sends each list, and one that receives a list and adds it to our result. To do this, we will simply use overloading, since we cannot (and should not) partially specialize functions:

 template <typename T, typename V> void flatten(std::list<std::list<T> > & list, std::list<V> & result) { // if you want to change the order or the resulting list, change here // here simply add the first list first and continue until the last for (auto & sublist : list) flatten(sublist, result); } template <typename T, typename V> void flatten(std::list<T> & list, std::list<V> & result) { // add the list to our result using references and splice to avoid unecessary copies or move result.splice(result.end(), list); } 

And it's all! Now you can just use it with as many lists and subscriptions you want:

 std::list<int> l1{ 1, 2, 3 }; std::list<int> l2{ 4, 5, 6 }; std::list<int> l3{ 7, 8, 9 }; std::list<int> l4{ 10, 11, 12 }; std::list<std::list<int> > sl1{ l1, l2 }; std::list<std::list<int> > sl2{ l3, l4 }; std::list<std::list<std::list<int> > > ssl{ sl1, sl2 }; auto result1 = flatten(l1); // gives { 1, 2, 3 } auto result2 = flatten(sl1); // gives { 1, 2, 3, 4, 5, 6 } auto result3 = flatten(ssl); // gives { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 } ... 

Hope this helps! If something is unclear, let me know and I will try to explain it better.

Answer 4

First, the error message should be read:

there is no known conversion for argument 1 from 'std :: list' to 'Stand :: List <std :: List <int →' In a static member function static std :: list Flattener :: flatten (std :: list <Ty> ) [with T = int; Ty = std :: list <int>] ':

Buggy compiler? or poor bonding?

This leads to the conclusion that you want another Flutter to call it so-changing:

 template<typename T, typename Ty> struct Flattener{ static std::list<T> flatten(typename std::list<Ty> deepList){ struct LAMBDA{ static Ty flatten_lambda(Ty ty, Ty accum){ return append(ty, accum); } }; Ty ty; Ty flat = foldr( static_cast<typename Fold<Ty, Ty>::func>(&LAMBDA::flatten_lambda), ty, deepList); return Flattener<T,T>::flatten(flat); } }; 

Note the extra <T,T> .