How can I solve SICP 2.4 in C++11

Question

This exercise ask for implement cons, car and cdr functions using only lambda functions.

The function cons(a,b) create a list of a followed by b, car(l) returns the first element of list l, and cdr(l) returns the rest of the list.

I got it working with lists of only two elements, but when you try to cons more elements it fails. Any Ideas?

#include <iostream>
#include <functional>

template<typename A>
A car( std::function< A(std::function<A(A,A)>) > m ){
    return m( [](A a, A){ return a; } );
}

template<typename A>
A cdr( std::function< A(std::function<A(A,A)>) > m ){
    return m( [](A, A b){ return b; } );
}

template<typename A>
std::function< A(std::function<A(A,A)>) >
cons( const A a, const A b){
    return [=](std::function<A(A,A)> l){ return l(a,b); };
}

int main(){
    //auto l = cons( cons( 1, 2 ), 3 );  // no matching function
    auto l = cons( 1, 2 );

    std::cout << car( l ) << ", " << cdr( l ) << std::endl;

    return 0;
}

UPDATE

I notice that the real signature of cons should be:

template<typename A,typename B, typename C>
std::function< C(std::function<C(A,B)>) >
cons( const A a, const B b){
    return [=](std::function<C(A,B)> l){ return l(a,b); };
}

Because this version also didn't work.

UPDATE 2 It can be simplified (more readable) with:

template<typename A, typename B, typename C>
using Cell<A,B,C> = std::function<C(A,B)>

Answer 1

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.