| // $G $F.go && $L $F.$A && ./$A.out | |
| // Copyright 2009 The Go Authors. All rights reserved. | |
| // Use of this source code is governed by a BSD-style | |
| // license that can be found in the LICENSE file. | |
| package main | |
| type Number struct { | |
| next *Number | |
| } | |
| // ------------------------------------- | |
| // Peano primitives | |
| func zero() *Number { | |
| return nil; | |
| } | |
| func is_zero(x *Number) bool { | |
| return x == nil; | |
| } | |
| func add1(x *Number) *Number { | |
| e := new(Number); | |
| e.next = x; | |
| return e; | |
| } | |
| func sub1(x *Number) *Number { | |
| return x.next; | |
| } | |
| func add(x, y *Number) *Number{ | |
| if is_zero(y) { | |
| return x; | |
| } | |
| return add(add1(x), sub1(y)); | |
| } | |
| func mul(x, y *Number) *Number { | |
| if is_zero(x) || is_zero(y){ | |
| return zero(); | |
| } | |
| return add(mul(x, sub1(y)), x); | |
| } | |
| func fact(n *Number) *Number { | |
| if is_zero(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 is_zero(x) { | |
| return 0; | |
| } | |
| return count(sub1(x)) + 1; | |
| } | |
| func check(x *Number, expected int) { | |
| var c = count(x); | |
| if c != expected { | |
| panic("error: found ", c, "; expected ", expected, "\n"); | |
| } | |
| } | |
| // ------------------------------------- | |
| // Test basic functionality | |
| func verify() { | |
| check(zero(), 0); | |
| check(add1(zero()), 1); | |
| check(gen(10), 10); | |
| check(add(gen(3), zero()), 3); | |
| check(add(zero(), gen(4)), 4); | |
| check(add(gen(3), gen(4)), 7); | |
| check(mul(zero(), zero()), 0); | |
| check(mul(gen(3), zero()), 0); | |
| check(mul(zero(), gen(4)), 0); | |
| check(mul(gen(3), add1(zero())), 3); | |
| check(mul(add1(zero()), gen(4)), 4); | |
| check(mul(gen(3), gen(4)), 12); | |
| check(fact(zero()), 1); | |
| check(fact(add1(zero())), 1); | |
| check(fact(gen(5)), 120); | |
| } | |
| // ------------------------------------- | |
| // Factorial | |
| func main() { | |
| verify(); | |
| for i := 0; i <= 10; i++ { | |
| print(i, "! = ", count(fact(gen(i))), "\n"); | |
| } | |
| } | |