Go’s Missing Functional Suspects

When you first start learning functional programming you get all kinds of tools that challenge how you think about lists. You get things like foldlfoldrmap, and filter. Those things are really hard to stop using because they’re very concise and clear in the way they function. Let’s make a golang generator that gives us those four functions for any type in go!

Writing a generator

Go could have macros but it doesn’t because there’s no precompiler. Instead of a precompiler they wrote code that does what macros do but you have to run it manually before you run your code rather than just inlining during compilation. So let’s write a generator that just spits out a random number and then we’ll modify it later so that it gives us what we want function wise.

In your scratch pad project directory toss the following into a file (pkg/generators/functional.go):

//go:build ignore

package main

import (
        "fmt"
        "math/rand"
        "os"
        "text/template"
        "time"
)

var genTemplate = `// Code generated by go; DO NOT EDIT.
// Generated {{ .Timestamp }}
package main

import "fmt"

func main() {
  fmt.Printf("%d\n", {{.Random}})
}
`

func main() {
        file, err := os.Create("main_random.go")
        if err != nil {
                fmt.Errorf("%v", err)
                os.Exit(1)
        }
        defer file.Close()

        template.Must(template.New("").Parse(genTemplate)).Execute(file, struct {
                Random    uint64
                Timestamp time.Time
        }{
                rand.Uint64(),
                time.Now(),
        })
}

What a mouthful. Don’t worry, this should make what we’re about to do much easier. This generator will get modified later. You can test it manually by doing a quick go run pkg/generators/functional.go && go run main_random.go and you can clean it up by just removing the generated main_random.go file. I’m going to put this generator in pkg/generators directory to refer to later so we have this directory structure for the demo:

.
├── app.go
├── go.mod
└── pkg
    └─── generators
         └── functional.go

Demo structs

Now let’s make a demo struct we can do something functional with. In pkg/mytypes/demo.go:

package mytypes

//go:generate go run ../generators/functional.go Demo string int

type Demo struct {
        Str string
        Num int
}

Now if you run go generate pkg/mytypes/demo.go you’ll actually see a new file main_random.go that will still just spit out a random number. Let’s fix that to do a filter.

Implementing filter

Focusing on pkg/generators/functional.go and modify a few things. First, the package needs to be fixed so change that the template does something more in the spirit of functional programming (make this more practical if you’re following this for real world stuff). Let’s enhance our generator to loop over arguments and use those. Our generator should now look something like:

//go:build ignore

package main

import (
        "fmt"
        "os"
        "strings"
        "text/template"
        "time"
)

var genTemplate = `{{- $m := . -}}
// Code generated by go; DO NOT EDIT.
// Generated {{ $m.Timestamp }}
// Functional receivers for {{ $m.Receiver }}
// With types {{ $m.Types }}

package {{ $m.Package }}
`

func gen(pkg, name string, types []string) error {
        file, err := os.Create(fmt.Sprintf("%s_fns.go", strings.ToLower(name)))
        if err != nil {
                return err
        }
        defer file.Close()

        funcs := template.FuncMap{
                "Title": strings.Title,
        }

        template.Must(template.New("").Funcs(funcs).Parse(genTemplate)).Execute(file, struct {
                Package   string
                Receiver  string
                Alias     string
                Types     []string
                Timestamp time.Time
        }{
                pkg,
                name,
                fmt.Sprintf("%ss", name),
                types,
                time.Now(),
        })
        return nil
}

func main() {
        if err := gen(os.Args[1], os.Args[2], os.Args[3:]); err != nil {
                fmt.Fprintf(os.Stderr, "error generating %s: %v\n", os.Args[1], err)
        }
}

and after go generate pkg/mytypes/demo.go our directory should be:

.
├── app.go
├── go.mod
└── pkg
    ├── generators
    │   └── functional.go
    └── mytypes
        ├── demo_fns.go
        └── demo.go

In the main function of the generator we’re gather arguments and giving them to the generator one by one. The line checking for a lowercase first letter is the gatherer. It’s not going to get any use for filter but we will need it for map because it takes one type and doesn’t necessarily return that type.

Now we’re pretty much set for life. Time to retire. Unless you’re having fun then let’s do some filtering. From here it’s just straight go.

Our filter function should look something like this:

type AS []A

func (xs As) Filter(fn func(A) bool) []A {
    rs := make([]A, 0)
    for _, x := range xs {
        if fn(x) {
            rs = append(rs, x)
        }
    }
    return rs
}

And we can template-ize that as:

type {{ $m.Alias }} []{{ $m.Receiver }}

func (xs {{ $m.Alias }}) Filter(fn func({{ $m.Receiver }}) bool) []{{ $m.Receiver }} {
        rs := make([]{{ $m.Receiver }}, 0)
        for _, x := range xs {
                if fn(x) {
                        rs = append(rs, x)
                }
        }
        return rs
}

So now when you run your generate statement you should get the following in pkg/mytypes/demo_fns.go:

// Code generated by go; DO NOT EDIT.
// Generated 2021-11-12 16:28:41.742174392 -0800 PST m=+0.000470763
// Functional receivers for Demo
// With types [string int]

package mytypes

type Demos []Demo

func (xs Demos) Filter(fn func(Demo) bool) []Demo {
        rs := make([]Demo, 0)
        for _, x := range xs {
                if fn(x) {
                        rs = append(rs, x)
                }
        }
        return rs
}

Now, wherever Demos are used you can do a quick demos.Filter(func (d Demo) { return d.Num > 3 }) to get all of your objects where the number is greater than three. In your own version you might even change the return type so that .Filter becomes chainable with some other stuff down the line.

Map

Map gets a little sticky. The return type is usually known to the programmer but go’s compiler needs to know. This is where all that wonky stuff we did in the generator’s main comes in handy. We can tell our generator what it is we really need from a Map.

Our ideal Map might look something like:

func (xs Demos) MapString(fn func(Demo) string) []string {
    rs := make([]string, 0)
    for _, x := range xs {
        rs = append(rs, fn(x))
    }
    return rs
}

Jeez, what a beaut.

To template that we need to be able to loop over whatever types were requested of the generator and to do that we can use some template magic:

{{- range $t := $m.Types }}
func (xs {{ $m.Alias }}) Map{{ $t | Title }}(fn func({{ $m.Receiver }}) {{ $t }}) []{{ $t }} {
        rs := make([]{{ $t }}, 0)
        for _, x := range xs {
                rs = append(rs, fn(x))
        }
        return rs
}
{{- end }}

This loops over the types our main parsed and generates MapString and MapInt. If you need others you can always go back to your pkg/mytypes/demo.go file and add the types to your go:generate line. Now when you generate you’ll have two more functions in your package.

So now we have filter and map. Lastly we need some fold equivalents and we’ll generate those in the mytypes package simply because this is a demo and you shouldn’t be copy and pasting code blindly into your editor.

Implementing folds

So, create another generator file called pkg/generators/folds.go and let’s modify functions main and gen to look like this:

func gen(pkg string, pairs [][]string) error {
        file, err := os.Create(fmt.Sprintf("%s_folds.go", strings.ToLower(pkg)))
        if err != nil {
                return err
        }
        defer file.Close()

        funcs := template.FuncMap{
                "Title": strings.Title,
        }

        template.Must(template.New("").Funcs(funcs).Parse(genTemplate)).Execute(file, struct {
                Package   string
                Pairs     [][]string
                Timestamp time.Time
        }{
                pkg,
                pairs,
                time.Now(),
        })
        return nil
}

func main() {
        pkg := os.Args[1]
        pairs := [][]string{}
        for idx := 2; idx < len(os.Args); idx += 2 {
                pairs = append(pairs, os.Args[idx:idx+2])
        }
        gen(pkg, pairs)
}

Our fold generator is going to take a list of type pairs we need folds for and generate those. So if we give the generator string int we’ll get folds where our accumulator and inputs are of types string int respectively.

In our template we’ll modify the non-boilerplate comments with the following bit of cuteness:

{{ range $t := $m.Pairs }}
func Foldl{{ index $t 0 | Title }}{{ index $t 1 | Title }}(fn func(a {{ index $t 0 }}, b {{ index $t 1 }}) {{ index $t 0 }}, acc {{ index $t 0 }}, is []{{ index $t 1 }}) {{ index $t 0 }} {
        res := acc
        for i := range is {
                res = fn(res, len(is) - 1 - i)
        }
        return res
}

func Foldr{{ index $t 0 | Title }}{{ index $t 1 | Title }}(fn func(a {{ index $t 0 }}, b func() {{ index $t 1 }}) {{ index $t 0 }}, acc {{ index $t 0 }}, is []{{ index $t 1 }}) {{ index $t 0 }} {
        res := acc
        for idx := 0; idx < len(is); idx++ {
                called := false
                lambda := func() {{ index $t 1 }} {
                        called = true
                        return is[idx]
                }
                res = fn(res, lambda)
                if !called {
                        return res
                }
        }
        return res
}
{{- end }}

With the input tuple string, int this template will generate FoldlStringInt and FoldrStringInt. Now we’re having some real fun.

Now we can add //go:generate go run ../generators/folds.go mytypes int int to pkg/mytypes/demo.go, run the generator, and then you can view the very excellent generated code in pkg/mytypes/mytypes_folds.go:

// Code generated by go; DO NOT EDIT.
// Generated 2021-11-12 16:52:05.48205752 -0800 PST m=+0.000807965
// Functional folds for mytypes
// Pairs:
// int - int

package mytypes


func FoldlIntInt(fn func(a int, b int) int, acc int, is []int) int {
        res := acc
        for i := range is {
                res = fn(res, len(is) - 1 - i)
        }
        return res
}

func FoldrIntInt(fn func(a int, b func() int) int, acc int, is []int) int {
        res := acc
        for idx := 0; idx < len(is); idx++ {
                called := false
                lambda := func() int {
                        called = true
                        return is[idx]
                }
                res = fn(res, lambda)
                if !called {
                        return res
                }
        }
        return res
}

Boom.

Wait just a gosh dang minute. Why’s that foldr look so weird? Well, short story is that in Haskell and similarly implemented languages, foldr will thunk the right value and only continue if that value is requested and in that way you can prematurely terminate a right fold. A left fold will not happen as the fold is evaluated from the left. This is a confusing thing if you’re not already familiar with it but the basics are that foldl + [1 2 3] -> (1 + (2 + 3)) and thus cannot short circuit. Conversely, foldr + [1 2 3] -> (3 + (2 + (1))) and if you notice the 1 in its own parens then you’ll notice that the + is only done if the next value is evaluated.

Okay, now boom slam.

That’s all for today!

About the author:

Tony O’Dell Tony O’Dell is a Software Engineer at AlphaFlow. Tony previously worked as a backend developer for GoDaddy, ZipRecruiter, and as a contractor specializing in Data Warehousing and Statistical Analysis.

Tony grew up in Michigan and has lived and visited many parts of the world. He served in the Marine Corps for five years working in avionics designing and building test equipment and working on the fast bois.

back to top