Higher-order functions in Go - Eli Bendersky's website

Higher-order functions in a statically typed language

A previous article on this site demonstrated the abstractions made possible by higher-order functions using Clojure. Go offers a useful contrast: it has the building blocks for functional programming, but the paradigm has never become mainstream there. The language does, however, support higher-order functions comfortably, and its closures are a central part of how idiomatic Go is written. Go's automatic memory management also removes usual concerns about values captured in closures going out of scope.

Reimplementing the tree-search example requires explicit type declarations first:

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

The search itself follows the same structure as the Clojure original, with the usual extra type noise:

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

Breadth-first search is defined without changing the core algorithm:

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

Defining successor functions for infinite and finite binary trees shows how higher-order functions combine with closures. The finite tree variant takes a value and returns a new Successors function that captures that value:

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

The returned function itself uses filter as a higher-order function:

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

The goal predicate can be generated the same way:

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

Invoking the search demonstrates how closely the Go version mirrors its dynamic-language counterpart:

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

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

The static types do add verbosity, but they also catch mistakes the dynamic version would miss. Passing succ and combiner in the wrong order in Clojure only fails at runtime — and only if the function arities happen to differ. In Go, it is a compile-time error. The types also serve as documentation for readers of the code.

Building a best-first search with a generated combiner

Extending the approach to best-first search requires a cost function and a combiner that sorts candidates by it. First, define the new function type:

type CostFunc func(s State) int

The combiner is itself produced by a higher-order function. Given a cost function, the generator returns an appropriate Combiner:

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

The search function ties everything together:

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

The cost function is generated from the 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
    }
  }
}

This allows the complete invocation:

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

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

Where this pattern shows up in practice

Higher-order functions are more than an academic exercise in Go; the standard library uses them extensively. Examples include bufio.Scanner.Split, the various *Func functions in the strings package such as FieldsFunc, sort.Slice, and net/http.ServeMux.HandleFunc. Returning functions is also common, with context.CancelFunc as the most prominent pattern. net/http.ProxyUrl is another illustration.

The verbosity noted in these examples is a known concern among Go developers; the "Lightweight anonymous function syntax" proposal aims to reduce it with terser syntax and stronger type inference. Even without that, the existing support for closures and function types enables the same powerful abstractions typically associated with more dynamically typed functional languages.