Skip to content

Instantly share code, notes, and snippets.

@yackx
Created February 5, 2014 07:58
Show Gist options
  • Save yackx/8819052 to your computer and use it in GitHub Desktop.
Save yackx/8819052 to your computer and use it in GitHub Desktop.
Peano integers in Go
// Peano integers are represented by a linked
// list whose nodes contain no data
// (the nodes are the data).
// http://en.wikipedia.org/wiki/Peano_axioms
package main
import "fmt"
// Number is a pointer to a Number
type Number *Number
func zero() *Number {
return nil
}
func isZero(x *Number) bool {
return x == nil
}
func succ(x *Number) *Number {
n := new(Number)
*n = x
return n
}
func prec(x *Number) *Number {
return *x
}
func add(x, y *Number) *Number {
if isZero(x) {
return y
}
return add(prec(x), succ(y))
}
func gen(i int) *Number {
if i > 0 {
return succ(gen(i - 1))
}
return zero()
}
func toInt(x *Number) int {
if isZero(x) {
return 0
}
return toInt(prec(x)) + 1
}
func isEven(x *Number) bool {
if isZero(x) {
return true
}
return !isEven(prec(x))
}
func isOdd(x *Number) bool {
return !isEven(x)
}
func main() {
fmt.Println("4+5 =", toInt(add(gen(4), gen(5))))
fmt.Println("isEven/isOdd 4 ?", isEven(gen(4)), isOdd(gen(4)))
fmt.Println("isEven/isOdd 5 ?", isEven(gen(5)), isOdd(gen(5)))
fmt.Println("isEven/isOdd 0 ?", isEven(gen(0)), isOdd(gen(0)))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment