12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788 |
- // Peano integers are represented by a linked
- // list whose nodes contain no data
- // (the nodes are the data).
- // http://en.wikipedia.org/wiki/Peano_axioms
- // This program demonstrates that Go's automatic
- // stack management can handle heavily recursive
- // computations.
- package main
- import "fmt"
- // Number is a pointer to a Number
- type Number *Number
- // The arithmetic value of a Number is the
- // count of the nodes comprising the list.
- // (See the count function below.)
- // -------------------------------------
- // Peano primitives
- func zero() *Number {
- return nil
- }
- func isZero(x *Number) bool {
- return x == nil
- }
- func add1(x *Number) *Number {
- e := new(Number)
- *e = x
- return e
- }
- func sub1(x *Number) *Number {
- return *x
- }
- func add(x, y *Number) *Number {
- if isZero(y) {
- return x
- }
- return add(add1(x), sub1(y))
- }
- func mul(x, y *Number) *Number {
- if isZero(x) || isZero(y) {
- return zero()
- }
- return add(mul(x, sub1(y)), x)
- }
- func fact(n *Number) *Number {
- if isZero(n) {
- return add1(zero())
- }
- return mul(fact(sub1(n)), n)
- }
- // -------------------------------------
- // Helpers to generate/count Peano integers
- func gen(n int) *Number {
- if n > 0 {
- return add1(gen(n - 1))
- }
- return zero()
- }
- func count(x *Number) int {
- if isZero(x) {
- return 0
- }
- return count(sub1(x)) + 1
- }
- // -------------------------------------
- // Print i! for i in [0,9]
- func main() {
- for i := 0; i <= 9; i++ {
- f := count(fact(gen(i)))
- fmt.Println(i, "! =", f)
- }
- }
|