Unpacking parameter pack with templated predicate

[prestokeys]

I'm trying to generalize the following (working) code:

#include <iostream>
#include <string>
#include <cmath>

int foo (int num) {return num;}
int foo (double num) {return std::round (num);}
int foo (std::string str) {return str.length();}

template <class T>
void predicate_and_action (const T& t) {
	if (foo(t) == 5)
		std::cout << "Hooray!" << std::endl;
}

template <class T>
void check (const T& t) {
	predicate_and_action(t);
}

template <class FIRST, class...REST>
void check (const FIRST& first, const REST&...rest) {
	predicate_and_action (first);
	check (rest...);
}

int main() {
	check (5, 4.9, "smile");
	std::cin.get();
}  

Output:

Hooray!
Hooray!
Hooray!

But the following attempt with PREDICATE_AND_ACTION template parameter fails to compile:

#include <iostream>
#include <string>
#include <cmath>

int foo (int num) {return num;}
int foo (double num) {return std::round (num);}
int foo (std::string str) {return str.length();}

template <class T>
void predicate_and_action (const T& t) {
	if (foo(t) == 5)
		std::cout << "Hooray!" << std::endl;
}

template <class PREDICATE_AND_ACTION, class T>
void check (PREDICATE_AND_ACTION pred_action, const T& t) {
	pred_action(t);
}

template <class PREDICATE_AND_ACTION, class FIRST, class...REST>
void check (PREDICATE_AND_ACTION pred_action, const FIRST& first, const REST&...rest) {
	pred_action(first);
	check (pred_action, rest...);
}

int main() {
	check (predicate_and_action, 5, 4.9, "smile");
	std::cin.get();
} 

Template argument deduction failed, it says. And using pred_action<T> and pred_action<FIRST> only makes it worse. How to fix this? Do we need to use a visitor pattern or something like that?

[prestokeys]

Is what I'm trying to achieve impossible because predicate_and_action<T> needs to be known at compile time? I'm sure there is a workaround of some sort.

[JLBorges]

#include <iostream>
#include <string>
#include <cmath>

int foo (int num) {return num;}
int foo (double num) {return std::round (num);}
int foo (std::string str) {return str.length();}

template <class T>
struct predicate_and_action {
    void operator() (const T& t ) const {
        if (foo(t) == 5) std::cout << "Hooray!" << std::endl;
    }
};

template < template<typename> class PREDICATE_AND_ACTION, class T >
void check ( const T& t) {
	PREDICATE_AND_ACTION<T>()(t);
}

template < template<typename> class PREDICATE_AND_ACTION, class FIRST, class...REST >
void check( const FIRST& first, const REST&...rest) {
	PREDICATE_AND_ACTION<FIRST>()(first);
	check<PREDICATE_AND_ACTION>( rest... );
}

int main() {
	check<predicate_and_action>( 5, 4.9, "smile" );
	//std::cin.get();
}

http://coliru.stacked-crooked.com/a/805abd8184fa9db1