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