Skip to content

Instantly share code, notes, and snippets.

@wardenlym
Forked from wancw/y-combinator.go
Created March 19, 2018 07:49
Show Gist options
  • Save wardenlym/1932aac3ed08bfe4633b061390182444 to your computer and use it in GitHub Desktop.
Save wardenlym/1932aac3ed08bfe4633b061390182444 to your computer and use it in GitHub Desktop.
Y combinator in Go, runable example: http://play.golang.org/p/xVHw0zoaWX
package main
import "fmt"
type (
tF func(int) int
tRF func(tF) tF
tX func(tX) tF
)
func Y(rf tRF) tF {
return func(x tX) tF { return func(n int) int { return rf(x(x))(n) } }(
func(x tX) tF { return func(n int) int { return rf(x(x))(n) } })
}
var fib = Y(func(f tF) tF {
return func(n int) int {
if n == 0 || n == 1 {
return n
}
return f(n-1) + f(n-2)
}
})
var fact = Y(func(f tF) tF {
return func(n int) int {
if n < 2 {
return 1
}
return n * f(n-1)
}
})
func main() {
for i := 1; i < 10; i++ {
fmt.Printf("%2d : %2d, %6d\n", i, fib(i), fact(i))
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment