Fixpoint operátor v C++

[desprit]

Jak se dá nejlépe implementovat Fix v C++? V Haskellu to je prostě f(Fix f), ale to vyžaduje líné vyhodnocování a typové proměnné.

[Reklama]

[Sten]

Obecně velmi obtížně. Ale třeba pro hledání fixed point ≥ 0 funkce constexpr int(int) lze napsat něco takového:

Kód: [Vybrat]

template <int(*func)(int),
          int point,
          bool fixed>
struct find_fix;

// point není fixed, zkusí point + 1
template <int(*func)(int),
          int point>
struct find_fix<func, point, false>
    : find_fix<func, point + 1, point + 1 == func(point + 1)>
{};

// point je fixed
template <int(*func)(int),
          int point>
struct find_fix<func, point, true>

{
    static constexpr int value = point;
};

template <int(*func)(int)>
int fix()
{
    return find_fix<func, 0, func(0) == 0>::value;
}

// Zkouška, fixed point je 42:
constexpr int test(int i)
{
return i != 42 ? i + 1 : i;
}

int main()
{
std::cout << fix<test>() << std::endl;
}


[Aoidhghean]

Obecně velmi obtížně. Ale třeba pro hledání fixed point ≥ 0 funkce constexpr int(int) lze napsat něco takového:

Kód: [Vybrat]

template <int(*func)(int),
          int point,
          bool fixed>
struct find_fix;

// point není fixed, zkusí point + 1
template <int(*func)(int),
          int point>
struct find_fix<func, point, false>
    : find_fix<func, point + 1, point + 1 == func(point + 1)>
{};

// point je fixed
template <int(*func)(int),
          int point>
struct find_fix<func, point, true>

{
    static constexpr int value = point;
};

template <int(*func)(int)>
int fix()
{
    return find_fix<func, 0, func(0) == 0>::value;
}

// Zkouška, fixed point je 42:
constexpr int test(int i)
{
return i != 42 ? i + 1 : i;
}

int main()
{
std::cout << fix<test>() << std::endl;
}


Tady jde zjevně o pevné body jsoucí funkcemi.

[Aoidhghean]

Jde to snadno. Něco jako

Kód: [Vybrat]

template<typename T> class Fix {
std::function<T(const std::function<T(T)>&,T)> f;
T operator()(T x) { return f(*this, x); }
}
Funkční objekt bude volat sám sebe, čímž se zajistí ten pevný bod. Haskell to má stejně, jen dvacetkrát kratší.

[Aoidhghean]

Jinak v C++ se dá taky implementovat pevný bod pro algebraické datové typy, ale syntax vypadá dost děsně.

[Reklama]