/*
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::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);
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::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()) << "]";
}
