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");
}
}