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

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

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

Answer 2

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.