Go 1.18: Fold with generics

Go 1.18 beta2 was released and with that we have an estimated release date for Go 1.18 and it’s March.

Because we are taking the time to issue a second beta, we now expect that the Go 1.18 release candidate will be issued in February, with the final Go 1.18 release in March.

Source: https://go.dev/blog/go1.18beta2

One of the main feature of the next version is generics. We can finally say goodbye to all the xxxInt64, xxxUint, and xxxInt functions, and replace it with generic functions. It’s awesome.

I use foldl and foldr a lot, at least the logic behind them, but sadly in Go it was very challenging before. With generics it’s finally easy to implement and easy to use.

Folding in general

Let’s see how foldl and foldr work in general. We have a list and we want to reduce or convert into a different structure, we can use folding into an accumulator. foldl is left-associative and foldr is right-associative.

An easy example with foldl. We have an initial list of numbers and we want to calculate their product. Sounds easy, it can be done in a simple loop, I know, but simple enough to get the idea of folding. In this case we have a list of int values and we get back a single int64 value. Why the type difference? It’s easier to see how it works if they have different types, we can use the same type.

First, we need a function that takes two argument, an accumulator (int64) and a single value (int), and returns with a new accumulator (int64).

func myfold(accumulator int64, value int) int64 {
  return accumulator * int64(value)
}

What do we want? We want to walk through on our list and call myfold on the next value and set the accumulator value to the value returned by the previous myfold all. With a loop it looks like this:

acc := int64(myList[0])
for _, value := range myList[0:] {
  acc = myFold(acc, value)
}

foldr does the same, but from the right to the left.

Folding is not only reducing

In general folding take an initial value and something we can iterate through and returns with a single something. The output can be the same type as the input, we can generate a new list from a list, but that’s most likely a map, except if you need previous values.

Generics in Go

We can specify type parameters and we can reuse them. There built-in type constraints like comparable or any. We can define new ones as well. We can define these type parameters in square brackets.

func Something[K comparable, V int64 | float64](table map[K]V) (K, V) {
  // ....
}

With this, we have a function Something that takes one map argument. The keys of the map has to be comparable and the values can be either int64 or float64. At the end the function returns with a K type key and a V type value.

Define a type constraint:

type Number64 interface {
    int64 | float64
}

With this, we can rewrite the function to use Number64 instead of int64 | float64:

func Something[K comparable, V Number64](table map[K]V) (K, V) {
  // ....
}

Foldl with generics

Now we understand how folding works, we can implement our foldl and foldr functions with generics.

func Foldl[T any, R any](init R, list []T, fold func(carry R, next T) R) R {
  for _, value := range list {
    init = fold(init, value)
  }

  return init
}

func Foldr[T any, R any](init R, list []T, fold func(carry R, next T) R) R {
  for idx := len(list)-1; idx >=0; idx-- {
    init = fold(init, list[idx])
  }

  return init
}

Product of integers

Take the first item as initial value and Foldl with the rest. In this case it does not matter if we use Foldl or Foldr because multiplication is associative and commutative.

myList := []int{1,2,3,4,5}

resultInt := Foldl(int64(myList[0]), myList[0:], func(c int64, value int) int64 {
  return c*int64(value)
})

fmt.Println(resultInt)  // 120

Reverse a string

In this case, foldl and foldr are not returning with the same value.

resultStrR := Foldr("", []rune("fancy"), func(c string, value rune) string {
  return c + string(value)
})

resultStrL := Foldl("", []rune("fancy"), func(c string, value rune) string {
  return c + string(value)
})

fmt.Println(resultStrR) // ycnaf
fmt.Println(resultStrL) // fancy

Construct a Family

We can go wild and crazy, let’s say we have a list of Persons and we want to group them as Family. A Person has a name and an age. A Family has adults and children.

type Person struct {
  Name string
  Age int
}

type Family struct {
  Adults []Person
  Children []Person
}

func newFamily() Family {
  return Family{Adults: []Person{}, Children: []Person{}}
}

Now we have all the required structs, we can define out list:

people := []Person{
  {Name: "Alice", Age: 16},
  {Name: "Bob", Age: 21},
  {Name: "Carol", Age: 33},
  {Name: "Dylan", Age: 12},
}

And finally, we can use folding to construct the Family:

resultFamily := Foldl(Family{}, people, func(c Family, value Person) Family {
  if value.Age < 18 {
    c.Children = append(c.Children, value)
  } else {
    c.Adults = append(c.Adults, value)
  }

  return c
})

fmt.Println(resultFamily.Adults)   // [{Bob 21} {Carol 33}]
fmt.Println(resultFamily.Children) // [{Alice 16} {Dylan 12}]

A more complex problem, filter

Creating filters is always a never ending story and with folds we have a new way to do easily.

First define our base filters:

type Filter interface {
  String() string
}

type NameFilter struct {
  value string
}

func (f NameFilter) String() string {
  return fmt.Sprintf("name=%s", f.value)
}

func Name(value string) NameFilter {
  return NameFilter{value: value}
}

type AgeFilter struct {
  value int
}

func (f AgeFilter) String() string {
  return fmt.Sprintf("name=%d", f.value)
}

func Age(value int) AgeFilter {
  return AgeFilter{value: value}
}

Now we can define some extra filters:

type OrFilter struct {
  values []Filter
}

func (f OrFilter) String() string {
  values := fold.Foldl([]string{}, f.values, func(c []string, value Filter) []string {
    return append(c, value.String())
  })

  return fmt.Sprintf("(%s)", strings.Join(values, " || "))
}

func Or(values ...Filter) OrFilter {
  return OrFilter{values: values}
}

type AndFilter struct {
  values []Filter
}

func (f AndFilter) String() string {
  values := fold.Foldl([]string{}, f.values, func(c []string, value Filter) []string {
    return append(c, value.String())
  })

  return fmt.Sprintf("(%s)", strings.Join(values, " && "))
}

func And(values ...Filter) AndFilter {
  return AndFilter{values: values}
}

With this we can chain filters to a query:

query := filter.And(
  filter.Or(filter.Name("alice"), filter.Name("bob")),
  filter.Or(filter.Age(55), filter.Age(31)),
)

fmt.Println(query.String()) // ((name=alice || name=bob) && (name=55 || name=31))

Obviously this can be achieved a lot of other ways, but here is a new method ;)