1 // Peano integers are represented by a linked 2 // list whose nodes contain no data 3 // (the nodes are the data). 4 // http://en.wikipedia.org/wiki/Peano_axioms 5 6 // This program demonstrates that Go's automatic 7 // stack management can handle heavily recursive 8 // computations. 9 10 package main 11 12 import "fmt" 13 14 // Number is a pointer to a Number 15 type Number *Number 16 17 // The arithmetic value of a Number is the 18 // count of the nodes comprising the list. 19 // (See the count function below.) 20 21 // ------------------------------------- 22 // Peano primitives 23 24 func zero() *Number { 25 return nil 26 } 27 28 func isZero(x *Number) bool { 29 return x == nil 30 } 31 32 func add1(x *Number) *Number { 33 e := new(Number) 34 *e = x 35 return e 36 } 37 38 func sub1(x *Number) *Number { 39 return *x 40 } 41 42 func add(x, y *Number) *Number { 43 if isZero(y) { 44 return x 45 } 46 return add(add1(x), sub1(y)) 47 } 48 49 func mul(x, y *Number) *Number { 50 if isZero(x) || isZero(y) { 51 return zero() 52 } 53 return add(mul(x, sub1(y)), x) 54 } 55 56 func fact(n *Number) *Number { 57 if isZero(n) { 58 return add1(zero()) 59 } 60 return mul(fact(sub1(n)), n) 61 } 62 63 // ------------------------------------- 64 // Helpers to generate/count Peano integers 65 66 func gen(n int) *Number { 67 if n > 0 { 68 return add1(gen(n - 1)) 69 } 70 return zero() 71 } 72 73 func count(x *Number) int { 74 if isZero(x) { 75 return 0 76 } 77 return count(sub1(x)) + 1 78 } 79 80 // ------------------------------------- 81 // Print i! for i in [0,9] 82 83 func main() { 84 for i := 0; i <= 9; i++ { 85 f := count(fact(gen(i))) 86 fmt.Println(i, "! =", f) 87 } 88 } 89
