The Y combinator is not something Go code is likely to need in practice, but generics make a reasonably reusable implementation possible. Static typing costs some of the elegance the combinator has in dynamically typed languages, and the trick remains mostly a curiosity.

Typing the anonymous functions

Implementations in Clojure and Python rely on anonymous functions throughout; Go requires each of them to carry an explicit type. The pieces below describe how the combinator's definition is written in Go, not how the combinator works.

type Func[T, U any] func(T) U
type TagFunc[T, U any] func(Func[T, U]) Func[T, U]
type CombinatorFunc[T, U any] func(CombinatorFunc[T, U]) Func[T, U]

Three type declarations carry the structure. Func is the underlying computation function — the type the function would have if ordinary recursion were used. It takes two generic parameters: T for the argument and U for the result. What the user actually writes is a FuncTag, while CombinatorFunc exists only inside the definition of the Y combinator.

func Y[T, U any](f TagFunc[T, U]) Func[T, U] {
  return func(self CombinatorFunc[T, U]) Func[T, U] {
    return f(func(n T) U {
      return self(self)(n)
    })
  }(func(self CombinatorFunc[T, U]) Func[T, U] {
    return f(func(n T) U {
      return self(self)(n)
    })
  })
}

Producing a callable function

Because the recursive function may not refer to itself by name, the user first writes a "tag" function that accepts and returns a Func. That step is also where Func is instantiated with the concrete types required:

var factorial_tag = func(recurse Func[int, int]) Func[int, int] {
  return func(n int) int {
    if n == 0 {
      return 1
    }
    return n * recurse(n-1)
  }
}

Invoking Y then yields the function that can actually be called:

fac := Y(factorial_tag)

The result, fac, has type Func and evaluates the factorial of its argument, so it is used as answer := fac(param).

A second example: summing a binary tree

A function that sums the values in a binary tree exercises a more involved recursive flow, and its parameter and return types differ from each other:

type Node struct {
  val   int
  left  *Node
  right *Node
}

var treesum_tag = func(recurse Func[*Node, int]) Func[*Node, int] {
  return func(n *Node) int {
    if n == nil {
      return 0
    } else {
      return n.val + recurse(n.left) + recurse(n.right)
    }
  }
}

The usable function is once again generated by applying Y:

treesum := Y(treesum_tag)