Комбинаторы с фиксированной точкой в ​​C ++ - PullRequest
Новая
       10

Комбинаторы с фиксированной точкой в ​​C ++

7 голосов
/ 30 сентября 2008

Меня интересуют реальные примеры использования комбинаторов с фиксированной точкой (таких как y-комбинатор в C ++. Вы когда-нибудь использовали комбинатор с фиксированной точкой с egg или bind в реальном живом коде?

Я нашел этот пример в яйце немного плотным: 

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);
}

Можете ли вы объяснить, как это все работает?

Есть ли хороший простой пример, возможно, использующий связывание с возможно меньшим количеством зависимостей, чем этот?

Ответы [ 3 ]

30 голосов
/ 30 сентября 2008

Здесь тот же код, преобразованный в boost::bind, обратите внимание на y-комбинатор и его сайт приложения в основной функции. Надеюсь, это поможет. 

#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;
}
8 голосов
/ 15 августа 2012 
#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;
}
3 голосов
/ 30 сентября 2008

Можете ли вы объяснить, как все это работает?

fix2 - это y-комбинатор (в частности, это комбинатор для функций с двумя аргументами; первый аргумент - это функция (с целью рекурсии), второй аргумент - «правильный» аргумент функции). Создает рекурсивные функции.

bll :: ret (...), кажется, создает некоторую форму функционального объекта, тело которого является 

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

Предполагается, что «ленивый» останавливает бесконечное расширение первого (функционального) аргумента (читайте о разнице между ленивыми и строгими y-комбинаторами, чтобы понять почему).

Код довольно ужасный. Приятно иметь анонимные функции, но из-за отсутствия синтаксической поддержки в C ++ они не стоят усилий.

...