Fixpunkt-Kombinator in C ++

Question

Ich habe Interesse an konkreten Beispielen von festen Punkt combinators (zB y-combinator in C ++. Haben Sie schon einmal verwendet, um einen festen Punkt combinator mit Ei oder

War es hilfreich?

einreichen

Lösung

Hier ist der gleiche Code in boost::bind Bekanntmachung den y-combinator und seine Applikationsstelle in der Hauptfunktion umgewandelt. Ich hoffe, das hilft.

#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 1

Hier ist der gleiche Code in boost::bind Bekanntmachung den y-combinator und seine Applikationsstelle in der Hauptfunktion umgewandelt. Ich hoffe, das hilft.

#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

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

Answer 3

  

Können Sie erklären, wie das alles funktioniert?

fix2 ist ein y-Kombinator (genauer gesagt, es ist ein Kombinator für Funktionen mit zwei Argumenten, das erste Argument die Funktion ist (zum Zweck der Rekursion), das zweite Argument ist ein „richtiges“ Funktionsargument). Es schafft rekursive Funktionen.

BLL :: ret (...) erscheint eine Form eines Funktionsobjekt zu schaffen, deren Körper ist

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

Die „faul“ ist vermutlich eine unendliche Ausdehnung des ersten (Funktion) Argument zu stoppen (lesen Sie auf den Unterschied zwischen faul und strengen Y Combinator, um zu sehen, warum).

Der Code ist ziemlich schrecklich. Anonyme Funktionen sind nett zu haben, aber die hackery um C ++ 's Mangel an syntaktischer Unterstützung machen sie nicht die Mühe wert, zu arbeiten.