This is just a little fun. Jason Hickey in "Introduction to Objective Caml" poses some little end of chapter problems to define arithmetic operations for a type of unary (base-1) natural numbers. The type is
type num = Z | S of numwhere
Z represents the number zero and if i is a unary number, then S i is i + 1.
This formulation of Church numerals using a recursive type and pattern matching means in truth, the problems can be solved in less than 5 minutes or so. Of course, the real Church numerals are numbers encoded in functions
- $c_{0} = \lambda s.\lambda z.\;z$
- $c_{1} = \lambda s.\lambda z.\;s\;z$
- $c_{2} = \lambda s.\lambda z.\;s\;(s\;z)$
- $c_{3} = \lambda s.\lambda z.\;s\;(s\;(s\;z))$
- $\cdots$
Alright, without further ado, here we go then.
type num = Z | S of num let scc (x : num) : num = S x let prd : num -> num = function | S n -> n | _ -> Z let rec add (x : num) (y : num) : num = match (x, y) with | (Z, _) -> y | (_, Z) -> x | (S m, n) -> scc (add m n) let rec sub (x : num) (y : num) : num = match (x, y) with | (Z, _) -> Z | (n, Z) -> n | (S m, n) -> sub m (prd n) let rec mul (x : num) (y : num) : num = match (x, y) with | (Z, _) -> Z | (_, Z) -> Z | (S Z, x) -> x | (x, S Z) -> x | (S m, n) -> add (mul m n) n let rec to_int : num -> int = function | Z -> 0 | S n -> 1 + to_int n let rec from_int (x : int) = if x = 0 then Z else scc (from_int (x - 1))For example, in the top-level we can write things like,
# to_int (mul (sub (from_int 23) (from_int 11)) (from_int 2));; - : int = 24
The main thing I find fun about this little program though is how obvious its mapping to C++. Of course you need a discriminated union type my default choice being boost::variant<> (by the way, standardization of a variant type for C++ is very much under active discussion and development, see N4450 for example from April this year - it seems that support for building recursive types might not be explicitly provided though... That would be a shame in my opinion and if that's the case, I beg the relevant parties to reconsider!).
#include <boost/variant.hpp>
#include <boost/variant/apply_visitor.hpp>
#include <stdexcept>
#include <iostream>
struct Z;
struct S;
typedef boost::variant<Z, boost::recursive_wrapper<S>> num;
struct Z {};
struct S { num i; };
int to_int (num const& i);
struct to_int_visitor
: boost::static_visitor<int> {
int operator ()(Z const& n) const { return 0; }
int operator ()(S const& n) const { return 1 + to_int (n.i); }
};
int to_int (num const& i) {
return boost::apply_visitor (to_int_visitor (), i);
}
num from_int (int i) {
if (i == 0){
return Z {};
}
else{
return S {from_int (i - 1)};
}
}
num add (num l, num r);
struct add_visitor : boost::static_visitor<num> {
num operator () (Z, S s) const { return s; }
num operator () (S s, Z) const { return s; }
num operator () (Z, Z) const { return Z {}; }
num operator () (S s, S t) const { return S { add (s.i, t) }; }
};
num add (num l, num r) {
return boost::apply_visitor (add_visitor (), l, r);
}
num succ (num x) { return S{x}; }
struct prd_visitor : boost::static_visitor<num>{
num operator () (Z z) const { return z; }
num operator () (S s) const { return s.i; }
};
num prd (num x) {
return boost::apply_visitor(prd_visitor (), x);
}
num sub (num x, num y);
struct sub_visitor : boost::static_visitor<num> {
num operator () (Z, Z) const { return Z {}; }
num operator () (Z, S) const { return Z {}; }
num operator () (S m, Z) const { return m; }
num operator () (S m, S n) const { return sub (m.i, prd (n)); }
};
num sub (num x, num y) {
return boost::apply_visitor (sub_visitor (), x, y);
}
//Tests
int main () {
num zero = Z {};
num one = succ (zero);
num two = succ (succ (zero));
num three = succ (succ (succ (zero)));
std::cout << to_int (add (two, three)) << std::endl;
std::cout << to_int (sub (from_int (23), from_int (12))) << std::endl;
return 0;
}
I didn't get around to implementing mul in the above. Consider it an "exercise for the reader"!
