[Generic/Polytypic] Template not quite right

[Greg Buchholz]

/*
I've been experimenting with some generic/polytypic programs, and
I've stumbled on to a problem that I can't quite figure out. In the
program below, I'm trying to define a generic version of "transform"
which works not only on lists, but lists of list, lists of lists of
lists, etc. I'm calling it "fmap" and it passes around actual lists
instead of iterators (for now). In order to get it to work, I thought
I'd have one templated function which works on just lists (call this is
base case) and another templated function which works on lists of lists
of lists... and recursively calls "fmap" until we get down to a simple
list of something and then we call the base case. My current thinking
is that the "fmap" labeled Recursive Case #1 should be the most
general,
and should make all the code below work properly. Unfortunately, my
intuition appears to be wrong, and I needed to define Recursive Cases
#2
and #3 in order to get the examples below to work. Can anyone help me
see why #1 doesn't work? Commenting out the "#define REC_No_2_3"
results in errors like...

t.C:122: error: No match for 'fmap(list<list<int> > &, char(&)(int))'
t.C:126: error: No match for 'fmap(list<list<int> > &, int(&)(int))'
t.C:130: error: No match for 'fmap(list<list<list<int> > > &,
int(&)(int))'

....for the first error, it seems like it should be able to match my #1
by instantiating...
In = list
Out = list
T = int
U = char

....Or maybe you can provide a link to other people working on polytypic
programming in C++? (You can look at a syntax highlighted version of
the code at... http://sleepingsquirrel.org/cpp/test_fmap.cpp.html )

Thanks,

Greg Buchholz
*/
#include<iostream>
#include<list>
#include<algorithm>
#include<functional>
#include<iterator>

#define REC_No_2_3 //undef to comment out extra code that I think
//shouldn't be needed.
using namespace std;

//Base Case: No further calls to "fmap"
template<template<class> class In, class T, class U>
In<U> fmap(In<T> i, U (*f)(T))
{
In<U> temp;
transform(i.begin(),i.end(),back_inserter(temp),f);
return temp;
}

//Recursive Case #1: Should be used with nested lists
template<template<class>class In, template<class> class Out, class T,
class U>
list<Out<U> > fmap(list<In<T> > l, U (*f)(T))
{
list<Out<U> > temp;
// Using "transform" doesn't work, complaining of unresolved
overloading
// of bind2nd...
// transform(l.begin(),l.end(),back_inserter(temp),
bind2nd(fmap,f));
// return temp;

for(typename list<In<T> >::const_iterator iter = l.begin();
iter != l.end(); ++iter)
{
temp.push_back(fmap(*iter,f));
}
return temp;
}

#ifdef REC_No_2_3
//Recursive Case #2: Note that the output data structure has to be the
// same as the input data structure.
template<class In, class Func> list<list<In> > fmap(list<list<In> > l,
Func f)
{
list<list<In> > temp;
for(typename list<list<In> >::const_iterator iter = l.begin();
iter != l.end(); ++iter)
{
temp.push_back(fmap(*iter,f));
}
return temp;
}

//Recursive Case #3: Seems like the problem here is that "Out" doesn't
// depend on "In", so "Out" has to be manually
specified.
template<class In, class Out, class Func>
list<list<Out> > fmap(list<list<In> > l, Func f)
{
list<list<Out> > temp;
for(typename list<list<In> >::const_iterator iter = l.begin();
iter != l.end(); ++iter)
{
temp.push_back(fmap(*iter,f));
}
return temp;
}
#endif

int lsize(list<int> l) //compute number of elements in a list
{
int size = 0;
for(list<int>::const_iterator i = l.begin(); i!= l.end(); ++i)
size++;
return size;
}

int inc(int x){ return x+1; }
char to_char(int x){ return 'A'+(char)x; }

template<class T> std:stream& operator<<(std:stream&, const
std::list<T>&);

int main(int argc, char* argv[])
{
int tmp[] = {1,2,3};
list<int> simple_list(tmp,tmp+3);

list<list<int> > lol;
lol.push_back(simple_list);
lol.push_back(simple_list);

cout << "to_char of simple list: " << simple_list << " => "
<< fmap(simple_list,to_char) << endl;

#ifndef REC_No_2_3
cout << "lol = " << lol << endl
<< "lengths of lol's lists = " << fmap(lol,lsize) << endl;
#endif

//This example uses Recursive #3.
cout << "to_char of lol: "<< lol << " => "
<< fmap<int,char>(lol,to_char) << endl;

//The next two "fmap"s use Recursive #2.
cout << " inc of lol: "<< lol << " => "
<< fmap(lol,inc) << endl;

list<list<list<int> > > lolol;
lolol.push_back(lol);
cout << " inc of lolol: "<< lolol << " => " << fmap(lolol,inc) <<
endl;

//And I haven't yet got this to work...
//cout << "to_char of lolol: "<< lolol << " => "
// << fmap(lolol,to_char) << endl;

return 0;
}

template<class T> std:stream& operator<<(std:stream& 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()) << "]";
}

 

[Greg Buchholz]

/*
OK, I've solved part of my problem. In "Recursive Case #1",
changing the template parameter "Out" to "In" allows a few more of my
examples to run. Now I need to know how to pass a multiply nested
template to a templated template parameter (er, there's probably a
better, more techinical wording for that). For example (from below)...

fmap<list<list>,list<list> >(lolol,inc)

....isn't proper syntax. My compiler (g++) complains...

t.C:113: error: type/value mismatch at argument 1 in template parameter
list for 'template<class _Tp, class _Alloc> class list'
t.C:113: error: expected a type, got 'list'
t.C:113: error: template argument 2 is invalid
t.C:113: error: type/value mismatch at argument 1 in template parameter
list for 'template<class _Tp, class _Alloc> class list'
t.C:113: error: expected a type, got 'list'
t.C:113: error: template argument 2 is invalid
t.C:113: error: No match for 'fmap(list<list<list<int> > > &, int
(&)(int))'

....And I'd appreciate any tips or hints on changes I could make to the
code in order to help the compiler deduce the template parameters
without having to manually specify them.

Thanks,

Greg Buchholz
*/
#include<iostream>
#include<list>
#include<algorithm>
#include<functional>
#include<iterator>

#define PROBLEM_AREA //undef to comment out problem areas and
//successfully compile the rest of program.
using namespace std;

//Base Case: No further calls to "fmap"
template<template<class> class In, class T, class U>
In<U> fmap(In<T> i, U (*f)(T))
{
In<U> temp;
transform(i.begin(),i.end(),back_inserter(temp),f);
return temp;
}

//Recursive Case #1: Should be used with nested lists
template<template<class> class In, template<class> class Out, class T,
class U>
list<In<U> > fmap(list<In<T> > l, U (*f)(T))
{
list<In<U> > temp;

for(typename list<In<T> >::const_iterator iter = l.begin();
iter != l.end(); ++iter)
{
temp.push_back(fmap(*iter,f));
}
return temp;
}

int lsize(list<int> l) //compute number of elements in a list
{
int size = 0;
for(list<int>::const_iterator i = l.begin(); i!= l.end(); ++i)
size++;
return size;
}

int inc(int x){ return x+1; }
char to_char(int x){ return 'A'+(char)x; }

template<class T> std:stream& operator<<(std:stream&, const
std::list<T>&);

int main(int argc, char* argv[])
{
int tmp[] = {1,2,3};
list<int> simple_list(tmp,tmp+3);

list<list<int> > lol;
lol.push_back(simple_list);
lol.push_back(simple_list);

cout << "to_char of simple list: " << simple_list << " => "
<< fmap(simple_list,to_char) << endl;

cout << "lol = " << lol << endl
<< "lengths of lol's lists = " << fmap(lol,lsize) << endl;

cout << "to_char of lol: "<< lol << " => "
<< fmap<list,list,int,char>(lol,to_char) << endl;

cout << " inc of lol: "<< lol << " => "
<< fmap<list,list>(lol,inc) << endl;

list<list<list<int> > > lolol;
lolol.push_back(lol);

/* How do you tell the compiler that the template parameters
are lists of lists? */
#ifdef PROBLEM_AREA
cout << " inc of lolol: "<< lolol << " => "
<< fmap<list<list>,list<list> >(lolol,inc) << endl;

cout << "to_char of lolol: "<< lolol << " => "
<< fmap<list<list>,list<list> >(lolol,to_char) << endl;
#endif

return 0;
}

template<class T> std:stream& operator<<(std:stream& 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()) << "]";
}

 

[XHengDF]

change to:
#include<iostream>
#include<list>
#include<algorithm>
#include<functional>
#include<iterator>
using namespace std;

//Base Case: No further calls to "fmap"
template<template<class> class Alloc, template<class, class> class
Container, class T, class U>
Container<U, Alloc<U> > fmap(Container<T, Alloc<T> > i, U (*f)(T))
{
Container<U, Alloc<U> > temp;
transform(i.begin(),i.end(),back_inserter(temp),f);
return temp;
}

//Recursive Case #1: Should be used with nested lists
template<template<class> class Alloc, template<class, class> class
Container, class T, class U>
list<Container<U, Alloc<U> > > fmap(list<Container<T, Alloc<T> > > l, U
(*f)(T))
{
list<Container<U, Alloc<U> > > temp;

for(typename list<Container<T, Alloc<T> > >::const_iterator iter =
l.begin();
iter != l.end(); ++iter)
{
temp.push_back(fmap(*iter,f));
}
return temp;
}

int lsize(list<int> l) //compute number of elements in a list
{
int size = 0;
for(list<int>::const_iterator i = l.begin(); i!= l.end(); ++i)
size++;
return size;


}

int inc(int x){ return x+1; }
char to_char(int x){ return 'A'+(char)x; }

template<class T> std:stream& operator<<(std:stream& 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()) << "]";
}

int main(int argc, char* argv[])
{
int tmp[] = {1,2,3};
list<int> simple_list(tmp,tmp+3);

list<list<int> > lol;
lol.push_back(simple_list);
lol.push_back(simple_list);

cout << "to_char of simple list: " << simple_list << " => "
<< fmap(simple_list,to_char) << endl;

cout << "lol = " << lol << endl
<< "lengths of lol's lists = " << fmap(lol,lsize) << endl;

cout << "to_char of lol: "<< lol << " => "
<< fmap(lol,to_char) << endl;

cout << " inc of lol: "<< lol << " => "
<< fmap(lol,inc) << endl;

list<list<list<int> > > lolol;
lolol.push_back(lol);

return 0;
}
you know std::list's declare is
template<class _Ty,
class _Ax = allocator<_Ty> >
class list;
so i add the Alloc to tell complier to deduce the params.
and i change to In to Container.
and
fmap<list<list>,list<list> >(lolol,inc)
....isn't proper syntax. My compiler (g++) complains...
because the function tell the complier wrong infors, so she can not
deduce the right params

so should add somethings likes:
template<typename L>
list<L> incL(list<L>);

cheers!