blob: ccff66bfef966e6588ba7e5810568abcba93d0e6 [file] [log] [blame]
 // \$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 <= 9; i++ { print(i, "! = ", count(fact(gen(i))), "\n"); } }