Foldable Go

I’m a big fan of functional programming. I think the principles behind it help to make code easier to reason about and simpler to test. The project I’m working on at the moment however is written in Go, which isn’t really designed for functional programming. So I set myself a challenge; to see if some functional techniques could be implemented with Go. This attempt was to replace for loops with the functional equivalent.

Generics

One problem is that Go is statically typed, but does not support generics. Code generation is available but it’s an added complication which adds constraints on how code is written and built.

The core of the problem with a lack of generics is not being able to re-use code. The only language feature Go has to allow this kind of code re-use is interfaces.

The idea is to have as much reusable code which can be derived from the smallest amount of unique code that needs to be written for each implementation. The ideal case is where no unique code needs to be written for each case, which is why generics are helpful.

This means that in Go the generic methods will need to return a generic type, which could be anything:

type T interface{}

Casting (called a type assertion in Go) result values from the generic type T will be required, which is obviously sacrificing a fair bit of type safety.

In addition Go doesn’t have covariant type checking. Neither of the following calls to function f will compile because a []int cannot be used as a []T. Therefore the generic type T will leak further out into the code than desired.

f := func(list []T) {
list = append(list, 4)
}
i := []int{1, 2, 3}
f(i)
f(i.([]T))

List comprehensions

Go code uses for loops everywhere, which means a lot of repeated code. I wanted to explore one of the most basic functional programming techniques, by implementing some list comprehension style processing to see what is possible. For example map, filter, take and partition.

A visual representation of a left fold

The great thing is, a lot of these functions can be implemented in terms of a fold function. Only a foldl (left fold) function needs to be defined for any particular type, and then generic versions of map, filter etc can be written.

Foldable

This is somewhat related to enumerable, iterators, functors, monads and other concepts, but here I’ve called it Foldable. Along with two other required methods, I came up with the following interface:

type Foldable interface {
Foldl(init T, f func(result, next T) T) T
Init() Foldable
Append(item T) Foldable
}

Init creates a new instance of the required type, while Append adds an element to the Foldable .

I then created generic functions which operate on this interface, for instance map:

func Map(foldable Foldable, mapFunc func(T) T) Foldable {
return foldable.Foldl(foldable.Init(), func(result, next T) T {
return result.(Foldable).Append(mapFunc(next))
}).(Foldable)
}

An obvious implementation of Foldable would be a generic List :

type List []Tfunc (list List) Foldl(init T, foldFunc func(result, next T) T) T {
result := init
for _, x := range list {
result = foldFunc(result, x)
}
return result
}
func (list List) Init() Foldable {
return List{}
}
func (list List) Append(item T) Foldable {
return append(list, item)
}

An example which multiplies each item by 2 would be:

Map(List{0, 1, 2}, func(x T) T { return x.(int) * 2 }).(List)

From these examples, it can be seem that a cast to the individual item is required as it is being processed, and another cast of the result back to List. Casting individual items when being read from the result is also required. The function must also return a T instead of the desired int . To reduce the number of places that casts are required, I could re-implement Foldable for specific types, eg slice of int[]int.

The real benefit though is that Foldable could be implemented for any built in or user defined data structure. A HashMap Foldable, a Set Foldable, an IO stream; and still reuse the same generic functions.

Parallel

One interesting generic function is a Parallel Map. MapToType is a function which changes the type between input and output foldable instances.

func async(waitGroup *sync.WaitGroup, mapFunc func() T) *T {
var r T
waitGroup.Add(1)
go func() {
r = mapFunc()
waitGroup.Done()
}()
return &r
}
func ParMap(foldable Foldable, mapFunc func(T) T) Foldable {
waitGroup := &sync.WaitGroup{}
pendingResults := MapToType(List{}, foldable,
func(next T) T {
return async(waitGroup,
func() T { return mapFunc(next) })
}).(Foldable)
waitGroup.Wait()
derefPointer := func(next T) T { return *next.(*T) }
return MapToType(foldable, pendingResults, derefPointer).
(Foldable)
}

Channels

Go has a built in concurrency primitive channels and they can be made Foldable too. Because of the way channels work, it wasn’t practical to write pure, immutable functions for the Channel type. It also required special handling in certain functions because they’re such a different Go type.

It’s worth the extra work to support this type, as it means lazy streams of data processing can be setup. The following example returns a new channel which applies the maths to any data sent to the original channel:

Map(
Map(
channel,
func(item T) T { return item.(int) * 2 }
).(Channel),
func(item T) T { return item.(int) + 1 }
).(Channel)

There are other interesting combinations, like performing a map in parallel over a channel, then filtering the results. The following example only includes the even results on the returned channel.

Filter(
ParMap(
channel,
func(item T) T { return item.(int) + 2}
).(Channel),
func(item T) bool { return item.(int) % 2 == 0 }
).(Channel)

Conclusion

The resulting code certainly isn’t idiomatic Go, as I’m fighting the language to a certain extent. A lot of the type safety has been lost as there are a few required casts, which is pretty ugly.

The exercise of building something higher level than a for loop in Go was interesting and worthwhile, but even being able to reuse and combine generic code in interesting ways doesn’t make up for the downsides.

Full source code is available at https://github.com/caspersg/gofuncs

Zendesk Engineering

Engineering @ Zendesk

Thanks to Steven McPhillips and Adel Smee

Casper Szymiczek-Graley

Written by

Zendesk Engineering

Engineering @ Zendesk

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade