Recursive call to templatized function with new template arguments

Question

I am trying to implement some functional constructs in c++. Wanted to implement a function that flattens list of lists 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 attempt to call the 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 the 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 call to Flattener::flatten the code compiles.

What am I doing wrong? (As I am new to c++ and template programming, some explanation would be really helpful too).

Edit:

Tried this. Same Error. I think I am onto 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's the compiler error for this one:

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

Not sure, but `Fold::func` needs a `typename` since it's dependent. — Cheers and hth. - Alf, Oct 17 '15 at 22:08
Also, the `return Flattener::flatten(flat);` is infinitely recursive (or rather, would be infinitely recursive if the types allowed it to compile). It doesn't pick up the specialization of the class, because `Flatten` here refers to the instantation it's used in. — Cheers and hth. - Alf, Oct 17 '15 at 22:11
For the first comment, I think so too, but the compiler doesn't show an error, and then I got used to the habit of not writing. Cut to chase, it still works without `typename` being mentioned. — tmj, Oct 17 '15 at 22:13
Second comment, I see, so how do I redo this as to achieve what I want to do. — tmj, Oct 17 '15 at 22:13
You could write `Flattener::flatten`, where `A` and `B` are the relevant types, possibly the same single type? — Cheers and hth. - Alf, Oct 17 '15 at 22:14
I thought so too. Type for argument `A` is clear, which will remain `T`, however for argument `B`, I would want to send the type `X` (where `std::list` is equivalent to `Ty`). How to deduce `X` is still unclear to me. `Flattener::flatten` — tmj, Oct 17 '15 at 22:17
All the three functions `append`, `cons` and `foldr` have been implemented by me. I will edit the question to include them at the risk of overly bloating the question size. Also, as I mentioned, I am new to c++ I did not know about the `C-style` casts thing. I'll update that too. — tmj, Oct 17 '15 at 22:42
@tMJ that (obviously) compiles fine. What instantiation(s) cause the failure? — sehe, Oct 17 '15 at 23:00
Isn't `std::list>` different from `std::list` or do I have this wrong?... — CinchBlue, Oct 18 '15 at 13:02
@VermillionAzure Of course it is, what statement are you refering to though? — tmj, Oct 18 '15 at 13:05

dbajgoric · Answer 1 · 2015-10-26T23:10:35.587

AS @tMJ pointed out, writing Flattener<T, T> will make the compilation error go away, but Flattener::flatten method will be able two flatten only two levels deep list (actually error will come back when you try to flatten m-nested list where m >= 3 as we'll have type mismatch again).

In order to make this work for list with m levels std::list<std::list<...<std::list<int>...>> we have to have a way to find out what is the type of element of current Ty container. For example if Ty = std::list<std::list<std::list<int>>> then current type of element of Ty is actually std::list<std::list<int>>. And this is the type of Ty that must be set in next step of recursion.

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

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;
    }
};

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'll produce 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);

P.S. To clarify, there is no recursion happening here. Every call to Flattener<T,Ty>::flatten() invokes static method of different specialization of Flattener class template.

If one is not using a standard container or any other place where `Ty::value_type` constructs are not available, they can use `decltype` type speicifer to evaluate the type at compile time. See @tMJ's answer. — tmj, Nov 03 '15 at 09:18

score 2 · Accepted Answer · edited May 23 '17 at 11:51

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

Read more on Type deduction in Recursive Templates: What are some uses of decltype(auto)?

score 2 · Answer 3 · answered Oct 31 '15 at 00:20

Your approach seems rather complicated to me. So let me share my solution, and i hope it will suit you. If you really want a correction of your code, and not a solution to your problem, this is not the appropriate answer. All the code i share has been 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 by the first problem. Your solution requires to give the type of the data, but that type is already known. So how to recover it automatically? We'll use for that a structure:

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

Given a type, it only gives the same type. To give the type inside the 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 give the value_type of the std::list, and so recursively until the type is not a std::list. So it can work with several layers of std::list.

It is used that way:

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

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

// 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 the actual work. What we need is two functions: one that receives a list of lists and dispatch each list, and one that receives a list and add it to our result. For that we will simply use overloading, as we cannot (and do not need to) 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 that's all! Now, you can simply use it with as much list and sublist 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 it helps! If anything is not clear, let me know and i'll try to explain it better.

Surt · Answer 4 · 2015-10-26T21:52:39.520

1

First thing the error message should read:

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

Buggy compiler? or bad pasting?

This leads to the conclusion that you wanted the other Flattener called so change to:

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>.

edited Oct 26 '15 at 21:52

answered Oct 26 '15 at 21:39

Surt

15,501
3
23
39

bad pasting, sorry, edited out the actual name of the container. – tmj Oct 26 '15 at 21:42
1

but as far as I can guess, the change you suggest will only flatten one level down and not more. – tmj Oct 26 '15 at 21:43
So flattening a list of lists to a list isn't what you wanted? – Surt Oct 26 '15 at 21:50

Recursive call to templatized function with new template arguments

4 Answers4