cons
from your example could not be compiled, because compiler is unable to deduce return type for lambda function. What you are looking for specifically is polymorphic lambda function. Unfortunately C++11 doesn't support polymorphic lambdas, but there are several ways to implement cons
, car
and cdr
in C++ anyway.
The first (and possibly the most straightforward) way to implement cons
, car
and cdr
is using std::tuple
or std::pair
. This implementation is almost similar to definitions in chapter 2.1.3 of the book.
#include <iostream>
#include <tuple>
template<typename A, typename B>
A car( std::tuple<A, B> m ) {
return std::get<0>(m);
}
template<typename A, typename B>
B car( std::tuple<A, B> m ) {
return std::get<1>(m);
}
template<typename A, typename B>
std::tuple<A, B>
cons(const A a, const B b) {
return std::tuple<A, B>(a, b);
}
int main() {
auto l = cons(cons(1, 2), 3);
std::cout << car(car(l)) << ", " << cdr(car(l)) << ", ";
std::cout << cdr(l) << std::endl;
return 0;
}
But this implementation is not following original idea of exercise 2.4. To follow it we could simply create our own pair
class and implement operator()
method parametrized by lambda return type.
#include <iostream>
#include <functional>
template<typename A, typename B>
class pair {
A _a;
B _b;
public:
pair(const A a, const B b): _a(a), _b(b) {}
template<typename R>
R operator()(std::function<R(A, B)> func) {
return func(_a, _b);
}
};
And then we could implement cons
, car
and cdr
just using it:
template<typename A, typename B>
A car(pair<A, B> p) {
return p( std::function<A(A, B)> ( [](A a, B) { return a; } ) );
}
template<typename A, typename B>
B cdr(pair<A, B> p) {
return p( std::function<B(A, B)> ( [](A, B b) { return b; } ) );
}
template<typename A, typename B>
pair<A, B>
cons(const A a, const B b) {
return pair<A, B>(a, b);
}
int main() {
auto p = cons(cons("a", 2), 3);
std::cout << car(car(p)) << ", " << cdr(car(p)) << ", ";
std::cout << cdr(p) << std::endl;
return 0;
}
As far as I understand, C++14 (provisionally named C++1y) will introduce some features like generic lambdas which might simplify implementation.
UPDATE
After reading proposal for generic (polymorphic) lambda expressions in C++14, I've come to the following working implementation:
#include <iostream>
auto car = [](auto func) { return func( [](auto a, auto b) { return a; } ); };
auto cdr = [](auto func) { return func( [](auto a, auto b) { return b; } ); };
auto cons = [](auto a, auto b) { return [=](auto func) { return func(a, b); }; };
int main() {
auto p = cons( cons("a", 2), 3 );
std::cout << car(car(p)) << ", " << cdr(car(p)) << ", ";
std::cout << cdr(p) << std::endl;
return 0;
}
Please note, that it will only work with compiler implementing such proposal (e.g. GCC 4.8, Clang 3.4) using -std=c++1y
flag.