1
2
3
4
5
6
7 package main
8
9 import (
10 "fmt"
11 "runtime"
12 "time"
13 )
14
15 type Number struct {
16 next *Number
17 }
18
19
20
21
22 func zero() *Number { return nil }
23
24 func is_zero(x *Number) bool { return x == nil }
25
26 func add1(x *Number) *Number {
27 e := new(Number)
28 e.next = x
29 return e
30 }
31
32 func sub1(x *Number) *Number { return x.next }
33
34 func add(x, y *Number) *Number {
35 if is_zero(y) {
36 return x
37 }
38
39 return add(add1(x), sub1(y))
40 }
41
42 func mul(x, y *Number) *Number {
43 if is_zero(x) || is_zero(y) {
44 return zero()
45 }
46
47 return add(mul(x, sub1(y)), x)
48 }
49
50 func fact(n *Number) *Number {
51 if is_zero(n) {
52 return add1(zero())
53 }
54
55 return mul(fact(sub1(n)), n)
56 }
57
58
59
60
61 func gen(n int) *Number {
62 if n > 0 {
63 return add1(gen(n - 1))
64 }
65
66 return zero()
67 }
68
69 func count(x *Number) int {
70 if is_zero(x) {
71 return 0
72 }
73
74 return count(sub1(x)) + 1
75 }
76
77 func check(x *Number, expected int) {
78 var c = count(x)
79 if c != expected {
80 panic(fmt.Sprintf("error: found %d; expected %d", c, expected))
81 }
82 }
83
84
85
86
87 func verify() {
88 check(zero(), 0)
89 check(add1(zero()), 1)
90 check(gen(10), 10)
91
92 check(add(gen(3), zero()), 3)
93 check(add(zero(), gen(4)), 4)
94 check(add(gen(3), gen(4)), 7)
95
96 check(mul(zero(), zero()), 0)
97 check(mul(gen(3), zero()), 0)
98 check(mul(zero(), gen(4)), 0)
99 check(mul(gen(3), add1(zero())), 3)
100 check(mul(add1(zero()), gen(4)), 4)
101 check(mul(gen(3), gen(4)), 12)
102
103 check(fact(zero()), 1)
104 check(fact(add1(zero())), 1)
105 check(fact(gen(5)), 120)
106 }
107
108
109
110
111 func main() {
112 t0 := time.Now()
113 verify()
114 for i := 0; i <= 9; i++ {
115 print(i, "! = ", count(fact(gen(i))), "\n")
116 }
117 runtime.GC()
118 t1 := time.Now()
119
120 gcstats("BenchmarkPeano", 1, t1.Sub(t0))
121 }
122
View as plain text