Higher-order functions in Go

March 04, 2023 at 19:37 Tags Go

A few weeks ago I wrote about the powerful abstractions that higher-order functions enable, using Clojure code as an example.

In this post I want to show equivalent code using a modern statically-typed language - Go. Please make sure to review the previous post first, since it describes the problem statement in detail.

Go and higher-order functions

While Go has many of the building blocks required to support functional programming, at this time it's not considered a mainstream programming paradigm for the language.

That said, my favorite part of functional programming is definitely supported and widely used in Go - higher-order functions. Go makes it simple to pass functions as arguments to other functions, and return functions from functions. Moreover, it has first-class support for closures, which makes the function-based design process much more powerful. This also meshes well with Go's automatic memory management, mostly eliminating worries about values going in and out of scope in closures.

The tree search example in Go

Let's reproduce the tree search example from the previous post in Go; the full code is here. The first task we run into is types; since Go is statically typed, we have to define our types explicitly:

type State int
type States []State

// GoalP takes a state and determines whether it's a goal state.
type GoalP func(s State) bool

// Successors returns the successors of a state.
type Successors func(s State) States

// Combiner determines the search strategy by combining successors of the
// current state with all the other states into a single list of states.
type Combiner func(succ States, others States) States

And this is the tree search function:

// treeSearch returns the state if it's found in the tree; returns -1 if such a
// state wasn't found.
func treeSearch(states States, goalp GoalP, succ Successors, combiner Combiner) State {
  if len(states) == 0 {
    return -1
  }

  first := states[0]
  if goalp(first) {
    return first
  } else {
    return treeSearch(combiner(succ(first), states[1:]), goalp, succ, combiner)
  }
}

While it's somewhat more verbose, its logic follows the Clojure code very closely. Now we're ready to define BFS search:

// prependOthers is a Combiner function that prepends others to succ.
func prependOthers(succ States, others States) States {
  return append(others, succ...)
}

func bfsTreeSearch(start State, goalp GoalP, succ Successors) State {
  return treeSearch(States{start}, goalp, succ, prependOthers)
}

To see how this function is invoked, we'll define a general infinite binary tree Successors function, and another for finite binary trees:

func binaryTree(s State) States {
  return []State{s * 2, s*2 + 1}
}

func finiteBinaryTree(n State) Successors {
  return func(s State) States {
    return filter(binaryTree(s), func(item State) bool { return item <= n })
  }
}

finiteBinaryTree is a nice example of higher-order functions in Go. It takes a value and returns a function that adheres to the Successors function type; in fact, it returns a new function created at runtime - a closure that closes over the value n. Moreover, the function it returns also makes use of higher-order functions in its body, because it invokes filter with a filtering function as a parameter. filter is:

// filter filters a slice based on a predicate, returning a new slice whose
// elements fulfill the predicate.
func filter[T any](s []T, pred func(item T) bool) []T {
  var result []T
  for _, item := range s {
    if pred(item) {
      result = append(result, item)
    }
  }
  return result
}

To call bfsTreeSearch we need to figure out another function parameter - the goal function (GoalP). We can use a higher-order function for this as well:

// stateIs returns a GoalP that checks a state for equality with n.
func stateIs(n State) GoalP {
  return func(s State) bool { return n == s }
}

Now we're ready to invoke bfsTreeSearch:

treeLimit := 30
tree := finiteBinaryTree(State(treeLimit))

bfsFound := bfsTreeSearch(1, stateIs(17), tree)

Note how similar this code is to the Clojure variant; Go supports all the same higher-order function constructs, letting us build powerful abstractions using them. The static types make the code somewhat more verbose, but this has advantages as well!

Imagine that you don't remember in which order successors and combiner should be passed to tree-search in the Clojure code; if you pass them in the wrong order, the code will build fine and you will get an error at runtime about invoking some function with the wrong number of arguments. This is lucky, because these two functions just happen to have different arities; in less lucky cases the error could come much later or be more obscure; or, there could be no error at all and the result could be incorrect.

In Go if you pass succ after combiner, you'll just get a compile-time type error.

Types have a benefit for documentation and code-reading purposes as well, but I don't want to turn this post into a static vs. dynamic typing debate. Let's look at some of the more advanced tree searching functions instead.

Even more higher-order functions in best-first search

A slightly more advanced example involves a "best"-first search; a greedy heuristic that sorts all state candidates by some criteria and pursues them in a priority order. We can still reuse our treeSearch function for it, but have to devise an appropriate Combiner. Let's start with a new function type:

type CostFunc func(s State) int

Given a state s, a cost function returns the integer cost. Now we can write our combiner that sorts a list of states based on a cost function:

func sorter(cost CostFunc) Combiner {
  return func(succ States, others States) States {
    all := append(succ, others...)
    sort.Slice(all, func(i, j int) bool {
      return cost(all[i]) < cost(all[j])
    })
    return all
  }
}

Another nice example of higher-order functions in action. sorter can be seen as a generator of Combiner functions; it can generate a new Combiner given a cost function. At this point we have all we need to implement bestCostTreeSearch:

func bestCostTreeSearch(start State, goalp GoalP, succ Successors, cost CostFunc) State {
  return treeSearch(States{start}, goalp, succ, sorter(cost))
}

The only thing remaining is figuring out what cost function we'd like to pass to the search. A simple one just measures the linear distance of a given state from our goal state:

// costDiffTarget creates a cost function that uses numerical distance from `n`
// as the cost.
func costDiffTarget(n State) CostFunc {
  return func(s State) int {
    delta := int(s) - int(n)
    if delta < 0 {
      return -delta
    } else {
      return delta
    }
  }
}

Given a target state, costDiffTarget generates a function that can serve as the cost function for search. We can now invoke bestCostTreeSearch:

treeLimit := 30
tree := finiteBinaryTree(State(treeLimit))

bestFound := bestCostTreeSearch(1, stateIs(17), tree, costDiffTarget(17))

Conclusion

Go has complete and powerful support for higher-order functions - including proper closures. While the syntax - mostly due to static typing - is somewhat more verbose than in other languages, it's more of an issue for code samples than it is for large code bases.

The verbosity issue is also in discussion by the Go developers, with proposals like Lightweight anonymous function syntax promising terser syntax and more powerful type inference. So there's hope for further improvement in this area.

Go itself uses higher-order functions extensively in the standard library; some examples include bufio.Scanner.Split, a whole array of *Func functions in the strings package (e.g. FieldsFunc), the sort.Slice function used in this post and of course net/http.ServeMux.HandleFunc.

Examples of returning functions also abound; the best known is probably the convention of the context package to return context.CancelFunc for context cancellation. But there are other examples, like net/http.ProxyUrl.

P.S. If you want to see a more mind-bending example of Go's higher-order functions, check out The Y combinator in Go with generics.

from Hacker News https://ift.tt/KsB7xGi