OLD | NEW |
1 // $G $F.go && $L $F.$A && ./$A.out | 1 // $G $F.go && $L $F.$A && ./$A.out |
2 | 2 |
3 // Copyright 2009 The Go Authors. All rights reserved. | 3 // Copyright 2009 The Go Authors. All rights reserved. |
4 // Use of this source code is governed by a BSD-style | 4 // Use of this source code is governed by a BSD-style |
5 // license that can be found in the LICENSE file. | 5 // license that can be found in the LICENSE file. |
6 | 6 |
7 package main | 7 package main |
8 | 8 |
9 type Number struct { | 9 type Number struct { |
10 next *Number | 10 next *Number |
11 } | 11 } |
12 | 12 |
13 | 13 |
14 // ------------------------------------- | 14 // ------------------------------------- |
15 // Peano primitives | 15 // Peano primitives |
16 | 16 |
17 func zero() *Number { | 17 func zero() *Number { |
18 » return nil; | 18 » return nil |
19 } | 19 } |
20 | 20 |
21 | 21 |
22 func is_zero(x *Number) bool { | 22 func is_zero(x *Number) bool { |
23 » return x == nil; | 23 » return x == nil |
24 } | 24 } |
25 | 25 |
26 | 26 |
27 func add1(x *Number) *Number { | 27 func add1(x *Number) *Number { |
28 » e := new(Number); | 28 » e := new(Number) |
29 » e.next = x; | 29 » e.next = x |
30 » return e; | 30 » return e |
31 } | 31 } |
32 | 32 |
33 | 33 |
34 func sub1(x *Number) *Number { | 34 func sub1(x *Number) *Number { |
35 » return x.next; | 35 » return x.next |
36 } | 36 } |
37 | 37 |
38 | 38 |
39 func add(x, y *Number) *Number{ | 39 func add(x, y *Number) *Number { |
40 if is_zero(y) { | 40 if is_zero(y) { |
41 » » return x; | 41 » » return x |
42 } | 42 } |
43 | 43 |
44 » return add(add1(x), sub1(y)); | 44 » return add(add1(x), sub1(y)) |
45 } | 45 } |
46 | 46 |
47 | 47 |
48 func mul(x, y *Number) *Number { | 48 func mul(x, y *Number) *Number { |
49 » if is_zero(x) || is_zero(y){ | 49 » if is_zero(x) || is_zero(y) { |
50 » » return zero(); | 50 » » return zero() |
51 } | 51 } |
52 | 52 |
53 » return add(mul(x, sub1(y)), x); | 53 » return add(mul(x, sub1(y)), x) |
54 } | 54 } |
55 | 55 |
56 | 56 |
57 func fact(n *Number) *Number { | 57 func fact(n *Number) *Number { |
58 if is_zero(n) { | 58 if is_zero(n) { |
59 » » return add1(zero()); | 59 » » return add1(zero()) |
60 } | 60 } |
61 | 61 |
62 » return mul(fact(sub1(n)), n); | 62 » return mul(fact(sub1(n)), n) |
63 } | 63 } |
64 | 64 |
65 | 65 |
66 // ------------------------------------- | 66 // ------------------------------------- |
67 // Helpers to generate/count Peano integers | 67 // Helpers to generate/count Peano integers |
68 | 68 |
69 func gen(n int) *Number { | 69 func gen(n int) *Number { |
70 if n > 0 { | 70 if n > 0 { |
71 » » return add1(gen(n - 1)); | 71 » » return add1(gen(n - 1)) |
72 } | 72 } |
73 | 73 |
74 » return zero(); | 74 » return zero() |
75 } | 75 } |
76 | 76 |
77 | 77 |
78 func count(x *Number) int { | 78 func count(x *Number) int { |
79 if is_zero(x) { | 79 if is_zero(x) { |
80 » » return 0; | 80 » » return 0 |
81 } | 81 } |
82 | 82 |
83 » return count(sub1(x)) + 1; | 83 » return count(sub1(x)) + 1 |
84 } | 84 } |
85 | 85 |
86 | 86 |
87 func check(x *Number, expected int) { | 87 func check(x *Number, expected int) { |
88 » var c = count(x); | 88 » var c = count(x) |
89 if c != expected { | 89 if c != expected { |
90 » » panic("error: found ", c, "; expected ", expected, "\n"); | 90 » » print("error: found ", c, "; expected ", expected, "\n") |
| 91 » » panic("fail") |
91 } | 92 } |
92 } | 93 } |
93 | 94 |
94 | 95 |
95 // ------------------------------------- | 96 // ------------------------------------- |
96 // Test basic functionality | 97 // Test basic functionality |
97 | 98 |
98 func verify() { | 99 func verify() { |
99 » check(zero(), 0); | 100 » check(zero(), 0) |
100 » check(add1(zero()), 1); | 101 » check(add1(zero()), 1) |
101 » check(gen(10), 10); | 102 » check(gen(10), 10) |
102 | 103 |
103 » check(add(gen(3), zero()), 3); | 104 » check(add(gen(3), zero()), 3) |
104 » check(add(zero(), gen(4)), 4); | 105 » check(add(zero(), gen(4)), 4) |
105 » check(add(gen(3), gen(4)), 7); | 106 » check(add(gen(3), gen(4)), 7) |
106 | 107 |
107 » check(mul(zero(), zero()), 0); | 108 » check(mul(zero(), zero()), 0) |
108 » check(mul(gen(3), zero()), 0); | 109 » check(mul(gen(3), zero()), 0) |
109 » check(mul(zero(), gen(4)), 0); | 110 » check(mul(zero(), gen(4)), 0) |
110 » check(mul(gen(3), add1(zero())), 3); | 111 » check(mul(gen(3), add1(zero())), 3) |
111 » check(mul(add1(zero()), gen(4)), 4); | 112 » check(mul(add1(zero()), gen(4)), 4) |
112 » check(mul(gen(3), gen(4)), 12); | 113 » check(mul(gen(3), gen(4)), 12) |
113 | 114 |
114 » check(fact(zero()), 1); | 115 » check(fact(zero()), 1) |
115 » check(fact(add1(zero())), 1); | 116 » check(fact(add1(zero())), 1) |
116 » check(fact(gen(5)), 120); | 117 » check(fact(gen(5)), 120) |
117 } | 118 } |
118 | 119 |
119 | 120 |
120 // ------------------------------------- | 121 // ------------------------------------- |
121 // Factorial | 122 // Factorial |
122 | 123 |
123 | 124 |
124 func main() { | 125 func main() { |
125 | 126 |
126 » verify(); | 127 » verify() |
127 for i := 0; i <= 9; i++ { | 128 for i := 0; i <= 9; i++ { |
128 » » print(i, "! = ", count(fact(gen(i))), "\n"); | 129 » » print(i, "! = ", count(fact(gen(i))), "\n") |
129 } | 130 } |
130 } | 131 } |
131 | |
OLD | NEW |