Tags Go , Lisp

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