https://eli.thegreenplace.net/2022/the-y-combinator-in-go-with-generics/

Toggle navigation [log] Eli Bendersky's website

  * About
  * Archives

The Y combinator in Go with generics

June 11, 2022 at 07:55 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)

---------------------------------------------------------------------

For comments, please send me an email.

---------------------------------------------------------------------
(c) 2003-2022 Eli Bendersky

Back to top