mapcar contest

[jacob navia]

Hi

I am writing a container library in C. I have developed iterators, and
generic containers, and to test my library I wrote the lisp function
"mapcar".

Mapcar takes a list and builds a list containing the result of a monadic
function applied to each element of the input list.

For instance

(mapcar #'abs (1 -2 3 -4 5 -6 7))

will produce

(1 2 3 4 5 6 7)

i.e. the function 'abs' will be applied to each element.

Within my software, mapcar looks like this:

int mapcar(SequentialContainer *src, /* The source container */
void *(*fn)(void *),/* Function to call with each element */
SequentialContainer *result) /* The resulting container */
{
Iterator *it = iSequentialContainer.newIterator(src);
int r=1;
void *obj;
if (it == NULL)
return CONTAINER_ERROR_NOMEMORY;
for (obj = it->GetFirst(it);
obj != NULL;
obj = it->GetNext(it)) {
void *tmp = fn(obj);
int r = iSequentialContainer.Add(result,tmp);
if (r < 0) {
/* In case of any error return a partial result
and the error code */
break;
}
}
deleteIterator(it);
return r;
}

"SequentialContainer" is an abstract class that includes lists, arrays,
stringcollections, and all containers that have a natural sequence
(index) that follows the natural integers. The result of "mapcar" then,
will be of the same actual type that the "result" container passed to
mapcar.

Now (at last) my question:

What would be the corresponding C++ code?
What would be the best way of implementing it?

Thanks in advance to all C++ wizards that take this challenge.

jacob

 

[Ian Collins]

Hi

I am writing a container library in C. I have developed iterators, and
generic containers, and to test my library I wrote the lisp function
"mapcar".

Mapcar takes a list and builds a list containing the result of a monadic
function applied to each element of the input list.

For instance

(mapcar #'abs (1 -2 3 -4 5 -6 7))

will produce

(1 2 3 4 5 6 7)

i.e. the function 'abs' will be applied to each element.

Within my software, mapcar looks like this:

int mapcar(SequentialContainer *src, /* The source container */
void *(*fn)(void *),/* Function to call with each element */
SequentialContainer *result) /* The resulting container */

"SequentialContainer" is an abstract class that includes lists, arrays,
stringcollections, and all containers that have a natural sequence
(index) that follows the natural integers. The result of "mapcar" then,
will be of the same actual type that the "result" container passed to
mapcar.

Now (at last) my question:

What would be the corresponding C++ code?

The idiomatic solution is probably to use std::transform:

int main()
{
int data[] = {1, -2, 3, -4, 5, -6, 7};

std::vector<int> vi(data, data+sizeof(data)/sizeof(int));

std::list<int> li;
std::list<int>::iterator it(li.begin());
std::insert_iterator< std::list<int> > insert(li,it);

std::transform( vi.begin(), vi.end(), insert, abs );

return 0;
}

What would be the best way of implementing it?

If you don't want to use iterators and you want to use generic in and
out containers, something like:

template <typename T,
template <typename X,typename A=std::allocator<X> > class In,
template <typename X,typename A=std::allocator<X> > class Out,
typename Op>
void mapcar( const In<T>& in, Out<T>& out, Op op )
{
typename Out<T>::iterator it(out.begin());

std::insert_iterator< Out<T> > insert(out,it);

std::transform( in.begin(), in.end(), insert, abs );
}

Which would be called as

std::vector<int> vi;
std::list<int> li;

mapcar( vi, li, abs );

 

[Juha Nieminen]

template <typename T,
template <typename X,typename A=std::allocator<X> > class In,
template <typename X,typename A=std::allocator<X> > class Out,
typename Op>
void mapcar( const In<T>& in, Out<T>& out, Op op )
{
typename Out<T>::iterator it(out.begin());

std::insert_iterator< Out<T> > insert(out,it);

std::transform( in.begin(), in.end(), insert, abs );
}

That way of doing it is more "type-safe" in the sense that you will get
more sensical error message in case the parameters are of the wrong type
(although that's debatable, as usually you will only get a very confusing
error of type "mapcar was not declared in this score"). However, it's not
strictly necessary to do it that complicated. This achieves the same thing
with less code:

template<typename In, typename Out, typename Op>
void mapcar(const In& in, Out& out, Op op)
{
std::insert_iterator<Out> insert(out, out.begin());
std::transform(in.begin(), in.end(), insert, op);
}

(If you need the element type for some reason, you can always use
In::value_type and Out::value_type.)

 

[Ian Collins]

That way of doing it is more "type-safe" in the sense that you will get
more sensical error message in case the parameters are of the wrong type
(although that's debatable, as usually you will only get a very confusing
error of type "mapcar was not declared in this score"). However, it's not
strictly necessary to do it that complicated. This achieves the same thing
with less code:

template<typename In, typename Out, typename Op>
void mapcar(const In& in, Out& out, Op op)
{
std::insert_iterator<Out> insert(out, out.begin());
std::transform(in.begin(), in.end(), insert, op);
}

Indeed it does, but I needed a refresher on template template parameters!

The advantage of the iterator approach I didn't mention is it can be
used on raw arrays as well as containers.

 

[jacob navia]

Thanks for your help.

I wrote this small program as you suggested:

#include <vector>
#include <algorithm>
#include <list>

using namespace std;

int main()
{
int data[] = {1, -2, 3, -4, 5, -6, 7};

std::vector<int> vi(data, data+sizeof(data)/sizeof(int));

std::list<int> li;
std::list<int>::iterator it(li.begin());
std::insert_iterator< std::list<int> > insert(li,it);

std::transform( vi.begin(), vi.end(), insert, abs );

return 0;
}



The compiler tells me:

/tmp $ g++ mapcar2.cpp
mapcar2.cpp: In function ‘int main()’:
mapcar2.cpp:17: error: no matching function for call to
‘transform(__gnu_cxx::__normal_iterator<int*, std::vector<int,
std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*,
std::vector<int, std::allocator<int> > >,
std::insert_iterator<std::list<int, std::allocator<int> > >&,
<unresolved overloaded function type>)’
/tmp $


I am sorry but I can't decipher that. What is wrong?

Thanks in advance and excuse my ignorance.

jacob

 

[Ian Collins]

Thanks for your help.

I wrote this small program as you suggested:

#include <vector>
#include <algorithm>
#include <list>

using namespace std;

int main()
{
int data[] = {1, -2, 3, -4, 5, -6, 7};

std::vector<int> vi(data, data+sizeof(data)/sizeof(int));

std::list<int> li;
std::list<int>::iterator it(li.begin());
std::insert_iterator< std::list<int> > insert(li,it);

std::transform( vi.begin(), vi.end(), insert, abs );

return 0;
}



The compiler tells me:

/tmp $ g++ mapcar2.cpp
mapcar2.cpp: In function ‘int main()’:
mapcar2.cpp:17: error: no matching function for call to
‘transform(__gnu_cxx::__normal_iterator<int*, std::vector<int,
std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*,
std::vector<int, std::allocator<int> > >,
std::insert_iterator<std::list<int, std::allocator<int> > >&,
<unresolved overloaded function type>)’

"<unresolved overloaded function type>" is probably telling you you
haven't declared abs (<stdlib.h> missing).

 

[Balog Pal]

"<unresolved overloaded function type>" is probably telling you you
haven't declared abs (<stdlib.h> missing).

Or in other cases it means exactly what it says, the function you want to
pass is an overload set, and it can nt decide which member to use.

C++ just sucks here, as all the cures I'm aware are worse than the medicine.

 

[jacob navia]

Le 07/11/10 09:46, Ian Collins a écrit :

Thanks for your help.

I wrote this small program as you suggested:

#include <vector>
#include <algorithm>
#include <list>

using namespace std;

int main()
{
int data[] = {1, -2, 3, -4, 5, -6, 7};

std::vector<int> vi(data, data+sizeof(data)/sizeof(int));

std::list<int> li;
std::list<int>::iterator it(li.begin());
std::insert_iterator< std::list<int> > insert(li,it);

std::transform( vi.begin(), vi.end(), insert, abs );

return 0;
}



The compiler tells me:

/tmp $ g++ mapcar2.cpp
mapcar2.cpp: In function ‘int main()’:
mapcar2.cpp:17: error: no matching function for call to
‘transform(__gnu_cxx::__normal_iterator<int*, std::vector<int,
std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*,
std::vector<int, std::allocator<int> > >,
std::insert_iterator<std::list<int, std::allocator<int> > >&,
<unresolved overloaded function type>)’

"<unresolved overloaded function type>" is probably telling you you
haven't declared abs (<stdlib.h> missing).

No, I included <stdlib.h> but the result was the same.
I resolved it by writing

int myabs(int n)
{
if (n < 0) n = -n;
return n;
}

and passing "myabs" instead of "abs" This worked. The whole program
looks like this:

#include <iostream>
#include <vector>
#include <algorithm>
#include <list>
#include <stdlib.h>
int myabs(int n)
{
if (n < 0) n = -n;
return n;
}

using namespace std;

int main()
{
int data[] = {1, -2, 3, -4, 5, -6, 7};

std::vector<int> vi(data, data+sizeof(data)/sizeof(int));

std::list<int> li;
std::list<int>::iterator it(li.begin());
std::insert_iterator< std::list<int> > insert(li,it);

std::transform( vi.begin(), vi.end(), insert, myabs );

cout << "contains:";
for (it=li.begin(); it!=li.end(); ++it)
cout << " " << *it;

cout << endl;

return 0;
}

Thanks for your code (and patience).

 

[Ian Collins]

Le 07/11/10 09:46, Ian Collins a écrit :

No, I included <stdlib.h> but the result was the same.
I resolved it by writing

Does your system declare abs as a macro? Does

std::transform( vi.begin(), vi.end(), insert, (abs) );

fix it?

 

[Balog Pal]

Does your system declare abs as a macro? Does

std::transform( vi.begin(), vi.end(), insert, (abs) );

fix it?

How would it?

abs is a 3 function overload set:

float abs(float);
double abs(double);
long double abs(long double);

if you have a
template <typename T>
void foo( T t);

and call
foo(abs)

what you expect to be deduced as T and passed in the function?

The only infix workarounds I know are to use an insane static_cast<> on the
function, or to call the template with the type explicitly provided in <>,
what most times defeats the very purpose to use the function template.
(think std::make_pair).

If you can you rather twist the code, createing a non-overload wrapper for
the wanted function, or avoid overloading -- the latter is limited to code
you're in control and other restrictions, as with constructiors you're still
out of luck.

 

[Juha Nieminen]

Or in other cases it means exactly what it says, the function you want to
pass is an overload set, and it can nt decide which member to use.

C++ just sucks here, as all the cures I'm aware are worse than the medicine.

I wouldn't be so dramatic. All you need is to write your own operator
function which is unambiguous and does what you want, eg:

int myOperatorFunction(int param) { return abs(param); }

Then use that for the parameter to std::transform.

Yes, it's a bummer to have to write that line, but C++0x will alleviate
it a bit with lambdas.

 

[Ian Collins]

How would it?

abs is a 3 function overload set:

float abs(float);
double abs(double);
long double abs(long double);

According to the C standard, the signature for abs() is "int abs(int)".
C++ adds "long abs(long)".

On my system (OpenSolaris) g++ finds the correct overload, which is why
I posted the code I did.

 

[jacob navia]

Le 07/11/10 19:39, Ian Collins a écrit :

According to the C standard, the signature for abs() is "int abs(int)".
C++ adds "long abs(long)".

On my system (OpenSolaris) g++ finds the correct overload, which is why
I posted the code I did.

In mine, I have

int abs(int) __attribute__((__const__));
inline long abs(long __i) { return labs(__i); }
inline long long abs(long long __x) { return __x >= 0 ? __x : -__x; }

/tmp $ uname -a
Darwin Mac-Pro-de-jacob-navia.local 10.4.0 Darwin Kernel Version 10.4.0:
Fri Apr 23 18:28:53 PDT 2010; root:xnu-1504.7.4~1/RELEASE_I386 i386
/tmp $

It is OK Ian, with your hint that "abs" could be the culprit I solved
the problem.

jacob

 

[Balog Pal]

According to the C standard, the signature for abs() is "int abs(int)".
C++ adds "long abs(long)".

On my system (OpenSolaris) g++ finds the correct overload, which is why
I posted the code I did.

DOH, mis-thought for fabs()...

 

[Ian Collins]

DOH, mis-thought for fabs()...

My guess (now confirmed) was a "bug" in Jacob's system headers. The
overloads shouldn't be in the global namespace, or even in the C header
at all. If I change my code to include <cstdlib> and write

std::transform( vi.begin(), vi.end(), insert, std::abs );

I get the same unresolved overloaded error from g++.