fork download
copy 
  1. // Peano integers are represented by a linked list
  2. // whose nodes contain no data (the nodes are the data).
  3. // See: http://e...content-available-to-author-only...a.org/wiki/Peano_axioms
  4.  
  5. // This program demonstrates the power of Go's
  6. // segmented stacks when doing massively recursive
  7. // computations.
  8.  
  9. package main
  10.  
  11. import "fmt"
  12.  
  13. // Number is a pointer to a Number
  14. type Number *Number
  15.  
  16. // The arithmetic value of a Number is the count of
  17. // the nodes comprising the list.
  18. // (See the count function below.)
  19.  
  20. // -------------------------------------
  21. // Peano primitives
  22.  
  23. func zero() *Number {
  24. 	return nil
  25. }
  26.  
  27. func isZero(x *Number) bool {
  28. 	return x == nil
  29. }
  30.  
  31. func add1(x *Number) *Number {
  32. 	e := new(Number)
  33. 	*e = x
  34. 	return e
  35. }
  36.  
  37. func sub1(x *Number) *Number {
  38. 	return *x
  39. }
  40.  
  41. func add(x, y *Number) *Number {
  42. 	if isZero(y) {
  43. 		return x
  44. 	}
  45. 	return add(add1(x), sub1(y))
  46. }
  47.  
  48. func mul(x, y *Number) *Number {
  49. 	if isZero(x) || isZero(y) {
  50. 		return zero()
  51. 	}
  52. 	return add(mul(x, sub1(y)), x)
  53. }
  54.  
  55. func fact(n *Number) *Number {
  56. 	if isZero(n) {
  57. 		return add1(zero())
  58. 	}
  59. 	return mul(fact(sub1(n)), n)
  60. }
  61.  
  62. // -------------------------------------
  63. // Helpers to generate/count Peano integers
  64.  
  65. func gen(n int) *Number {
  66. 	if n > 0 {
  67. 		return add1(gen(n - 1))
  68. 	}
  69. 	return zero()
  70. }
  71.  
  72. func count(x *Number) int {
  73. 	if isZero(x) {
  74. 		return 0
  75. 	}
  76. 	return count(sub1(x)) + 1
  77. }
  78.  
  79. // -------------------------------------
  80. // Print i! for i in [0,9]
  81.  
  82. func main() {
  83. 	for i := 0; i <= 9; i++ {
  84. 		f := count(fact(gen(i)))
  85. 		fmt.Println(i, "! =", f)
  86. 	}
  87. }
  88.  
Success #stdin #stdout 0.24s 30008KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 ! = 1
1 ! = 1
2 ! = 2
3 ! = 6
4 ! = 24
5 ! = 120
6 ! = 720
7 ! = 5040
8 ! = 40320
9 ! = 362880
https://ideone.com/ZoVzt
language:
Go (go 1.12.1)
created:
14 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!