combinadores punto fijo en C++

Question

estoy interesado en ejemplos reales de uso de combinadores de punto fijo (como el y-combinator en C++. ¿Ha usado un combinador de punto fijo con egg o bind en el código de carne y hueso?

I encontrado este ejemplo en huevo un poco densa:??

void egg_example() 
{ 
    using bll::_1; 
    using bll::_2; 

    int r = 
     fix2(
      bll::ret<int>(
       // \(f,a) -> a == 0 ? 1 : a * f(a-1) 
       bll::if_then_else_return(_2 == 0, 
        1, 
        _2 * lazy(_1)(_2 - 1) 
       ) 
      ) 
     ) (5); 

    BOOST_CHECK(r == 5*4*3*2*1); 
} 

Puede explicar cómo funciona todo esto

¿hay un ejemplo simple agradable quizás usando bind tal vez con un menor número de dependencias que éste

Answer 1

Aquí está el mismo código convertido en boost::bind observe el y-combinator y su sitio de aplicación en la función principal. Espero que esto ayude.

#include <boost/function.hpp> 
#include <boost/bind.hpp> 
#include <iostream> 

// Y-combinator compatible factorial 
int fact(boost::function<int(int)> f,int v) 
{ 
    if(v == 0) 
    return 1; 
    else 
    return v * f(v -1); 
} 

// Y-combinator for the int type 
boost::function<int(int)> 
    y(boost::function<int(boost::function<int(int)>,int)> f) 
{ 
    return boost::bind(f,boost::bind(&y,f),_1); 
} 


int main(int argc,char** argv) 
{ 
    boost::function<int(int)> factorial = y(fact); 
    std::cout << factorial(5) << std::endl; 
    return 0; 
} 

Answer 2

Puede explicar cómo funciona todo esto?

Fix2 es una y-combinador (específicamente, es un combinador para funciones con dos argumentos; el primer argumento es la función (a los efectos de la recursión), el segundo argumento es un argumento de la función "adecuado") . Crea funciones recursivas.

BLL :: ret (...) parece crear alguna forma de un objeto función, cuyo cuerpo es

if(second arg == 0) 
{ 
    return 1; 
} 
else 
{ 
    return second arg * first arg(second arg - 1); 
} 

El "perezosa" es de suponer que para detener la expansión infinita de la primera (función) argumento (lee la diferencia entre los combinadores perezosos y estrictos y para ver por qué).

El código es bastante horrible. Es bueno tener funciones anónimas, pero el hackery para evitar la falta de soporte sintáctico de C++ hace que no valga la pena el esfuerzo.

Answer 3

#include <functional> 
#include <iostream> 

template <typename Lamba, typename Type> 
auto y (std::function<Type(Lamba, Type)> f) -> std::function<Type(Type)> 
{ 
    return std::bind(f, std::bind(&y<Lamba, Type>, f), std::placeholders::_1); 
} 

int main(int argc,char** argv) 
{ 
    std::cout << y < std::function<int(int)>, int> ([](std::function<int(int)> f, int x) { 
     return x == 0 ? 1 : x * f(x - 1); 
    }) (5) << std::endl; 
    return 0; 
}