Church numerals: Difference between revisions

Content added Content deleted
(→‎{{header|C++}}: Add subtraction and division)
(→‎{{header|C++}}: tweeks; clean-up)
Line 263: Line 263:


// apply the function zero times (return an identity function)
// apply the function zero times (return an identity function)
auto Zero() {
auto Zero = [](auto){ return [](auto x){ return x; }; };

⚫
return [](auto) {
// define Church True and False
return [=](auto x) {return x;};
auto True = [](auto a){ return [=](auto){ return a; }; };
};
auto False = [](auto){ return [](auto b){ return b; }; };
⚫
}


// apply the function f one more time
// apply the function f one more time
Line 297: Line 297:
auto Exp(auto a, auto b) {
auto Exp(auto a, auto b) {
return b(a);
return b(a);
⚫
}

// check if a number is zero
auto IsZero(auto a){
⚫
return a([](auto){ return False; })(True);
}
}


Line 309: Line 314:
};
};
}
}
)([=](auto) {return x;})([](auto y){return y;});
)([=](auto){ return x; })([](auto y){ return y; });
};
};
};
};
Line 317: Line 322:
auto Subtract(auto a, auto b) {
auto Subtract(auto a, auto b) {
{
{
auto a_minus_b = b([](auto c){ return Predecessor(c);})(a);
return b([](auto c){ return Predecessor(c); })(a);

// Each lambda has its own type which gives '3-1' a different
// type than '4-2'. Normalize the number based on successors to 0.
return a_minus_b([=](auto f) {return Successor(f);})(Zero());
};
};
}
}
Line 327: Line 328:
namespace
namespace
{
{
// helper functions for division. These funtions are only
// helper functions for division.
// visible in this source file


// end the recusrion
// end the recusrion
auto Divr(decltype(Zero()), auto) {
auto Divr(decltype(Zero), auto) {
return Zero();
return Zero;
}
}


// count how many times b can be subtracted from a
// count how many times b can be subtracted from a
auto Divr(auto a, auto b) {
auto Divr(auto a, auto b) {
return Successor(Divr(Subtract(a, b), b));
auto a_minus_b = Subtract(a, b);
auto isZero = IsZero(a_minus_b);

// normalize all Church zeros to be the same (intensional equality).
// In this implemetation, Church numerals have extensional equality
// but not intensional equality. '6 - 3' and '4 - 1' have extensional
// equality because they will both cause a function to be called
// three times but due to the static type system they do not have
// intensional equality. Internally the two numerals are represented
// by different lambdas. Normalize all Church zeros (1 - 1, 2 - 2, etc.)
// to the same zero (Zero) so it will match the function that end the
// recursion.
return isZero
(Zero)
(Successor(Divr(isZero(Zero)(a_minus_b), b)));
}
}
}
}
Line 343: Line 357:
// apply the function a / b times
// apply the function a / b times
auto Divide(auto a, auto b) {
auto Divide(auto a, auto b) {
return Divr(Subtract(Successor(a), b), b);
return Divr(Successor(a), b);
}
}


// create a Church numeral from an integer at compile time
// create a Church numeral from an integer at compile time
template <int N> constexpr auto ToChurch() {
template <int N> constexpr auto ToChurch() {
if constexpr(N<=0) return Zero();
if constexpr(N<=0) return Zero;
else return Successor(ToChurch<N-1>());
else return Successor(ToChurch<N-1>());
}
}
Line 354: Line 368:
// use an increment function to convert the Church number to an integer
// use an increment function to convert the Church number to an integer
int ToInt(auto church) {
int ToInt(auto church) {
return church([](int n){return n + 1;})(0);
return church([](int n){ return n + 1; })(0);
}
}


int main() {
int main() {
// show some examples
// show some examples
auto zero = Zero();
auto zero = Zero;
auto three = Successor(Successor(Successor(zero)));
auto three = Successor(Successor(Successor(zero)));
auto four = Successor(three);
auto four = Successor(three);
auto six = ToChurch<6>();
auto six = ToChurch<6>();
auto nine = ToChurch<9>();
auto ten = ToChurch<10>();
auto ten = Successor(nine);
auto thousand = Exp(ten, three);


std::cout << "\n 3 + 4 = " << ToInt(Add(three, four));
std::cout << "\n 3 + 4 = " << ToInt(Add(three, four));
⚫
std::cout << "\n 4 + 3 = " << ToInt(Add(four, three));
std::cout << "\n 3 * 4 = " << ToInt(Multiply(three, four));
std::cout << "\n 3 * 4 = " << ToInt(Multiply(three, four));
std::cout << "\n 4 * 3 = " << ToInt(Multiply(four, three));
std::cout << "\n 3^4 = " << ToInt(Exp(three, four));
std::cout << "\n 3^4 = " << ToInt(Exp(three, four));
std::cout << "\n 4^3 = " << ToInt(Exp(four, three));
std::cout << "\n 4^3 = " << ToInt(Exp(four, three));
std::cout << "\n 0^0 = " << ToInt(Exp(zero, zero));
std::cout << "\n 0^0 = " << ToInt(Exp(zero, zero));
std::cout << "\n 9 - 6 = " << ToInt(Subtract(nine, six));
std::cout << "\n 4 - 3 = " << ToInt(Subtract(four, three));
std::cout << "\n 9 - 9 = " << ToInt(Subtract(nine, nine));
std::cout << "\n 3 - 4 = " << ToInt(Subtract(three, four));
std::cout << "\n 6 / 3 = " << ToInt(Divide(six, three));
std::cout << "\n 6 / 3 = " << ToInt(Divide(six, three));
std::cout << "\n 3 / 6 = " << ToInt(Divide(three, six));
std::cout << "\n 3 / 6 = " << ToInt(Divide(three, six));
auto looloolooo = Add(Exp(ten, nine), Add(Exp(ten, six), Exp(ten, three)));
auto looloolooo = Add(Exp(thousand, three), Add(Exp(ten, six), thousand));
auto looloolool = Successor(looloolooo);
auto looloolool = Successor(looloolooo);
std::cout << "\n 10^9 + 10^6 + 10^3 + 1 = " << ToInt(looloolool) << "\n";
std::cout << "\n 10^9 + 10^6 + 10^3 + 1 = " << ToInt(looloolool);

// calculate the golden ratio by using a Church numeral to
// apply the funtion '1 + 1/x' a thousand times
⚫
std::cout << "\n golden ratio = " <<
thousand([](double x){ return 1.0 + 1.0 / x; })(1.0) << "\n";
}</syntaxhighlight>
}</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
3 + 4 = 7
3 + 4 = 7
4 + 3 = 7
3 * 4 = 12
3 * 4 = 12
4 * 3 = 12
3^4 = 81
3^4 = 81
4^3 = 64
4^3 = 64
0^0 = 1
0^0 = 1
9 - 6 = 3
4 - 3 = 1
9 - 9 = 0
3 - 4 = 0
6 / 3 = 2
6 / 3 = 2
3 / 6 = 0
3 / 6 = 0
10^9 + 10^6 + 10^3 + 1 = 1001001001
10^9 + 10^6 + 10^3 + 1 = 1001001001
golden ratio = 1.61803
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Church_numerals"