The Y Combinator, a Lightning Talk from GoLab 2025

This is the "all killer, no filler" version of my previous talks on implementing the Y Combinator in Go.

The deck starts by explaining the problem the Y Combinator solves, then introduces the concept of the untyped lambda calculus and how that can be used to implement a near-unreadable version of the Y Combinator in Go.

It then goes through a number of refactoring steps in which meaningful names are introduced for the various component parts of the Y Combinator, concluding with a fully typed version which includes automated memoisation of previously calculated variables.

1. RECURSION THE HARD WAY
Y
ELEANOR M
C
HUGH
@feyeleanor
...AN EXTRACT FROM...

2. A NAMED FUNCTION CAN CALL ITSELF
package main
func main() {
main()
}
11.GO
github://feyeleanor/y_recursion_the_hard_way
this recurses because main() is a named function

3. BUT CAN AN ANONYMOUS FUNCTION CALL ITSELF
package main
func main() {
func(x) {
...
}
}
github://feyeleanor/y_recursion_the_hard_way
but how do we make an anonymous function recurse?

4. BUT CAN AN ANONYMOUS FUNCTION CALL ITSELF
package main
func main() {
g := func(x) {
g()
}
}
github://feyeleanor/y_recursion_the_hard_way
works if we run it in the scope where it's created?
otherwise it's not an option

5. ANONYMOUS FUNCTIONS ARE THE MATHEMATICAL BASIS OF COMPUTATION
github://feyeleanor/y_recursion_the_hard_way

6. ANONYMOUS FUNCTIONS AND THE LAMBDA CALCULUS
github://feyeleanor/y_recursion_the_hard_way

7. A FIXED POINT IS WHEN A FUNCTION RETURNS THE VALUE PASSED TO IT
github://feyeleanor/y_recursion_the_hard_way
in untyped lambda calculus functions are anonymous
but every function has a fixed point
which is not the general case in mathematics
so given f(x) = x
2 - 3x + 4
f(2) = 2 is a fixed point
meaning that calculating f for a value returns that value unchanged
so given f(x) = x
f(2) = 2 is also a fixed point

8. INTRODUCING THE Y COMBINATOR
Y g = (λf.(λx.f (x x)) (λx.f (x x))) g
= (λx.g (x x)) (λx.g (x x))
= g ((λx.g (x x)) (λx.g (x x)))
= g (Y g)
the Y combinator uses fixed points
to express recursion
for an anonymous function
github://feyeleanor/y_recursion_the_hard_way
this is good math but hard to read!

9. THE UNTYPED Y COMBINATOR IN GO
func Y(g func(any) any) func(any) any {
return func(f any) func(any) any {
return f.(func(any) any)(f).(func(any) any)
}(func(f any) any {
return g(func(x any) any {
return f.(func(any) any)(f).(func(any) any)(x)
})
})
}
25.GO
github://feyeleanor/y_recursion_the_hard_way
WTAF?!?!?!?!
it's even worse in go because of types

10. THE UNTYPED Y COMBINATOR IN GO (PRE-GENERICS)
func Y(g func(interface{}) interface{}) func(interface{}) interface{} {
return func(f interface{}) func(interface{}) interface{} {
return f.(func(interface{}) interface{})(f).(func(interface{}) interface{})
}(func(f interface{}) interface{} {
return g(func(x interface{}) interface{} {
return f.(func(interface{}) interface{})(f).(func(interface{}) interface{})(x)
})
})
}
25.GO
github://feyeleanor/y_recursion_the_hard_way
WTAF?!?!?!?!
!!!and it used to be even worse!!!

11. COMPUTING FACTORIALS IS A CLASSIC RECURSIVE PROBLEM
github://feyeleanor/y_recursion_the_hard_way

12. THE UNTYPED Y COMBINATOR
func main() {
...
factorial := Y(func(g any) any {
return func(n any) (r any) {
if n, ok := n.(int); ok {
switch {
case n == 0, n == 1:
return 1
case n > 1:
return n * g.(func(any) any)(n-1).(int)
}
}
panic(n)
}
})
...
}
func Y(g func(any) any) func(any) any {
return func(f any) func(any) any {
return f.(func(any) any)(f).(func(any) any)
}(func(f any) any {
return g(func(x any) any {
return f.(func(any) any)(f).(func(any) any)(x)
})
})
}
25.GO
github://feyeleanor/y_recursion_the_hard_way

13. INTRODUCING GO TYPES TO THE Y COMBINATOR
type Function func(any) any
func Y(g func(any) any) func(any) any {
return func(f any) func(any) any {
return f.(func(any) any)(f).(func(any) any)
}(func(f any) any {
return g(func(x any) any {
return f.(func(any) any)(f).(func(any) any)(x)
})
})
}
func Y(g Function) Function {
return func(f any) Function {
return f.(Function)(f).(Function)
}(func(f any) any {
return g(func(x any) any {
return f.(Function)(f).(Function)(x)
})
})
}
26.GO
github://feyeleanor/y_recursion_the_hard_way
becomes

14. INTRODUCING GO TYPES TO THE Y COMBINATOR
type Function func(any) any
func Recursor(f any) Function {
return f.(Function)(f).(Function)
}
func Y(g Function) Function {
return func(f any) Function {
return f.(Function)(f).(Function)
}(func(f any) any {
return g(func(x any) any {
return f.(Function)(f).(Function)(x)
})
})
}
func Y(g Function) Function {
return Recursor(
func(f any) any {
return g(func(x any) any {
return Recursor(f)(x)
})
})
}
26.GO
github://feyeleanor/y_recursion_the_hard_way
becomes

15. INTRODUCING GO TYPES TO THE Y COMBINATOR
type Function func(any) any
func Recursor(f any) Function {
return f.(Function)(f).(Function)
}
type Transformer func(Function) Function
func Y(g Function) Function {
return Recursor(
func(f any) any {
return g(func(x any) any {
return Recursor(f)(x)
})
})
}
func Y(g Transformer) Function {
return Recursor(
func(f any) any {
return g(func(x any) any {
return Recursor(f)(x)
})
})
}
26.GO
github://feyeleanor/y_recursion_the_hard_way
becomes

16. INTRODUCING GO TYPES TO THE Y COMBINATOR
type Function func(any) any
func Recursor(f any) Function {
return f.(Function)(f).(Function)
}
type Transformer func(Function) Function
func main() {
...
factorial := Y(func(g Function) Function {
return func(n any) (r any) {
if n, ok := n.(int); ok {
switch {
case n == 0, n == 1:
return 1
case n > 1:
return n * g(n-1).(int)
}
}
panic(n)
}
})
...
}
func Y(g Transformer) Function {
return Recursor(
func(f any) any {
return g(func(x any) any {
return Recursor(f)(x)
})
})
}
27.GO
github://feyeleanor/y_recursion_the_hard_way

17. SIMPLIFYING THE TYPED Y COMBINATOR
Y g = (λf.(λx.f (x x)) (λx.f (x x))) g
= (λx.g (x x)) (λx.g (x x))
= g ((λx.g (x x)) (λx.g (x x)))
= g (Y g)
github://feyeleanor/y_recursion_the_hard_way

18. SIMPLIFYING THE TYPED Y COMBINATOR
type Function func(any) any
type Transformer func(Function) Function
type Recursor func(Recursor) Function
func (r Recursor) Apply(t Transformer) Function {
return t(r(r))
}
func Y(t Transformer) Function {
g := func(r Recursor) Function {
return func(x any) any {
return r.Apply(t)(x)
}
}
return g(g)
}
func main() {
...
factorial := Y(func(g Function) Function {
return func(n any) (r any) {
if n, ok := n.(int); ok {
switch {
case n == 0, n == 1:
return 1
case n > 1:
return n * g(n-1).(int)
}
}
panic(n)
}
})
...
}
28.GO
github://feyeleanor/y_recursion_the_hard_way

19. THE Y COMBINATOR WITH GENERIC TYPES
type Function[T, R any] func(T) R
type Transformer[T, R any] func(Function[T, R]) Function[T, R]
type Recursor[T, R any] func(Recursor[T, R]) Function[T, R]
func (r Recursor[T, R]) Apply(t Transformer[T, R]) Function[T, R] {
return t(r(r))
}
func Y[T, R any](t Transformer[T, R]) Function[T, R] {
g := func(r Recursor[T, R]) Function[T, R] {
return func(x T) R {
return r.Apply(t)(x)
}
}
return g(g)
}
func main() {
...
factorial := Y(func(g Function[int, int]) Function[int, int] {
return func(n int) (r int) {
switch {
case n < 0:
panic(n)
case n > 1:
return n * g(n - 1)
}
return 1
}
})
...
}
29.GO
github://feyeleanor/y_recursion_the_hard_way

20. THE GENERIC Y COMBINATOR WITH AUTOMATIC RESULT CACHING
func Y[T comparable, R any](t Transformer[T, R]) Function[T, R] {
m := make(map[T]R)
g := func(r Recursor[T, R]) Function[T, R] {
return func(x T) (v R) {
var ok bool
if v, ok = m[x]; ok {
return v
}
v = r.Apply(t)(x)
m[x] = v
fmt.Printf("Y: setting m[%v] = %v", x, v)
return v
}
}
return g(g)
}
func main() {
...
factorial := Y(func(g Function[int, int]) Function[int, int] {
return func(n int) (r int) {
switch {
case n < 0:
panic(n)
case n > 1:
return n * g(n-1)
}
return 1
}
})
...
}
30.GO
github://feyeleanor/y_recursion_the_hard_way

22. LEANPUB://GONOTEBOOK [GITHUB | SLIDESHARE]://FEYELEANOR