The Y combinator in Go with generics

A few years ago I've written in some detail about the Y combinator, including implementations in Clojure and Python.

This short post is showing how to implement the Y combinator in Go using generics; in general, static typing makes the Y combinator somewhat less appealing, but I figured that generics will at least allow the implementation to be reasonably reusable. Not that this is useful in any real-world scenario, of course :-)

I won't explain how the Y combinator itself works here (please refer to the previous post for that), only the Go specifics. The full, runnable code for this post is available on GitHub.

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]

The Y combinator's definition uses several kinds of anonymous functions. In Go, we need those to have explicit types. Func is the underlying computation function - it's what the function type would be if we'd used normal recursion. It's parameterized with two generic types: T for its parameter type and U for its return type.

FuncTag is the type of the functions users should write now. CombinatorFunc is only used in the definition of the Y combinator itself:

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)
    })
  })
}

Here's how to use it. To define a recursive factorial-computing function that does not refer to itself by name, the user has to create a "tag" function that takes and returns a Func. At this point we also instantiate the Func to have the exact types we need:

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)
  }
}

And the actual factorial function that users can call is created with:

fac := Y(factorial_tag)

Now fac is function of type Func: it computes and returns the factorial of its parameter, and can be simply invoked as answer := fac(param).

We can also try the other example in my previous post - a function that finds the sum of values in a binary tree. It demonstrates a slightly more complicated recursive flow as well as different types for the function's parameter and return value:

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)
    }
  }
}

And once again, the actual usable function is generated by invoking Y:

treesum := Y(treesum_tag)