Typelists, template function specialization, generic programming.
Greg Buchholz
I'm experimenting with some generic programming, and I'd thought
I'd
try an easy example first. The idea behind "fmap" below is similar to
STL "transform", but instead of working on just lists, it would work on
lists of lists, and lists of lists of lists..., etc. I started down a
different path...
http://groups.google.com/group/comp.lang.c++/browse_thread/thread/bbc7f73dc8d15252/0391fb10633939f6
...but when I couldn't get that to work, I thought I try a different
approach using typelists. But I get compiler errors like...
f.cpp:61: error: template-id `fmap<NullType, int, int>' for `int
fmap(int, int (*)(int))' does not match any template declaration
f.cpp:61: error: invalid function declaration
f.cpp: In function `typename compose<Coll, Out>::type fmap(typename
compose<Tem, Base>::type, Out (*)(In)) [with Coll = TemList<std::list,
NullType>, In = int, Out = int]':
f.cpp:106: instantiated from here
f.cpp:52: error: no matching function for call to `fmap(const int&, int
(*&)(int))'
...Anyone have advice on how to fix this, or what approach I should be
taking in order to implement "fmap"?
Thanks,
Greg Buchholz
*/
#include<iostream>
#include<list>
#include<iterator>
using namespace std;
class NullType {};
// A "template list" list like a lot like a "type list"...
template<template<class>class H, class T> struct TemList
{
typedef T Tail;
};
/* "compose" turns a list of templates into a type. For example...
list<list<list<int> > > > x;
...is the same as...
compose<TemList<list,
TemList<list,
TemList<list, NullType> > >,int >::type x;
*/
template<class Tem,class Base> struct compose;
template<template<class>class Tem,class Base>
struct compose<TemList<Tem,NullType>,Base >
{
typedef Tem<Base> type;
};
template<template<class>class Tem,class Tail, class Base>
struct compose<TemList<Tem,Tail>,Base >
{
typedef Tem<typename compose<Tail,Base>::type> type;
};
//Here is the "fmap" function, which should take an arbitrarily
//nested lists of lists of lists... and recursively apply a function
//to each member of the lists of lists of lists...
//Recursive Case: Should be used with nested lists
template<class Coll, class In, class Out>
typename compose<Coll,Out>::type
fmap(typename compose<Coll,In>::type l, Out (*f)(In))
{
typename compose<Coll,Out>::type temp;
for(typename compose<Coll,In>::type::const_iterator iter =
l.begin();
iter != l.end(); ++iter)
{
temp.push_back(fmap<typename Coll::Tail,In,Out>(*iter,f));
}
return temp;
}
//Base Case: No further calls to "fmap"
//C++ apparently doesn't support partial specialization of functions,
// so use a concrete "int" for this particular example...
template <> int fmap<NullType,int,int>(int i, int (*f)(int))
{
return f(i);
}
int inc(int x){ return x+1; }
template<class T>
std::ostream& operator<<(std::ostream&, const std::list<T>&);
int main(int argc, char* argv[])
{
int tmp[] = {1,2,3};
list<int> simple_list(tmp,tmp+3);
cout << "inc of simple list: " << simple_list << " => " ;
cout << fmap<TemList<list, NullType>,int,int>(simple_list,inc)
cout << endl;
list<list<int> > lol;
lol.push_back(simple_list);
lol.push_back(simple_list);
cout << "inc of lol: "<< lol << " => " ;
cout << fmap<TemList<list,TemList<list,NullType> >,int,int>(lol,inc)
cout << endl;
return 0;
}
template<class T>
std::ostream& operator<<(std::ostream& o, const std::list<T>& l)
{
o << "[";
for(typename std::list<T>::const_iterator i = l.begin(); i !=
--l.end(); ++i)
o << *i << ",";
return o << *(--l.end()) << "]";
}
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Zhenghui Zhou
Since the statand c++ doesn't support funtion template specialization,
so the code will not work as you want.
And Anderi had given a proposal called Int2Type which can help you to
solve the problem, and the code:
#include<iostream>
#include<list>
#include<iterator>
#include <boost/static_assert.hpp>
using namespace std;
template <int N>
struct Int2Type
{
enum { value = N };
};
class NullType {
};
// A "template list" list like a lot like a "type list"...
template<template<class>class H, class T> struct TemList
{
typedef T Tail;
};
/* "compose" turns a list of templates into a type. For example...
list<list<list<int> > > > x;
...is the same as...
compose<TemList<list,
TemList<list,
TemList<list, NullType> > >,int >::type x;
*/
template<class Tem,class Base> struct compose;
template<template<class>class Tem,class Base>
struct compose<TemList<Tem,NullType>,Base >
{
enum { length = 1 };
typedef Tem<Base> type;
};
template<template<class>class Tem,class Tail, class Base>
struct compose<TemList<Tem,Tail>,Base >
{
enum { length = compose<Tail, Base>::length + 1 };
typedef Tem<typename compose<Tail,Base>::type> type;
};
template<class Baes>
struct compose<NullType, Base>
{
enum { length = 0 };
};
//Here is the "fmap" function, which should take an arbitrarily
//nested lists of lists of lists... and recursively apply a function
//to each member of the lists of lists of lists...
//Base Case: No further calls to "fmap"
//C++ apparently doesn't support partial specialization of functions,
// so use a concrete "int" for this particular example...
template<class Coll, class In, class Out>
int fmap(int i, int (*f)(int), Int2Type<0>)
{
return f(i);
}
//Recursive Case: Should be used with nested lists
template<class Coll, class In, class Out>
typename compose<Coll,Out>::type
fmap(typename compose<Coll,In>::type l, Out (*f)(In),
Int2Type<compose<Coll,In>::length>)
{
typename compose<Coll,Out>::type temp;
for(typename compose<Coll,In>::type::const_iterator iter =
l.begin();
iter != l.end(); ++iter)
{
temp.push_back(fmap<typename
Coll::Tail,In,Out>(*iter,f,Int2Type<compose<typename
Coll::Tail,In>::length>()));
}
return temp;
}
int inc(int x){ return x+1; }
template<class T>
std::ostream& operator<<(std::ostream&, const std::list<T>&);
int main(int argc, char* argv[])
{
int tmp[] = {1,2,3};
list<int> simple_list(tmp,tmp+3);
cout << "inc of simple list: " << simple_list << " => " ;
cout << fmap<TemList<list,
NullType>,int,int>(simple_list,inc,Int2Type<compose<TemList<list,
NullType>, int>::length>());
cout << endl;
list<list<int> > lol;
lol.push_back(simple_list);
lol.push_back(simple_list);
cout << "inc of lol: "<< lol << " => " ;
cout << fmap<TemList<list,TemList<list,NullType>
>,int,int>(lol,inc,Int2Type<compose<TemList<list,TemList<list,NullType> >,int>::length>());
cout << endl;
return 0;
}
template<class T>
std::ostream& operator<<(std::ostream& o, const std::list<T>& l)
{
o << "[";
for(typename std::list<T>::const_iterator i = l.begin(); i !=
--l.end(); ++i)
o << *i << ",";
return o << *(--l.end()) << "]";
}
BTW: I think the compose class is something chaos here:)
Greg Buchholz
>
> Since the statand c++ doesn't support funtion template specialization,
> so the code will not work as you want.
>
> And Anderi had given a proposal called Int2Type which can help you to
> solve the problem, and the code:
Excellent! I knew it must be possible, I just wasn't using the
correct incantation. Looks like it uses a "phantom type" right? I
just got of copy of "Modern C++ Design", so along with your code, I've
probably got plenty to study for a while.
> BTW: I think the compose class is something chaos here:)
Yeah, no disagreements there. But it would be interesting to have
a library of reusable generic functions like "fmap", right? Or is it
too esoteric to ever be of any practial use in C++? Now I just need to
figure out how to get the compiler to deduce those those typelists (is
that *very* wishful thinking, or merely moderately wishful thinking?).
Thanks again,
Greg Buchholz
Carl Barron
Zhenghui Zhou <zhouzh...@gmail.com> wrote:
> Greg Buchholz wrote:
> > /*
> > I'm experimenting with some generic programming, and I'd thought
> > I'd
> > try an easy example first. The idea behind "fmap" below is similar to
> > STL "transform", but instead of working on just lists, it would work on
> > lists of lists, and lists of lists of lists..., etc. I started down a
> > different path...
> >
I am guessing you want to transform the list<list<... > ... > as if it
was a flattened list. The problem then reduces to whether the argument
of list <list<Q> > or list<Q> this assumes the types in the 'flattened'
list is not a container. All stl containers have a typedef member
const_iterator. Defining a container as a type with a typedef member
const_iterator, the problem can be solved by SFINAE. I leave the
details to boost::mpl to provide a macro to create an SFINAE class to
check for const_iterator. and boost::mpl::true_,boost::mpl::false_ to
hold the results of the test and to overload the template function
fmap.
A solution [not super tested] but works with a vector<vector<int> >.
The code should work with vector<list<deque<T> > > as well...
// begin code
#include <boost/mpl/has_xxx.hpp>
#include <boost/mpl/bool.hpp>
#include <boost/mpl/and.hpp>
#include <algorithm>
// create the SFINAE class
BOOST_MPL_HAS_XXX_TRAIT_DEF(const_iterator) // no ;
// a meta function to allow specialization if a container does
// not contain a typedef ... const_iterator. A container needs
// iterator 'generaators' begin(),end(),and a type iterator to
// iterate the collection as per std iterators.
template <class T>
struct is_container:has_const_iterator<T>{};
// key test is this a container of container,
template <class T>
struct is_container_of_container:boost::mpl::and_
<
typename is_container<T>::type,
typename is_container<typename T::value_type>::type
> {};
// easy case list is not a container of container.
template <class T,class Func,class Out>
Out fmap(T & list,Func f,Out out,boost::mpl::false_)
{
return std::transform(list.begin(),list.end(),out,f);
}
// general case list is a container of container.
template <class T,class Func,class Out>
Out fmap(T &list,Func f,Out out,boost::mpl::true_)
{
typedef typename is_container_of_container
<
typename T::value_type
>::type bool_type;
for(T::iterator it=list.begin();it!=list.end();++it)
{
out = fmap(*it,f,out,bool_type());
}
return out;
}
// main template function that user actually uses...
template <class T,class Func,class Out>
Out fmap(T &list,Func f,Out out)
{
typedef typename is_container_of_container<T>::type bool_type;
return fmap(list,f,out,bool_type());
}
// end code.
Greg Buchholz
> I am guessing you want to transform the list<list<... > ... > as if it
> was a flattened list. The problem then reduces to whether the argument
> of list <list<Q> > or list<Q> this assumes the types in the 'flattened'
> list is not a container.
Thanks for the code, it gives me more to study and think about. I
was actually looking to keep the shape of the containers the same (i.e.
not flattened). The eventual idea was to see if I couldn't come up
with a set of generic array primitives, like in the J and K
languages...
http://www.jsoftware.com/
http://www.kuro5hin.org/story/2002/11/14/22741/791
...execpt it would be statically typed and embedded in C++.
Thanks,
Greg Buchholz
Larry
> /*
> I'm experimenting with some generic programming, and I'd thought
> I'd
> try an easy example first. The idea behind "fmap" below is similar to
> STL "transform", but instead of working on just lists, it would work on
> lists of lists, and lists of lists of lists..., etc. I started down a
> different path...
>
> http://groups.google.com/group/comp.lang.c++/browse_thread/thread/bbc7f73dc8d15252/0391fb10633939f6
>
> ...but when I couldn't get that to work, I thought I try a different
> approach using typelists. But I get compiler errors like...
> ...Anyone have advice on how to fix this, or what approach I should be
> taking in order to implement "fmap"?
type of the result tree given the source tree. To that end, I created
a
rebind<TreeSrc,NewLeaf>::type template metafunction which, given a tree
of type TreeSrc, it replaces the OldLeaf types with NewLeaf. The rest
comes pretty easy; however, instead of using only a function template,
which, as you noted, doesn't allow partial specialization, I used
a function template which call a static function in a class template.
This allowed the needed partial specialization.
Anyway, the code is in:
http://boost-consulting.com/vault/
in the iterators subdirectory in transform_tree.zip.
Let me know if you've got questions.
Larry
[snip]
>> ...Anyone have advice on how to fix this, or what approach I
>> should be
>> taking in order to implement "fmap"?
> When I tried, I found the problem was figuring how to calculate the
> type of the result tree given the source tree. To that end, I created
> a
> rebind<TreeSrc,NewLeaf>::type template metafunction which, given a
> tree
> of type TreeSrc, it replaces the OldLeaf types with NewLeaf. The rest
> Anyway, the code is in:
>
> http://boost-consulting.com/vault/
>
> in the iterators subdirectory in transform_tree.zip.
The rebind template metafunction is "primarily" implemented
using application_parts, which really just dissects a template
instantiation. I've just uploaded the docs for that to
http://boost-consulting.com/vault
/Template Metaprogramming/mpl-extensions-refmanual.html
However, these docs describe the code as it existed prior to the
addition of application_parts_stl_def_alloc.hpp which is used
to handle (imperfectly) default template args. The test program,
libs/mpl/test/application_parts_test.cpp
in the transform_tree.zip file shows the imperfection if the
#if in rebind_level template in rebind_tree.hpp is changed
to select the #else branch.
I hope the docs make it clearer what's going on, and
any help in perfecting rebind_level would be appreciated.
Larry
> Larry wrote:
[snip]
> However, these docs describe the code as it existed prior to the
> addition of application_parts_stl_def_alloc.hpp which is used
> to handle (imperfectly) default template args. The test program,
>
> libs/mpl/test/application_parts_test.cpp
Wrong. The proper test program is mentioned in the rebind_tree.hpp
comments.
[snip]
I've uploaded a newer version of transform_tree.zip which has
better comments in nested_value_type_mpl_iterator.hpp. This
should make the workings of rebind a little clearer.
Anybody else iterested in this?